Game - 2 (Editorial)

Editorial

Game Interpretation

Each tetrahedron shows a number from \{1,2,3,4\} on its top face. A valid move is to flip a tetrahedron to a strictly larger face. Thus, from a given face value $x$, the possible moves are:

[ 1 2,3,4  2 3,4  3 4  4 no move ]

This is a classic impartial combinatorial game. Each tetrahedron is an independent subgame, and the overall position is the XOR of their Grundy values.

Grundy Values

For each face value $v$, compute its Grundy number $G(v)$:

[

G(4) = 0 (no moves)

G(3) = mex{G(4)} = mex{0} = 1

G(2) = mex{G(3), G(4)} = mex{1,0} = 2

G(1) = mex{G(2), G(3), G(4)} = mex{2,1,0} = 3

]

Thus:

[ G(1)=3, G(2)=2, G(3)=1, G(4)=0. ]

Winning Condition

Let $S$ be the string of visible faces. The position is winning for the first player iff:

[ G( S_1 ) G( S_2 ) G( S_N ) 0. ]

If the XOR is zero, the position is losing.

Final Rule

[ Print 1 if the XOR is nonzero, otherwise print 0. ]

C++ Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    int xor_sum = 0;
    for (char c : s) {
        if (c == '1') xor_sum ^= 3;
        else if (c == '2') xor_sum ^= 2;
        else if (c == '3') xor_sum ^= 1;
    }
    
    cout << (xor_sum != 0 ? 1 : 0);
    return 0;
}