Help with Atcoder Educational DP Contest

general
,
1

Can anyone please explain me the approach and the logic behind solving the Sushi problem in AtCoder Educational DP Contest? Link to the problem:- J - Sushi

2

SInce the order doesn’t matter, consider a_i to be the number of dishes with i sushis.
Let dp(i,j,k,l) represent i dishes with 0 sushis, j dishes with 1 sushi and so on.
We have a base case
dp(n,0,0,0)=0
Furthermore, the chance of choosing a plate with i sushis is \frac{a_i}{n}.
Notice that whenever we eat from a plate with i sushis, i>0, the number of dishes with i sushis reduce by one, and the number of dishes with i-1 sushis increases by 1.
Therefore
dp(a_0,a_1,a_2,a_3) = \frac{a_0}{n}dp(a_0,a_1,a_2,a_3) + \frac{a_1}{n}dp(a_0 + 1,a_1-1,a_2,a_3) + \frac{a_2}{n}dp(a_0,a_1+1,a_2-1,a_3)+\frac{a_3}{n}dp(a_0,a_1,a_2+1,a_3-1) + 1
We add 1 because it takes one turn to to go there.
Simplifying the expression
\frac{n-a_0}{n}dp(a_0,a_1,a_2,a_3) = \frac{a_1}{n}dp(a_0 + 1,a_1-1,a_2,a_3) + \frac{a_2}{n}dp(a_0,a_1+1,a_2-1,a_3)+\frac{a_3}{n}dp(a_0,a_1,a_2+1,a_3-1) + 1
Given that \sum a_i = n
\frac{a_1+a_2+a_3}{n}dp(a_0,a_1,a_2,a_3) = \frac{a_1}{n}dp(a_0 + 1,a_1-1,a_2,a_3) + \frac{a_2}{n}dp(a_0,a_1+1,a_2-1,a_3)+\frac{a_3}{n}dp(a_0,a_1,a_2+1,a_3-1) + 1. In fact, we can neglect a_0 always as it can be written as n-a_1-a_2-a_3.
Removing a_0 as a dependency gives
\frac{a_1+a_2+a_3}{n}dp(a_1,a_2,a_3) = \frac{a_1}{n}dp(a_1-1,a_2,a_3) + \frac{a_2}{n}dp(a_1+1,a_2-1,a_3)+\frac{a_3}{n}dp(a_1,a_2+1,a_3-1) + 1.
Simplifying
dp(a_1,a_2,a_3) =\frac{n}{a_1+a_2+a_3} (\frac{a_1}{n}dp(a_1-1,a_2,a_3) + \frac{a_2}{n}dp(a_1+1,a_2-1,a_3)+\frac{a_3}{n}dp(a_1,a_2+1,a_3-1)+ 1).

code snippet 
long double solve(int a,int b,int c){
    long double currans=0;
    if(a<0 || b<0 || c<0){
        return 0;
    }
    if(ans[a][b][c]!=-1){
        return ans[a][b][c];
    }
    long double A=a,B=b,C=c;
    currans=(A/n * solve(a-1,b,c)) + (B/n * solve(a+1,b-1,c)) +(C/n * solve(a,b+1,c-1)) + 1;
    currans*=n;
    currans/=a+b+c;
    ans[a][b][c]=currans;
    return ans[a][b][c];
}
3 Likes
3

Thank you so much :smile:

4

Just one more doubt. In the REBIT problem of April Long what do we have to print as the output. I am not asking for a solution but I am unable to figure out the meaning of the last sentence of the problem statement, “compute P.Q^(-1) modulo 998244353”, isn’t it the same as P/Q modulo 998244353. But if it is the same then why is the output so weird for P/Q = 1/4, shouldn’t the output simply be 0.25 in each case? What do we have to actually compute?

5

@everule1 Please help.

6

Q^{-1}Q=QQ^{-1}=1\ mod\ p Where Q^{-1} is an integer and gcd(Q,p)=1.

7

But Q = 4 in the sample case 1 (where probability is 1/4) then how are we getting 748683265 as the output?

8

I cannot help you with the sample cases. Search modular inverse.

1 Like
9

Thanks. I respect the rules of the contest and appreciate your help.

10

I have a doubt. How is summation(ai) = n? Is n over here the number of total sushis left or the number of dishes?

11

Number of dishes.

12

@everule1 Sorry for disturbing you again. Why do we add 1? What I have studied till now about a random variable X is that E(X) i.e. expectation of X is the sum of the products of the values of X and their corresponding probabilities. How do you make the dp transition? I am getting confused.

13

You go to that state after 1 turn.
Consider the simplest case. Just one dish with one sushi.

The probability of eating that sushi is 100%. If there are 0 sushis left, it is the base case and the number of turns needed is 0. So it is
100% * 0 + 1.

1 Like
14

@everule1 Here is my code, but it doesn’t work. Can you please help me fix it?

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

    #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define rep(i,a,b) for(int i=a; i<b; i++)
    #define ll long long
    #define pb push_back
    #define inf 1e+18L
    #define MOD 1000000007
    #define MAXN 1000007

    int n;
    double dp[307][307][307];

    double solve(int a, int b, int c)
    {
        if(a<0 || b<0 || c<0) return 0;
        if(dp[a][b][c] != -1) return dp[a][b][c];
        double A=a, B=b, C=c;
        double currans = 0;
        currans = (A/n * solve(a-1,b,c)) + (B/n * solve(a+1,b-1,c)) + (C/n * solve(a,b+1,c-1)) + 1;
        currans *= n;
        currans /= (a+b+c);
        dp[a][b][c] = currans;
        return dp[a][b][c];
    }

    int main()
    {
        FastIO
        memset(dp, -1, sizeof(dp));
        cin >> n;
        vector<int> cnt(4,0);
        int x;
        rep(i,0,n)
        {
            cin >> x;
            cnt[x]++;
        }
        cout << fixed << setprecision(10) << solve(cnt[1], cnt[2], cnt[3]);
        return 0;
    }
15

memset does not work with multidimensional arrays.
dp[0][0][0]=0; base case.

1 Like
16

Then how should I initialize a 3D array?

17 
        for(int i=0;i<307;i++){
            for(int j=0;j<307;j++){
                for(int k=0;k<307;k++){
                    dp[i][j][k]=-1;
                }
            }
        }

I would recommend vectors over arrays almost always

vector<vector<vector<double>>> dp(307,vector<vector<double>>(307,vector<double>(307,-1)));

Or maybe not idk :confused:

2 Likes
18

Now my code returns inf

19

^^^

1 Like
20

Thanks a lot. It finally works. :smile: