Any idea how to solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2338 ?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/23/2024 11:40:26 (k1).
Desktop version, switch to mobile version.
Supported by
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).