> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/g-cuboid-slicing-game.md).

# G: Cuboid Slicing Game

https\://open.kattis.com/contests/s82cve/problems/cuboidslicinggame

This problem uses the [Sprague-Grundy Theorem](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem). This solution assumes the reader is familiar with this method; if not, check out the Wikipedia page and stay tuned for an upcoming ICPC workshop on it!

Let $$N$$ be the maximum length of a cuboid in a dimension. Then the Sprague-Grundy recurrence can be naively implemented using dynamic programming in $$O(N^6)$$. Since $$N=30$$ in the problem and we are allowed 3 seconds to run, this is just within the range of possibility. The outline of the algorithm to calculate the Sprague-Grundy numbers (nimbers) is

```
dp = 31 x 31 x 31 array of all 0s
for x,y,z from 1,1,1 to 30,30,30:
    mex = 30 * 30 * 30 boolean array initialized to false
    for i,j,k from 0,0,0 to x,y,z:
         # cut the cuboid by removing the sections for which i <= x <= i+1, j <= y <= j+1, etc
         nimber_after_move = dp[i][j][k] ^ dp[x-1-i][j][k] ^ dp[i][y-1-j][k] ^ ... ^ dp[x-1-i][y-1-j][z-1-k]
         mex[nimber_after_move] = true
    ans = first index in mex corresponding to false
    dp[x][y][z] = ans
```

There are a couple of optimizations one can try in case this is too slow (but naive should pass in C++): we can use the symmetry of the problem and enforce $$x \geq y \geq z$$ for all values computed in the DP, and then set all permutations of $$(x,y,z)$$ once we have the answer, dividing the runtime by 6. We can also change the inner loops to iterate only up to $$i \leq \frac{x}{2}$$, etc, dividing the runtime by 8.