Any idea how to solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2338 ?
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Any idea how to solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2338 ?
Name |
---|
Just ignore P and solve the problem with an ordinary minimax DP. Then add 2 * P to the answer.
Very short sketch of proof:
If a player in a winning position passes, he'll obviously lose the game. If the losing player passes, he can let the winning player end the game in a smaller amount of moves (or the winning player will pass the move back), so passing only makes sense when no such shortcut exists (for example, when any loser's move will lead to an immediate victory of his opponent).