G: Cuboid Slicing Game

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

This problem uses the Sprague-Grundy 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.