Solution of Cuboid Slicing Game (IDI Open 2018)

Problem link: Click here.

Solution

It is clear that the question is a game theory question.

For game theory, we have a powerful tool: Sprague–Grundy function.

Basically, for a game situation $A$ and its SG function value $g(A)$:

• $g(A) = 0$ if and only if $A$ is a must-lose situation. Otherwise, $g(A) \in \mathbb{Z}^{ * }$
• If $A$ can be divided into $n$ sub-situations $x_1, x_2, \dots, x_n$, then $g(A) = g(x_1) \oplus g(x_2) \oplus \dots \oplus g(x_n)$, where $\oplus$ is the XOR operator
• If $A$ can be converted to situation $B_1$ or $B_2$ or ... or $B_n$ by only one operation, then $g(A) = mex\{g(B_1), g(B_2), \dots, g(B_n)\}$, where function $mex(S)$ is defined as the smallest non-negative integer that does not appear in $S$. For example, $mex\{0, 1, 2, 4\} = 3, mex\{\} = 0$

In Cuboid Slicing Game, if current situation has several cuboids, then we can divide it into many sub-games so that each game only has one cuboid. After we get the SG function values of these sub-games, we can get the SG value of current situation by simply XOR those values together.

For a single-cuboid-game, we can represent it by a tuple $(x, y, z)$.

If any of $x, y, z$ is equal to $0$, then it is clear that this is a must-lose situation (because you have no cuboid to cut), so its SG value is 0.

Otherwise, consider a way to cut the cuboid. Suppose after the cutting, cuboid $(x, y, z)$ becomes several smaller cuboids: $(x_1, y_1, z_1), (x_2, y_2, z_2), \dots$. This means, you make a decision, and you turn the current single-cuboid-situation to a new situation which contains several cuboids. Then you can just divide the new situation into some single-cuboid-situation.

There probably are many ways to cut the cuboid, each way turns current situation to a new situation. Calculate the SG values for all new situations, and use $mex$ function to get the SG value of current situation.

Of course, for efficiency, we need to use dynamic programming to calculate these values.

Code:

#include <bits/stdc++.h>

#define NS 35

using namespace std;

string name[2] = { "RUBEN", "ALBERT" };

int f[NS][NS][NS];

bool book[NS][NS][NS];

int mex(vector<int> &s)
{
    int res = 0;
    static bool h[NS * NS * NS];
    for (vector<int>::iterator i = s.begin(); i != s.end(); i++) h[*i] = 1;
    while (h[res]) res += 1;
    for (vector<int>::iterator i = s.begin(); i != s.end(); i++) h[*i] = 0;
    return res;
}

int dfs(int x, int y, int z)
{
    if (x < 1 || y < 1 || z < 1) return 0;
    int &F = f[x][y][z];
    if (book[x][y][z]) return F;
    book[x][y][z] = 1;
    vector<int> s;
    for (int i = 0; i <= x / 2; i += 1)
        for (int j = 0; j <= y / 2; j += 1)
            for (int k = 0; k <= z / 2; k += 1)
            {
                int g = dfs(i, j, k);
                g ^= dfs(i, j, z - k - 1);
                g ^= dfs(i, y - j - 1, k);
                g ^= dfs(i, y - j - 1, z - k - 1);
                g ^= dfs(x - i - 1, j, k);
                g ^= dfs(x - i - 1, j, z - k - 1);
                g ^= dfs(x - i - 1, y - j - 1, k);
                g ^= dfs(x - i - 1, y - j - 1, z - k - 1);
                s.push_back(g);
            }
    return F = mex(s);
}

int main(int argc, char const* argv[])
{
    string s;
    cin >> s;
    int fplayer = (s == name[1]), n, x, y, z, sg = 0;
    cin >> n;
    while (n--) cin >> x >> y >> z, sg ^= dfs(x, y, z);
    cout << name[fplayer ^ (sg == 0)] << endl;
    return 0;
}