Editorialist: maxward

The intended difficulty of this question was around red. During the contest, nobody was able to get this question, though 1021839 was getting close. The bounds for this question are a bit odd (\(1 \leq R,C \leq 14\)). Bounds like this usually suggest either a complete-search with pruning, or dynamic programming (DP). In this case, it was the latter. The following explanation presupposes familiarity with DP. Try checking the Resources tab, or this tutorial for an introduction to DP.

Let's imagine a function \(f(frontier)\) that finds the optimal partition into squares given that we only consider a particular frontier of the input. For example,

.110
..01
.111

is a valid frontier of

0110
1101
1111

Note that . is used to denote something not in the frontier, and out frontier is on the left side. Each call to \(f(frontier)\) will decompose the \(frontier\) state into some new frontier by removing a square whose top-left corner is on \(frontier\). Also, to simplify, we can deal with 0s by only allowing squares of size 1 to use them. Also, if we pre-compute the largest valid square starting at each top-left grid cell, it will save us a lot of computation in the DP.

Unfortunately, when we have a complete 14 by 14 grid of 1s, the number of valid frontiers is the number of valid bar-charts. That is \(15^{14}\). This is a bit too big. It turns out that there is a really useful observation to speed this up.

Consider only the left-most, tie-breaking by upper-most, location on a frontier. This will always need to be the top-left corner of some square in the partition of our frontier. So, it is valid for us to only try possible squares starting there when decomposing a particular frontier. This ends of limiting the state-space of the DP a great deal. This is easy to see by coming up with some arbitrary partition of a grid into squares, and seeing how many possible frontiers on it are now impossible to reach. One can do some experimentation to find out that, for a 14 by 14 grid, there are only about 1 million states. This means the algorithm should run in time. Since this is a bit unsatisfying, can we do some analysis to figure out why this number is so small?

This analysis is actually quite difficult, and is still somewhat of an open question. In fact, the integer sequence for the number of states on 1x1, 2x2, ... , NxN grids is not known to OEIS. If you manage to find an exact closed form, tight upper bound, or fast algorithm for computing the exact sequence, let me know, and maybe we can write a paper! Having said this, there is an interesting bit of analysis we can do.

Say we cut a partition \(p\) of our grid into squares along some column's edge, and get rid of all the squares to the left of the cut, and also remove all the squares that were cut into two pieces. Now, call the set \(C(p)\) of all of the frontiers resulting from cutting \(p\) on each column. Each element of \(C(p)\) is a valid frontier our DP would reach. In fact, the only additional states it can reach involve removing some sub-range of squares touching the cut column starting from the topmost. Let's call all of these states \(S(p)\). Each element of \(S(p)\) is a valid solution to the Key Cutting problem. This means that, if we call the set of all possible partitions \(P\), \(\sum_{p\in P}{S(p)}\) is bounded by the sum of solutions to Key Cutting for various values of \(N\). This give us an upper bound on the size of the state space for our DP. This upper bound is quite loose, but should be sufficient to show that our state space is only a few million.

(Note there is some subtlety in that Key Cutting does not allow one to cut all the way through the grid, but in the case of this question we can. Also, Key Cutting insists that the grid is N by N, but we may need to consider rectangles in the above formulation. The upper bound still works out, however.)

Indeed, say that \(g(N)\) is the solution to Key Cutting on an \(N\) by \(N\) grid. It is the case that the size of our DP state space is \(O(g(N))\). The proof of this is a messy injective argument---at least when I am proving it :(. However this is easily verified by experimentation. This allows one to prove a bound of a few million on the state space for \(N=14\).

Please feel free to send me (Max) a message if you have a better complexity bound, or solution!