Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined! ×

### CodeSherlock's blog

By CodeSherlock, history, 6 weeks ago,

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.

• 0

 » 6 weeks ago, # |   0 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 KHere 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, # ^ |   0 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.
•  » » 6 days ago, # ^ |   0 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