← CSES Better

Break the string - INOI 2021

INOI · 2021 · Indian National Olympiad in Informatics · BREAKSTR

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 · prefix-sums · dynamic-programming

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

balanced segments

Prefix balance reveals segment imbalance

A segment is valid when the change in the zero-minus-one prefix count has magnitude at most K.

State table
PrefixBalance
p00
pip(i-1) + (+1 for 0, -1 for 1)
segment i..jp_j - p_(i-1) in [-K,K]
  1. 1

    Track prefix balance

    Map each 0/1 character to a +1/−1 balance change.
  2. 2

    Find valid boundaries

    For each endpoint, find earlier prefix balances within K of the current balance and extend the minimum-segment DP.
  3. 3

    Minimize segment count

    Mark the chosen segment starts in the output.
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.