Lockdown ve Beklenen Değer

Geçmiş yarışmaların sorularını çözerken Lockdown problemi dikkatimi çekti. Bicoyu ve Fakoyu aradan çıkarıp problemi çevirelim. Elimizde N ve M yüzlü iki hilesiz tane zar var. Bu zarları birlikte atıyoruz. Sonuçlarımız a ve b olsun. Bu çıkan sonuçların mutlak değerini bir s değişkeni üzerinde topluyoruz s += |a-b|.

Zarların toplamının en az K olması için beklenen zar atım sayısı nedir ?

Kısıtlar: 2<=N<=100, 2<=M<=100, K<10^9

Problemin çözümü

Beklenen değer için denklem sistemimizi yazalım.

$i=0..max(N,M)-1$

$p[i], |a-b| \text{ değerinin gelme ihtimali olsun.}$

$d[i], |a-b| \text{ değerinin kendisi olsun.}$

$$ E[0] = 0$$

$$E[n] = 1 + \sum_{i=0}^{max(N,M)-1} p[i] * E[n - d[i]]$$

Problemimiz buraya kadar çözülmüş gibi duruyor. Ancak n - d[i] ifadesinde d[i]=0 olursa sonsuz döngüye girer. Denklem sistemimizi 0 dan kurtaracak şekilde çözersek.

$$E[n] = 1 + p[0] * E[n] + p[1] * E[n-1] \cdots$$

$$E[n] - p[0] = 1 + p[1] * E[n-1] \cdots$$

$$E[n] = \frac{1 + p[1] * E[n-1] \cdots}{1-p[0]}$$

$$E[n] = \frac{ 1+\sum_{i=1} p[i] * E[n - d[i]]}{1-p[0]}$$

Bunu recurrence relation haline getirirsek

$$E[n] = \begin{cases} 0 & \text{if $n\leq0$} \\ \frac{1}{1-p[0]} & \text{if $n=1$} \\ \frac{1}{1-p[0]} + \sum_{i\neq0} \frac{p[i]}{{1-p[0]}}* E[n - d[i]] & \text{if $n>1$} \end{cases}$$

Buraya kadar olan kısmın kodunu yazalım.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
#define maxSize 5
using namespace std;

double p[maxSize];
double d[maxSize];
map<double,double> dp;

double E1(int k, int size){
    if(k <= 0) return 0; // base condition
    if(dp.find(k) != dp.end()) return dp[k];

    double tot = 0;
    for(int i = 1; i < size; i++)
        tot += p[i] * E1(k - d[i], size) / (1 - p[0]);

    return dp[k] = tot + 1. / (1 - p[0]);
}

int main(){
    int N = 3;
    int M = 3;
    int K = 20;
    int size = max(N,M);

    map<int,double> freq;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            freq[abs(i-j)]++;// frekanslar

    for(auto c: freq) 
        p[c.first] = (double)c.second / (double)(N*M);// olasiliklar

    for(int i = 0 ; i < size ; i++)
        d[i] = i; // Adim sayilari

    cout << E(K,size) << endl;
}

Bu bize N in çok büyük olmayan değerleri için doğru sonucu verecektir. Ancak problemde K sayısı büyük olduğu için lineer yöntemlerden birini tercih edemeyiz. Kendini tekrar eden homojen lineer denklem sistemimizin n. elemanını arıyorsak matrix çarpımından faydalanabiliriz.

N = 3, M = 3 seçersek

$$ F[n] = c1 * F[n-1] + c2 * F[n-2] + k$$

şeklindeki bir recurrence ilişkinin n inci elemanı bulmak istiyorsak.

$$\begin{bmatrix} F[n] \\ F[n-1] \\ F[1] \end{bmatrix}= \begin{bmatrix} c1 & c2 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{n-3}* \begin{bmatrix} F[3] \\ F[2] \\ F[1] \end{bmatrix}$$

Bu eşitliği kullanarak Fast Matrix Exponentiation ile $O(max(N,M)^3 log K)$ zaman karmaşıklığıyla çözümü bulabiliriz.

Inputlar değişken olmasaydı verilen değerler için generating function hesaplayarak O(1) çözüm elde edebilirdik.