← CSES Better

Lower Towers Until the Sequence Has No Valley

ZIO · 2025 · Zonal Informatics Olympiad · P3

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

arrays · dynamic-programming · optimization

The organizer’s problem statement is available at the official source link.

sequence shape

A valid profile rises to a peak, then falls

A special tower sequence has no indices i < j < k with H[i] > H[j] and H[j] < H[k]. Each operation lowers one positive height by one; minimize operations, or return -1 if impossible.

nondecreasing prefixpeak / plateaunonincreasing suffixlower heights only
  1. 1

    Recognize the forbidden valley

    A valley exists when an earlier height is above a middle height and a later height is above that middle height.
  2. 2

    Only lower towers

    Each operation decreases one positive H[i] by exactly one; heights cannot be increased.
  3. 3

    Minimize operations

    Find the fewest decrements that remove every forbidden valley, or report -1 if no valid sequence is reachable.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.