Doubt on a facebook hackercup question Round 1

May someone please explain me what we are asked to find in this question?
Question Link:

link text

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]

1 Like

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:
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 :slight_smile:

There is official editorial on FB. Can you ask what is not clear in it?