#P2594. Coin Flipping Game

    ID: 15863 Type: Default 1000ms 256MiB

Coin Flipping Game

Coin Flipping Game

There is an n × m grid of coins. Two players, Dongdong and Xixi, play the following game. On each turn, a player may choose a connected block of coins and flip all coins in that block. However, the move is only valid if there exists a coin in the chosen block (called the pivot) such that:

  • Every other coin in the block is located in the upper‐left direction of this coin (that is, either directly above or directly to its left, or both),
  • This coin is flipped from tail (back side) to head (front side).

Two players take turns making moves, with Dongdong moving first. A player who is unable to make a valid move loses. Assuming both players play optimally, determine whether Dongdong has a winning strategy.

Observation: Note that a valid move always involves flipping at least one coin that is currently tail (the pivot coin) to head. A trivial move is to select a single coin that is tail; in this move the coin is flipped to head. More generally, any connected block chosen must lie entirely in a sub‐matrix whose bottom‐right coin (the pivot) is tail before the move, and all other coins in that block lie in its upper-left region.

This game is impartial, and its outcome can be determined by computing the nim‐sum over all coins – where the coin at position \((i,j)\) (with 0‐based indices) is assigned a Grundy value of \(i \oplus j\). Dongdong can force a win if and only if the overall nim‐sum over every coin that is initially tail is nonzero.

Important: The initial configuration of coins is such that all coins are tails. Thus, the nim‐sum is defined as

[ G = \bigoplus_{i=0}^{n-1}\bigoplus_{j=0}^{m-1} (i \oplus j), ]

Dongdong wins if \(G \neq 0\), and loses otherwise.

inputFormat

The first line contains two integers n and m --- the dimensions of the coin grid.

It is guaranteed that the grid contains exactly n × m coins, and initially all coins are tails.

outputFormat

Output a single string: Yes if Dongdong has a winning strategy, or No otherwise.

sample

1 1
No