CodeSherlock's blog

By CodeSherlock, history, 6 weeks 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

»
6 weeks 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].

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation. Actually I knew that something is wrong in optimal decision making but was not getting the right example to prove my mistake. Thankfully I got it...

    Now I can try out the DP solution.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I'm also relatively new to dp and wrote a code to same problem and my approach was almost similar to yours but instead I have used a 2-D dp array with states being : 1st — No. of stones and 2nd — index upto which array is considered. But it is not working in all the test cases could you help me by pointing out my mistake. Here is my code. Thanks