Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Reject a segment before descending into it: The Palindrome Cuts.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Palindrome partitioning matches the clues
- 2Keep this true after every move: path partitions exactly the processed prefix and every segment in it is palindromic
- 3Reach the result within O(n times 2^n) output-sensitive time
Rules and pressure
- Target cost: O(n times 2^n) output-sensitive time
- State rule: path partitions exactly the processed prefix and every segment in it is palindromic
New words in this mission
Open a term for a plain-language explanation.partition or shard+
One slice of a larger dataset or workload. Splitting work raises capacity, but cross-slice operations become harder.
Lesson 1 of 3
Live algorithm trace
Palindrome partitioning
Complete execution1 of 5
a
start
a
b
a
a
b
Try every prefix segment beginning at index zero.
1
search(start)2
if start reaches end: record path3
try every segment ending4
if segment is not palindrome: skip5
append segment and search after it6
undotext = aabstart = 0path = []
Truth to preserve / Cost target
Truth to preserve
path partitions exactly the processed prefix and every segment in it is palindromic
Cost target
O(n times 2^n) output-sensitive time
At each start position, try every ending position. Recurse only when the chosen segment is a palindrome, so no invalid partial partition grows deeper.
Your call · What should guide every step of this algorithm?