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
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
May you please elaborate the question ,I am have having problem with the language part.
There is official editorial on FB. Can you ask what is not clear in it?