Atcoder DP - K Stones

#1

Why is this approach wrong:

https://pastebin.com/LjCj4diw

Submission Link :

Please give justification why the approach used in above code is giving WA

#2

@koenigsegg,
Your code fails on the 2nd Sample case. You can dry run to find out why is it happening.

#3

I know it fails , In case u havent noticed , there’s a slight difference between the video solution and the one that i have coded,

I switched the for loops

I understand why the video solution is correct but this the code that i have written is i think doing the same thing, i.e DP
Just like O(N) coin change .

Please dont tell me which test case its failing

I WANT TO KNOW WHATS WRONG WITH THIS APPROACH THAT’S PRESENT IN THE CODE LINK

#4

@koenigsegg,
Did you try dry running on paper and pen?
“I WANT TO KNOW WHATS WRONG WITH THIS APPROACH THAT’S PRESENT IN THE CODE LINK”

Hey breaking news, you can, and that too, by yourself, just pick up a pen and paper, and start simulating what your program is doing. It’s not that complex.

#5

I did but i wasnt able to
And
Sorry for the rude reply but it was mainly bcoz i didnt get much replies in the previous courses that i had taken

Can u atleast provide me with a testcase that i could dry run bcoz i did this with some testcases and it didnt show any problem

Plus heres the updated code link


Still WA but i figured sorting numbers first would be better

#6

@koenigsegg,
Your code fails on the 3rd sample test case, you can use that for dry run.

#7

Thank U :blush:
Finally a good mentor in CB

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.