Codeforces k-Tree

codeforces
dynamic-programming
wa

#1

Problem: http://codeforces.com/problemset/problem/431/C

Solution: http://www.hastebin.com/qugasuduji.vala

I am unable to figure out why the above code (same logic as editorial) is leading to WA in test case 7. Could someone please help me identify where I am going wrong? I am guessing it’s something to do with the mod, but not too sure.


#2

You need to change the ‘int’ dp[104][2] to ‘long long’ dp[104][2]. This is because the temporary result stored in dp*[k] is of data type int which overflows and wraps around to give negative results and hence wrong answer.

Accepted solution


#3

Thanks @devilhector, I was making this mistake in another problem as well. Finally understood why the WA.