Editorial for Square Game
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
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 (
Let's imagine a function
.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 0
s 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 1
s, the number of valid frontiers is the number of valid bar-charts. That is
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
(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
Please feel free to send me (Max) a message if you have a better complexity bound, or solution!
Comments