Help with Atcoder Educational DP Contest

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

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
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.
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.
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;
        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;
    return ans[a][b][c];

Thank you so much :smile:

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?

@everule1 Please help.

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

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

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

1 Like

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

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

Number of dishes.

@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.

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

@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()
        memset(dp, -1, sizeof(dp));
        cin >> n;
        vector<int> cnt(4,0);
        int x;
            cin >> x;
        cout << fixed << setprecision(10) << solve(cnt[1], cnt[2], cnt[3]);
        return 0;

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

1 Like

Then how should I initialize a 3D array?

        for(int i=0;i<307;i++){
            for(int j=0;j<307;j++){
                for(int k=0;k<307;k++){

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:


Now my code returns inf


1 Like

Thanks a lot. It finally works. :smile: