← Back to posts

A good game theory problem

2 min read
Competitive Programming

https://atcoder.jp/contests/arc208/tasks/arc208_a

image-20251126201053422

Abstracting the Problem

The problems constraint is still too big, I'm thinking of how to reduce the constraints and the requirements of the game, such as: what's the strategy, which stone to be picked, etc.

Observation 1

Initially, all OR should be $2^X - 1$, if there's an off bit, just ignore that one. Because we can't make a number that has a bit turned on on previously off ones.

Observation 2

When there's only 1 on bit, the strategy is as simple as checking the parity. Solving for 2 bits must be able to solve for all $X$ bits.

Bits between each position is not independent, making the xor of state between different position doesn't work(?)

11
11 (winning state)
can be
11
10 (winning state)
or can be
11
01 (winning state)
or
11
00 (losing state)

2 pile is a winning state if one is a subset of another

11010110
00101001
110
001
011

101
001
011

111
001
001 (Losing state)

111
001
010 (Winning state)

101
010
010 (Losing state)

Ok the solution was just checking whether the xor and the or is the same. Wtf. It can be proven that for every losing state all of them are odds. And from every other state it can reach the losing state.

Comments