Overview

Under the constraint that “the adjusted stock prices must be strictly increasing each day,” we want to minimize the cost \(\sum |H_i-H'_i|\) of changing each day’s value to an integer. Through transformation, this becomes “L1 (absolute value) isotonic regression to make a sequence monotonically non-decreasing.”

Analysis

1. Transformation to handle “strictly increasing” more easily

The condition \(H'_1 < H'_2 < \cdots < H'_N\) means that each consecutive difference is at least 1. By defining: - \(A_i = H'_i - i\) - \(X_i = H_i - i\)

we get:

• \(H'_i < H'_{i+1}\) \(\Leftrightarrow H'_i - i \le H'_{i+1} - (i+1)\) \(\Leftrightarrow A_i \le A_{i+1}\)

In other words, “strictly increasing” is converted to “\(A_i\) is monotonically non-decreasing.”

Furthermore, the cost becomes: [ |H_i - H’_i| = |(H_i-i) - (H’_i-i)| = |X_i - Ai| ] so the objective is: [ \min \sum{i=1}^{N} |X_i - A_i| \quad \text{s.t. } A_1 \le A_2 \le \cdots \le A_N,\; A_i \in \mathbb{Z} ]

• Since \(X_i\) are integers, the optimal \(A_i\) can also be achieved as integers (by using medians as described below), so the integer constraint is naturally satisfied.

2. Why a naive approach is difficult

For example, if we consider DP, the range of \(A_i\) values is up to \(10^9\) in scale, which is impractical. Also, if we naively repeat “fixing parts that violate monotonicity,” it’s entangled with global optimality (how much to fix and where), and efficiency cannot be guaranteed.

3. Solution direction: L1 monotone regression uses “block medians”

The optimal solution for making a sequence monotonically non-decreasing partitions the indices into several contiguous intervals (blocks), where: - All values within each block are the same: \(A_i = c\) - That \(c\) is the median of the \(X_i\) values within the block

This minimizes \(\sum |X_i - c|\) (a fundamental property of absolute value sum minimization).

Therefore, the approach is: - Maintain the median for each block - If adjacent blocks violate monotonicity (left median > right median), merge them

This is a classic technique known as PAVA (Pool Adjacent Violators Algorithm).

Algorithm

Overall (PAVA: median version)

1. Compute \(X_i = H_i - i\).
2. Add each \(X_i\) as a single-element block, processing from left to right.
3. After each addition, for the last two blocks:
   • If “left block’s median > right block’s median,” this is a monotonicity violation, so merge the two blocks
   • Repeat until no violations remain
4. For each final block, add up the cost (sum of absolute deviations from the median).

Block internals: efficiently managing the median and cost

Within each block, we dynamically handle: - Adding elements - Retrieving the median - Computing \(\sum |x - \text{median}|\) (cost)

To maintain the median efficiently, we use two heaps: - low: the set of elements ≤ median (equivalent to a max-heap; in code, a min-heap with negated signs) - high: the set of elements > median (min-heap)

We always maintain: - len(low) == len(high) or len(low) == len(high)+1

This way, the median is always the maximum of low (its top element).

Furthermore, by maintaining sum_low and sum_high, for median \(m\): [ \sum{x \in low} (m-x) + \sum{x \in high} (x-m) ] can be computed in \(O(1)\) as: [ m\cdot |low| - sum_low + sum_high - m\cdot |high| ]

Speeding up merges (smaller into larger)

When merging two blocks, we add all elements from one block into the other. By always absorbing the smaller block into the larger one (union by size), each element is moved as the “smaller side” at most \(O(\log N)\) times, making the overall process fast.

Complexity

• Time complexity: \(O(N \log N)\) (Each element is moved only about \(O(\log N)\) times amortized through heap operations)
• Space complexity: \(O(N)\) (All elements are stored in heaps)

Implementation Notes

• The key insight is transforming “strictly increasing” to “non-decreasing” via \(X_i=H_i-i\).

• Since we use L1 (absolute value), the block representative value is the median, not the mean (getting this wrong leads to WA).

• Two heaps + partial sums efficiently manage the “median” and “cost.”

• Block merges must always go small → large to prevent worst-case complexity blowup.

  Source Code

import sys
import heapq

class Block:
    __slots__ = ("low", "high", "sum_low", "sum_high")

    def __init__(self):
        self.low = []   # max-heap via negatives
        self.high = []  # min-heap
        self.sum_low = 0
        self.sum_high = 0

    def size(self):
        return len(self.low) + len(self.high)

    def median(self):
        return -self.low[0]

    def add(self, x: int):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
            self.sum_low += x
        else:
            heapq.heappush(self.high, x)
            self.sum_high += x

        if len(self.low) < len(self.high):
            y = heapq.heappop(self.high)
            self.sum_high -= y
            heapq.heappush(self.low, -y)
            self.sum_low += y
        elif len(self.low) > len(self.high) + 1:
            y = -heapq.heappop(self.low)
            self.sum_low -= y
            heapq.heappush(self.high, y)
            self.sum_high += y

    def merge(self, other: "Block"):
        for v in other.low:
            self.add(-v)
        for v in other.high:
            self.add(v)

    def cost(self):
        m = -self.low[0]
        return m * len(self.low) - self.sum_low + self.sum_high - m * len(self.high)


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    H = data[1:]

    blocks = []
    for i, h in enumerate(H, start=1):
        x = h - i
        b = Block()
        b.add(x)
        blocks.append(b)

        while len(blocks) >= 2 and blocks[-2].median() > blocks[-1].median():
            b2 = blocks.pop()
            b1 = blocks.pop()
            if b1.size() < b2.size():
                b1, b2 = b2, b1
            b1.merge(b2)
            blocks.append(b1)

    ans = sum(b.cost() for b in blocks)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.