May someone please explain me what we are asked to find in this question?
Question Link:
You have to find the number to reach the given value. You have to calculate for both stressful and stress less. I did a dp solution for it .
Yes, you have to do 2 separate DP equations, one being for nth Catalan number and the other of the form
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Catalan nos? Whats those ? i did it also using paths
May you please elaborate the question ,I am have having problem with the language part.
Let dp[N][N] be our dp array. (N is maximum possible score i.e. 2000)
dp[x][y] stores the number of ways you can reach the score x:y stress-free.
It can be seen that dp[1][0] is 1.
Also, dp[x][x]=0 for all x from 0 to N, because its not a stress-free condition. (Your score needs to be strictly greater than your opponent’s score)
Now consider the score x:y.
2 possible scores from which you can reach this score are:
(x-1):y
and x:(y-1)
Hence, dp[x][y] = dp[x-1][y] + dp[x][y-1]
Now, the definition of stressful victory x:y can be interpreted as :
Your opponent need to reach score y:(y-1) in stress-free way for him.
So, the answer is simply dp[y][y-1]
Hope this helps
There is official editorial on FB. Can you ask what is not clear in it?