A row of mountains is photographed, and any contiguous crop [l, r] has an "asymmetric value": pair up mountains that are equidistant from the center, sum the absolute height differences. The task asks for more than one crop's answer — for every length k from 1 to N, the minimum asymmetric value among all crops of that length. CCC 2023 Senior Problem 2, Symmetric Mountains, looks like it requires enumerating a massive number of intervals. What it really tests is whether you can see that every interval has exactly one center, and eliminate the repeated work. The whole algorithm is one idea: fix a center, expand outward.

Companion video: Watch Berny's 2023 S2 Symmetric Mountains walkthrough on Xiaohongshu

Where This Fits in the CCC DSA Map

• Level: Senior S2
• Pattern: Center Expansion (two pointers moving outward)
• Prerequisite: arrays and indexing, loops, abs(), Big-O basics (Python basics: input, operators, and conditions, Python list fundamentals)
• What this teaches: turn "every interval has exactly one center" into an incremental recurrence (each step adds exactly one pair), then aggregate minima by length — recognize and remove repeated work
• Where it appears again: palindrome checking and longest palindromic substring, the two-pointer / sliding-window topic (planned), CPW-012 Searching for Strings (planned)

What to Study Next

• Related CP Weekly problems: CCC 2017 S1 Sum Game for prefix sums and interval sums, CCC 2020 S3 Searching for Strings for sliding windows (coming soon), and CCC 2016 J5/S2 Tandem Bicycle for sorting with two pointers (coming soon)
• Related Python / C++ foundations: Python Basics: Input, Operators, and Conditions, Python Lists: append() vs +
• Related DSA roadmap article: Prefix Sum and Sliding Window Patterns (planned)

What the Problem Is Asking

The input gives N mountain heights h₁…hₙ. A crop is a contiguous interval [l, r]; its asymmetric value is the sum of absolute differences of mirrored positions: |h_l − h_r| + |h_{l+1} − h_{r−1}| + …

Output N integers: the k-th one is the minimum asymmetric value among all crops of length k.

Official sample: N=7, heights [3 1 4 1 5 9 2], answer 0 2 0 5 2 10 10.

Read the original problem in the CEMC 2023 CCC Senior problem set.

Bounds: 1 ≤ N ≤ 5000, 0 ≤ h_i ≤ 10^5, with layered subtasks: N≤300 yields to brute force; the middle subtask has non-decreasing heights (where prefix sums can split the absolute values); full marks have no extra constraints — and center expansion handles all of them.

Where Beginners Often Get Stuck

• Sorting first: sorting makes absolute values easy to split, but it reorders the mountains — the photograph changes and so does every interval. Sorting is forbidden here.
• Brute force by length: enumerating every start for every length and recomputing each asymmetry from scratch is O(N³) — about 10¹¹ operations at N=5000, hopeless.
• Forgetting even centers: odd-length crops are centered on a mountain; even-length crops are centered on the gap between two mountains. Writing only one kind misses half the intervals.
• Initializing the answer array to 0: each length asks for a minimum, so the initial value must be infinity before taking min.
• Prefix-sum splitting for general data: splitting |a−b| requires knowing the order; full-mark data has no monotonicity, so that trick dies on subtask 3.

Core Algorithm Idea

Expand the definition of a crop [l, r]:

asym(l, r) = |h_l − h_r| + |h_{l+1} − h_{r−1}| + |h_{l+2} − h_{r−2}| + …

Except for the outermost pair, everything inside the brackets is exactly asym(l+1, r−1). That gives an incremental recurrence:

asym(l, r) = |h_l − h_r| + asym(l+1, r−1)

Empty intervals and single mountains cost 0. So if intervals are generated by "fix a center, expand outward", each expansion step only adds the newly exposed pair — the inner value is already in the accumulator, and no pair is ever computed twice.

Every interval [l, r] has exactly one center: an index c for odd lengths, a gap (c, c+1) for even lengths. Enumerating all centers (N position centers plus N−1 gap centers) and expanding outward covers all N(N+1)/2 intervals.

State / Data Structure Design

• ans[k]: the minimum asymmetric value among crops of length k (k = 1..N), initialized to infinity.
• Transient expansion state: left, right, cost — the current interval's endpoints and its accumulated asymmetry.

Each expansion produces one interval and updates ans[r − l + 1] with cost. The intervals themselves never need to be stored.

Algorithm Steps

1. Read N and the height array h.
2. Initialize ans[1..N] to infinity.
3. For each position center c (0..N−1): start from l=r=c with cost=0; each step adds |h[l] − h[r]|, updates ans[r−l+1] with cost, then moves l left and r right until out of bounds.
4. For each gap center c (0..N−2): start from l=c, r=c+1, and expand the same way.
5. Print ans[1..N], space-separated.

Sample Check with the Official Data

Verifying each length against the sample [3 1 4 1 5 9 2] (0-based indices):

Watch center 2 (the mountain of height 4) grow the crop [3 1 4 1 5]: (4,4) adds 0; expanding to (1,3) adds |1−1|=0; expanding to (0,4) adds |3−5|=2 — three steps, one new pair each. The official explanation lists the three length-5 crops as costing 2, 9, and 10; the minimum 2 matches the output.

Python Solution

n = int(input())
mountains = list(map(int, input().split()))
answer = [10**18] * (n + 1)

for center in range(n):
    cost = 0
    left = center
    right = center
    while left >= 0 and right < n:
        cost += abs(mountains[left] - mountains[right])
        length = right - left + 1
        answer[length] = min(answer[length], cost)
        left -= 1
        right += 1

for center in range(n - 1):
    cost = 0
    left = center
    right = center + 1
    while left >= 0 and right < n:
        cost += abs(mountains[left] - mountains[right])
        length = right - left + 1
        answer[length] = min(answer[length], cost)
        left -= 1
        right += 1

print(*answer[1:])

This matches the curriculum notebook (p2003, Session 3) line for line — same variable names students see in class: mountains, center, cost, answer. Note that cost grows monotonically during one expansion, but lengths do not share answers — you cannot prune an expansion early just because the cost already exceeds some length's record.

C++ Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> mountains(n);
    for (int& height : mountains) {
        cin >> height;
    }

    const long long INF = (1LL << 60);
    vector<long long> answer(n + 1, INF);

    for (int center = 0; center < n; center++) {
        long long cost = 0;
        int left = center;
        int right = center;
        while (left >= 0 && right < n) {
            cost += abs(mountains[left] - mountains[right]);
            int length = right - left + 1;
            answer[length] = min(answer[length], cost);
            left--;
            right++;
        }
    }

    for (int center = 0; center + 1 < n; center++) {
        long long cost = 0;
        int left = center;
        int right = center + 1;
        while (left >= 0 && right < n) {
            cost += abs(mountains[left] - mountains[right]);
            int length = right - left + 1;
            answer[length] = min(answer[length], cost);
            left--;
            right++;
        }
    }

    for (int length = 1; length <= n; length++) {
        if (length > 1) {
            cout << ' ';
        }
        cout << answer[length];
    }
    cout << '\n';
    return 0;
}

Same as the curriculum reference; long long guards against overflow (worst case about ⌊N/2⌋×10⁵); answer starts from a (1LL << 60)-scale infinity; the two loops are perfectly symmetric except for the initial (left, right).

Why the Algorithm Is Correct

• Every interval is visited exactly once: any interval [l, r] has a unique center (a position or a gap), its expansion from that center passes through [l, r], and intervals generated from different centers never overlap.
• Each updated cost equals the true asym(l, r): induction on the expansion radius. Radius 0 (or the gap initial state) gives length 1 (or 2), where cost = 0 plus the first pair — correct. Assuming the inner [l+1, r−1] value is correct, expanding to [l, r] adds exactly the outermost pair |h_l − h_r|, and the recurrence asym(l, r) = |h_l − h_r| + asym(l+1, r−1) makes it correct.
• ans[k] ends as the minimum over all crops of length k: every crop of length k is computed during its center's expansion and participates in the min — no omissions, no duplicates.

Therefore the output is exactly the requested minimum asymmetric value for every length.

Complexity Analysis

• Time O(N²): N(N+1)/2 intervals with O(1) amortized work each — about 12,502,500 constant-time updates at N=5000.
• Space O(N): the answer array, plus the input.
• Measured on this machine (Apple Silicon, CPython 3): the curriculum Python version takes about 17s on the N=5000 random case — it will not fit a typical 5-second limit; C++ runs it in about 0.03s with no pressure. Bottom line: use the Python version to learn the algorithm (some judges relax limits for Python or allow PyPy), and submit C++ in a real contest. Python tuning is constant-factor only (inline compare instead of min(), buffered input — together roughly the edge of 5s); the algorithm itself is already optimal in its complexity class.

Common Mistakes

1. Sorting first — reordering changes every interval and guarantees a wrong answer.
2. Forgetting gap centers — odd lengths come out right while even lengths stay at their initial value.
3. Initializing ans to 0 — the min updates never take effect and the output is all zeros.
4. Recomputing the full asymmetry inside each expansion — degrades to O(N³) and times out at full marks.
5. Prefix-sum splitting on non-monotonic data — splitting |a−b| needs a known order, which full-mark data does not have.
6. Output format — N integers on one line, space-separated; trailing spaces or missing lengths are format errors.

Review Questions

1. Why does every interval have exactly one center? Which lengths' optima are missed if gap centers are skipped?
2. Why is sorting illegal in this problem? Explain it in terms of how an "interval" is defined.
3. The recurrence asym(l, r) = |h_l − h_r| + asym(l+1, r−1) maps to a length-ordered DP — how is it written, and what do the three rolling rows store?
4. Why does the non-decreasing subtask allow O(1) asymmetry queries via prefix sums, and what exactly breaks on full-mark data?
5. If you must submit in Python under a tight limit, what constant-factor optimizations remain, and roughly how much do they save?