Hey everyone,
I wanted to share a very general technique that I recently noticed (it's more of a strategy, I'm not sure what to call it). Maybe someone can help me clarify this and offer other problems related to it. Here are the two problems I'll be discussing: problem 1 problem 2.
In the first problem, we have a 2D problem where N = 100,000, so this means we can't do a simple O(N^2) DP. The correct solution is to sweep over springboards sorted by x coordinates in linear time and maintain a monotonic set of optimum values for different y-values (basically, we must observe that, if we have two springboards i, j, where y[i] < y[j], then we will never use springboard j if the distance we can skip over up to point i is less than that for point j). You can check out the solution for more details, but the main point I'm trying to explore is that this solution required you to break the symmetry.
What I mean by this is that, rather than doing a DP[x][y] which would be a sort of shortest-path solution, we needed to just sweep over x in linear time, and then turn our attention to dealing with the y-component. It's almost like viewing this in 2D is a red herring, since the x and y aspects aren't used in the same way. In summary, we made the problem simple in one aspect (we swept over the x-axis), and then we found a way to work around the difficulty in the second aspect with some type of optimization (a set with an invariant).
In the second problem, which is quite different, we might think about transitions from [A, B] to [C, D] which seems difficult to do and likely O(N^2) in order to find all [A, B] initial ranges from which to transition via some rope. However, we can break the symmetry again here by simplifying the [A, B] part (the state we're transitioning from).
What we can do is just make DP[i][l] store the minimum cost to cover point l using the first i ropes. By doing this, we now sweep over l in linear time, and then we turn our attention to dealing with the [C, D] part. Now, it's relatively clear that we should use a segment tree, since this corresponds to just performing a range update for each l position and the ith rope. Again, what we did was to try to make one part of this problem easy (finding a state to transition from), then figure out how to do the rest of the problem with some optimization.
Please let me know if you have ideas on when this technique can be applied (what conditions of the above problems made this possible?) and other example problems if you have seen something similar before. Let me know if I've made any mistakes. Thanks!
