PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Consider the following restatement of the problem:
N+1 walls have been erected, each one meter apart. A window of height S has been cut into each wall at a specific height. The i’th window is has a height of Ci higher than the previous window. Take a rubber string and attach it to the bottom of the window in the first wall, pass it through all of the remaining windows, and attach it to the bottom of the window in the last wall. Compute the sum of the squares of the slopes of the rubber string between each wall and the next.
The problem is equivalent because the specific energy function used is irrelevant, so long as it is convex. If we use sqrt(K2+1) instead of K2 as the energy cost of producing K units of frosting, the optimal production schedule will remain unchanged. Using the former leads to the geometry problem above.
The problem can now be solved in linear time, by using an algorithm similar to a convex hull algorithm. We imagine 2 pieces of rubber, both initially attached to the bottom of the first window. We then, one window at a time, pull both pieces of rubber through the current window and attach them to the next. One piece of rubber always attaches to the bottom of the next window, the other always to the top. We keep a list, for each rubber string, of the window points it remains in contact with. We also keep track of the last point at which both pieces of rubber are in contact. Once a rubber string loses contact with a window, it will never again come in contact with that part of the window again. On each list we perform O(N) insertions, and O(N) deletions, so the overall runtime is O(N).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.