PROBLEM LINK:
Author: Sergey Kulik
Tester: Istvan Nagy and Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Backtracking, search pruning, offline computation, simulated annealing, randomized algorithms
PROBLEM:
Given a rectangular palace (a grid) subdivided into disjoint rectangular grids, place the maximum number of guards that don’t see each other. Guards see each other if they are in the same room and they are within one queen’s move or knight’s move away.
QUICK EXPLANATION:
Given a rectangular room M\times N, you obviously can’t place more than \min(M,N) guards. However, it is not guaranteed that you can place \min(M,N) guards.
Precompute at least one answer for all square rooms N \times N, 10 \le N \le 100. You can either do this in code or offline (hint: randomization helps). You’ll see that you can always place N guards 
Therefore, given any M\times N grid with \min(M,N) \ge 10, we can always place \min(M,N) guards (by taking any \min(M,N) \times \min(M,N) subgrid).
Now, brute-force all grids \min(M,N) \le 10 = \max(M,N). You’ll find that you can always place \min(M,N) guards Note this also holds for \min(M,N) \le 10 < \max(M,N) because we can ignore the extra rows/columns.
Finally, assume \max(M,N) < 10. Now there are occasions where you cannot place \min(M,N) guards. In this case, just brute-force all remaining grids to compute the maximum number of guards you can place (along with a possible configuration).
Finally, just fill in each rectangular room in the input with one of these precomputed solutions
EXPLANATION:
It’s immediately obvious that the rooms are independent of each other, and we can try to solve each rectangular room separately. So let’s just solve the following problem:
We have a rectangular room of dimensions M\times N. Place as many guards as possible.
A “guard”, which is a combination of a queen and a knight, is what’s actually called a “superqueen” in chess literature. One of the most common introductory problems given is called the “queens problem”, where you’re supposed to place N queens on an N\times N chessboard. So we can actually call the “superqueens problem”, which is harder than the N-queens problem (in the sense that every superqueens solution is also a valid queens solution). Let’s assume the grid is a square first. Obviously, you can place at most N superqueens in such a grid.
The obvious solution of course is to use backtracking to brute-force search for a solution, i.e. find any way to place N superqueens in an N\times N boards. However, if you do this in the usual way, you might find that brute force starts to get slow for N around 40, so we must find a much faster solution. However, looking at the results of the partially done brute force, we can probably guess the following:
There is no solution for 1 < N < 10, but there’s always to be a solution for N \ge 10.
Assuming this is true, what are the implications of this in the case of a rectangular grid?
- Given an M\times N grid, you cannot place more than \min(M,N) superqueens, but you can’t necessarily be able to place exactly \min(M,N) superqueens.
- If \min(M,N) \ge 10, then there’s a way to place \min(M,N) superqueens: take any \min(M,N)\times \min(M,N) subgrid and place \min(M,N) superqueens there, and ignore the other cells! There is always a way to place them according to the assumption above.
- If \min(M,N) < 10 but \max(M,N) \ge 10, then there is also a way to place \min(M,N) superqueens: Take any solution for the 10\times 10 grid, extend the grid so that it has \max(M,N) columns instead of 10 (i.e. that it is 10\times \max(M,N) in dimensions), and remove all but the first \min(M,N) rows. This is guaranteed to be a valid placement of \min(M,N) superqueens since we started with a 10\times 10 solution which contains a superqueen in each row.
- If \min(M,N) < 10 and \max(M,N) < 10, then there are only at most 81 such grids, and we can easily brute-force them
This is great, because we’ve handled all the cases! The only thing now is to discuss how to compute a solution for every N\times N grid, for N \ge 10.
Techniques to compute the solution
We discovered that finding just any solution using the normal backtracking approach works too slow. One way to optimize that brute-force search is to randomize it. What this means is that at any step, instead of trying out the next viable column, we try the columns in a shuffled order. This is in the hopes that the “bad choices” we make early on in our backtracking (which seems to happen often with normal backtracking) can be avoided, and that the number of solutions to any N\times N grid is high enough that the probability of a random placement of superqueens in the first few rows to have a valid extension to an optimal solution is really high. Doing this amazingly speeds up the solution by a huge factor: Just by doing this, the brute-forcer can now compute solutions for N up to 70 or 80 in a few seconds!
However, you might notice that the randomized version sometimes gets stuck at certain N s. In these cases, we can improve the solution by stopping the search after a fixed amount of steps, say 10^5, and simply starting again. The idea is that the brute-forcer might have been stuck by making a few bad mistakes early on, so the best way to proceed is to simply start from scratch. Using this improvement, the solution for all N up to 100 now takes around 6 seconds, using the editorialists’ pypy brute-forcer!
But we still have a problem: the time limit is 3 seconds, which is too little for our brute-forcer! Well, there are two ways to fix this:
- We can compute all the answers offline and just hardcode our solutions in our submission! If you do it right, you can store the answers in just under 23Kb of code, which passes our source code limit!
- Another way is to find a good seed for every N, where a “good seed” is simply a seed to our random generator which computes a solution relatively fast. We can do this computation offline, and then hardcode these seeds into our submission and compute the answers for these N s using these seeds. Since we only store a hundred numbers in code, this shouldn’t take much more than 2Kb of space. Amazingly, it’s really easy to find seeds for each N that is optimal in terms of speed, i.e. every choice the random generator makes yields a correct solution, so there’s no need to backtrack! One thing to take care of is compiler differences: Implementations of random generator libraries might differ across compilers/interpreters, so it’s advisable to create your own random generator for the task. It’s easy to write one though.
Time Complexity:
O(N^2) after preprocessing/backtracking
AUTHOR’S AND TESTER’S SOLUTIONS:
Will be uploaded