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. 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 the second problem, which is