General Problem Solving Technique

Правка en2, от johnkim3104, 2020-03-31 03:56:01

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский johnkim3104 2020-03-31 04:06:19 0 (published)
en3 Английский johnkim3104 2020-03-31 04:05:30 2617
en2 Английский johnkim3104 2020-03-31 03:56:01 859
en1 Английский johnkim3104 2020-03-31 03:50:37 372 Initial revision (saved to drafts)