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

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];
}
```

Thank you so much

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?

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.

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.

@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;
}
```

memset does not work with multidimensional arrays.

`dp[0][0][0]=0;`

base case.

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++){
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

Now my code returns inf

^^^

Thanks a lot. It finally works.