CodeSherlock's blog

By CodeSherlock, history, 4 years ago, In English

Hey Programmers, Hope you all are safe and doing well.

I am a beginner in DP, and while solving the atcoder dp series, Problem K (Stones) , I am not able to pass all sets of test cases. Also this I am not able to analyse whether its a DP or greedy problem.

Here is My Solution :.

My Logic : If we can reduce the no.of stones(k) to something where the opponent cannot make a next move, I win. Else I simply reduce the min no. (mn) of the given array from the no.of stones.

Can you please clear my confusion ? It will be helpful if you can point out the test case...where my solution goes wrong. Thank You.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, your logic is not correct because you have ignored the fact that both the players are playing optimally at every turn. So, it is not necessary at a particular k it will be optimum to always choose the minimum a[i] in A.
This problem is an extension of classic coin change problem where you have to try all the a[i] possible from set A on every state k (0<=k<=K). You can take a look at my solution. My solution to K
Here dp[i] is 1 if for this state player who starts the game wins and 0 if the other player wins. Our answer would dp[k].