Overview

Given \(N\) days of stock price data, this problem asks for the minimum modification cost (sum of absolute values) to make the prices strictly increasing. This can be efficiently solved using Slope Trick applied to “isotonic regression under the L1 norm.”

Analysis

Converting Strictly Increasing to Non-Decreasing

We are required to find corrected stock prices \(H'_i\) that are strictly increasing (\(H'_1 < H'_2 < \cdots < H'_N\)). By defining \(A_i = H_i - i\) and \(B_i = H'_i - i\), we get:

\[H'_1 < H'_2 < \cdots < H'_N \iff B_1 \leq B_2 \leq \cdots \leq B_N\]

This holds because under integer constraints, a difference of at least \(1\) becomes a difference of at least \(0\) after subtracting \(i\). The cost remains the same:

\[\sum_{i=1}^{N} |H_i - H'_i| = \sum_{i=1}^{N} |A_i - B_i|\]

This reduces the problem to “minimize \(\sum |A_i - B_i|\) subject to \(B\) being a non-decreasing sequence” — an L1 norm isotonic regression problem.

Issues with a Naive Approach

If we use DP to enumerate all possible values of \(B_i\), the value range can be up to \(10^9\), which is far too slow. Even with coordinate compression giving \(O(N^2)\), it would TLE for \(N \leq 2 \times 10^5\).

Solution via Slope Trick

In L1 norm minimization, the cost function becomes a piecewise linear convex function. The technique known as Slope Trick manages the “breakpoints (points where the slope changes)” of this piecewise linear convex function using a priority queue (heap), enabling efficient updates.

Algorithm

L1 isotonic regression to a non-decreasing sequence can be solved with the following greedy + heap algorithm:

1. Prepare a max-heap and set total_cost = 0.
2. Process each \(A_i\) (\(= H_i - (i+1)\), using 1-indexed offset) in order.
3. For each \(A_i\):
   • Push \(A_i\) onto the heap.
   • Check the maximum value \(\text{top}\) of the heap.
   • If \(\text{top} > A_i\), the non-decreasing constraint is violated, so:
     • Pop \(\text{top}\) and push \(A_i\) once more (conceptually updating the median).
     • Add \(\text{top} - A_i\) to the cost.
4. The final total_cost is the answer.

Intuitive explanation: The heap stores “median-like representative points of the optimal solution so far.” When a new value is smaller than the current representative, an adjustment is needed to maintain the non-decreasing constraint, and the adjustment cost is \(\text{top} - A_i\). The heap update (pop and push) corresponds to revising the optimal representative value of a past interval downward.

Concrete Example

For \(N = 3\), \(H = [5, 3, 4]\):

• \(A = [5 - 1, 3 - 2, 4 - 3] = [4, 1, 1]\)
• \(i=0\): push 4 → heap = [4], top = 4, \(4 \leq 4\) so do nothing. cost = 0
• \(i=1\): push 1 → heap = [4, 1], top = 4, \(4 > 1\) so pop 4, push 1 → heap = [1, 1], cost += 3 → cost = 3
• \(i=2\): push 1 → heap = [1, 1, 1], top = 1, \(1 \leq 1\) so do nothing. cost = 3

The answer is 3. Indeed, setting \(H' = [2, 3, 4]\) (\(B = [1, 1, 1]\)) gives \(|5-2|+|3-3|+|4-4| = 3\), achieving a cost of 3.

Complexity

• Time complexity: \(O(N \log N)\) (heap operations are \(O(\log N)\) per element)
• Space complexity: \(O(N)\) (the heap size is at most \(N\))

Implementation Notes

• Python’s heapq is a min-heap, so we store values with negated signs to use it as a max-heap.

• The offset used for converting strictly increasing to non-decreasing is \(i+1\) (1-indexed). When iterating with 0-indexed \(i\), use \(A_i = H_i - (i+1)\).

• Since \(H_i\) and \(A_i\) can be large, care is needed to ensure the total cost fits within 64-bit integers. However, in Python, integer overflow does not occur.

  Source Code

import heapq

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    H = [int(input_data[i+1]) for i in range(N)]
    
    # Transform to non-decreasing problem by subtracting index
    # Strictly increasing H'[i] means H'[i] - i is non-decreasing
    # Let A[i] = H[i] - i, then we want to find non-decreasing B[i] minimizing sum |A[i] - B[i]|
    
    A = [H[i] - (i + 1) for i in range(N)]  # using 1-indexed offset so H'_1 < H'_2 < ... < H'_N becomes B non-decreasing
    
    # Slope trick for isotonic regression (L1 norm)
    # We maintain the piecewise linear convex function f represented by a max-heap of slopes
    # For non-decreasing sequence minimizing L1 cost:
    # We use a max-heap. For each new element a:
    #   - push a into heap
    #   - if top of heap > a, we pop the top, push a again (merge operation), and add (top - a) to cost
    
    max_heap = []  # stored as negatives for max-heap behavior
    total_cost = 0
    
    for a in A:
        heapq.heappush(max_heap, -a)
        top = -max_heap[0]
        if top > a:
            heapq.heappop(max_heap)
            heapq.heappush(max_heap, -a)
            total_cost += top - a
    
    print(total_cost)

solve()

---

This editorial was generated by claude4.6opus-thinking.