Solution of Cuboid Slicing Game (IDI Open 2018)

2 months ago
0 comment

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 and its SG function value :

  • if and only if is a must-lose situation. Otherwise,
  • If can be divided into sub-situations , then , where is the XOR operator
  • If can be converted to situation or or ... or by only one operation, then , where function is defined as the smallest non-negative integer that does not appear in . For example,

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 .

If any of is equal to , 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 becomes several smaller cuboids: . 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 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;
}