← CSES Better

Break Up

ZCO · 2015 · Zonal Computing Olympiad · ZCO15001

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

dynamic-programming · palindromes · partitioning

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

palindrome partition

Cut the sequence only at palindrome boundaries

Every prefix can end with a final palindromic piece; the DP chooses the fewest pieces.

substring [l,r]palindrome testextend partition boundary
  1. 1

    Find palindromic ranges

    Precompute or expand around centers to identify palindromic intervals.
  2. 2

    Try each final piece

    For each prefix endpoint, try a final palindrome beginning at every valid earlier cut.
  3. 3

    Minimize piece count

    Store the minimum number of pieces for each prefix.
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.