Hello, everybody. The first round of OpenCup Season XV just ended. Let's discuss the problems.

# | User | Rating |
---|---|---|

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 206 |

2 | Monogon | 196 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 185 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

7 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 167 |

Hello, everybody. The first round of OpenCup Season XV just ended. Let's discuss the problems.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2020 05:29:00 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How about G?

Play randomly until each connected component becomes small (<= 10 possible moves). After that, compute grundy function of each component in O(2^n), and xor values for all components. With high probability, result will be non-zero.

One of the solutions involves only trivial observations, but a fair bit of coding.

When we have a game position, it can be partitioned into independent regions where moves can be made. Two possible moves are immediately dependent when they share at least one cell.

We will recognize three classes of regions based on two boolean outcomes.

Is it possible to invalidate all possible moves in the region by a single move?

Is it possible to make a move such that there remains at least one possible move from the region?

An example of (1) but not (2) is a square of 2 × 2 or 3 × 3 cells. Such a region (a

Type Iregion) requires exactly one move to disappear.An example of both (1) and (2) is a rectangle of 2 × 4 or 3 × 4 cells. In such a region (a

Type IIregion), we have a choice: it requires either one or two moves to disappear.An example of (2) but not (1) is any large region. Such a region (a

Type IIIregion) requires at least two moves to disappear.Our first goal will be to have only

Type IandType IIregions left on the board. We can try to achieve a perfect grid ofType IIregions (4 × 2 rectangles) by trying to place every square of the pattern shown on the left picture. Of course, Felix will mess things up, and the resulting board will look more like the right picture (result of a 16 × 20 game up to this point).There are 8

Type Iregions, 8Type IIregions and 2Type IIIregions on the right picture.In the second part of the game, we eliminate all

Type IIIregions by detecting them and making random moves in these regions.In the endgame, we have only

XType Iregions andYType IIregions.If

XandYare even, the player who makes a move loses if both play optimal: the winning strategy for the other player is to keep them both even after their turn. If we find Sophia in such position, we can make a random move and hope Felix does not follow the winning strategy.If

Xis even andYis odd, we make by eliminating oneType IIregion, so that both are even after our turn.If

Xis odd andYis even, we remove oneType Iregion just the same.Finally, if

XandYare both odd, we move in aType IIregion such that it leaves a newType Iregion, effectively making the new values ofXandYeven:Xincreases by one andYdecreases by one.The more

Type IIregions we had at the beginning, the more are our chances to eventually avoid the situation whenXandYare even and Sophia has to make a move. If we avoid that at least once before the game is over, we follow the above simple strategy to win.The above strategy is a simple case of calculating and using Grundy numbers for regions, as in winger's solution: they are 1 for

Type Iregions and 2 forType IIregions. Still, this solution requires only knowledge of elementary game theory and invention of simple symmetric strategies.When checked several times against the judges' test cases with different random seeds, it won at least 293 out of 300 games.

My solution with region cutoff of <= 16 wins ~99.85% of games on 16x16 field and nearly 100% on 25x25, but unfortunately is too slow to pass the TL.

I don't have a login. How can I get the problems? Will the contest be published on gym?

when did it start