Here's what that problem was about. You are given a sequence of 10 million numbers. To be more precise, you're given a way to generate it: start with a given number X0, then repeatedly compute Xi = ((Xi-1 xor A) + B) mod 250, where A and B are also given. You're looking to find the radius of each element in the sequence, defined as the largest number k such that the previous k elements and the next k elements are strictly less than the given element, and return the sum of the radii for all elements. The catch is, you have to do it while using at most 1 MB of memory - so you can only store about 1% of the sequence in memory at the same time!
The said problem looked somewhat standard on the surface. You're given a 10x10 chessboard with some cells removed. You need to find any connected set of cells on it that has exactly W white cells and exactly B black cells, or report that there isn't any. One could readily imagine a dynamic programming solution that goes row by row, remembering how many white cells we've taken so far, how many black cells we've taken so far, which cells are taken amount the last jagged row, and which connected components they form. However, such DP has too many states (roughly 10000 states of the jagged row with connected components, times 100 steps, times 50 white cells, times 50 black cells equals 2.5 billion, and although not all those states are reachable, a big fraction of them are) and will never run in time. So how does one solve this problem?
The key idea in solving this problem is that resolving horizontal conflicts and resolving vertical conflicts can be done independently. It's not clear from the first sight, since a boomerang is "connected", and thus when rotating it we're affecting both its horizontal and its vertical conflicts. However, we can notice that rotating a boomerang by 90 degrees causes one of the two things: its horizontal hand starts pointing in the other direction, or its vertical hand starts pointing in the other direction. Moreover, no matter which position the boomerang is in, we can always achieve both those outcomes by a 90 degree rotation! In other words, one rotation can change horizontal or vertical situation, but not both, and that's why horizontal and vertical conflicts are resolved independently.
Having noticed this, the problem breaks into even smaller pieces: it's somewhat obvious now that each row's and each column's conflicts can also be resolved independently. So instead of one monolithic 100x100 2D problem, now we have 200 separate 1x100 1D problems. Each 1D problem is solved with a somewhat classical O(N2) dynamic programming approach which finds what's the largest number of conflicts we can resolve using A moves in the first B cells, leaving the last cell pointing in a given direction. Each subproblem's output is the largest number of conflicts that can be resolved using 1, 2, ..., 100 moves. Now we need to combine those outputs into the overall solution, which is once again a standard dynamic programming question: what's the largest number of conflicts we can resolve using A moves in the first B subproblems. The overall running time of this solution is O(N3).
Thanks for reading, and check back next week!
0 komentar:
Post a Comment