this problem : https://codeforces.net/contest/1369/problem/D
my code : https://codeforces.net/contest/1369/submission/158768076
dp[i][j] = maximum number of yellow nodes of tree of level i. if j = 0, it's root is not colored. otherwise it's root is colored.
well, it seems reasonable but since it returns maximum value modulo 1e9+7, we can't tell which value is actually bigger one.
but my code passed. why does it work? or is it because of weak test data?
Since there are only $$$10^6$$$ tests you can take any other accepted solution and compare all values against it
If you look at $$$dp$$$ values in your solution, you can see that either $$$dp[i][0] = dp[i][1]$$$ or $$$dp[i][0] = dp[i][1] + 4$$$. So the only way your max function goes wrong is when $$$dp[i][1] + 4$$$ overflows $$$mod$$$. And if you assume that $$$dp$$$ values modulo $$$mod$$$ are somewhat random, then the probability of that is $$$\frac{4}{mod}$$$, so the fact that it doesn't happen in $$$10^6$$$ tests is not surprising, especially considering that $$$dp[i][0] \neq dp[i][1]$$$ is true only for $$$i \equiv 0 \mod 3$$$.
The smallest $$$n$$$ where your solution gives a wrong answer is
392'874'653that's very interesting thank you so much.