← CSES Better

Substring Importance - ZCO 2018

ZCO · 2018 · Zonal Computing Olympiad · STRIMPOR

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

strings · sliding-window · prefix-sums

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

substring window

Charge each good substring to the windows it touches

Good substrings start at X, end at Z, and have length divisible by three; a K-window’s importance counts those intersecting it.

substring [l,r]
0–3
window starts [l-K+1,r]
1–4
  1. 1

    Find good substrings

    Enumerate good-substring endpoints using the X/Z conditions and length residue.
  2. 2

    Map affected windows

    Convert each good interval into the range of K-window starts it intersects.
  3. 3

    Minimize importance

    Use a difference array to find the minimum total importance.
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.