Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Point every visited node toward its root: The Compressed Trails.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Full path compression matches the clues
- 2Keep this true after every move: parent links stay inside the same component and every find returns its representative
- 3Reach the result within O(n alpha(n)) amortized for all finds
Rules and pressure
- Target cost: O(n alpha(n)) amortized for all finds
- State rule: parent links stay inside the same component and every find returns its representative
Lesson 1 of 3
Live algorithm trace
Full path compression
Complete execution1 of 6
0
0
1
2
3
4
x
Node 5 begins at the end of a six-node parent chain.
1
find(x)2
if parent[x] != x3
parent[x] = find(parent[x])4
return parent[x]5
find every node6
return compressed parentsquery = 5path = 5 to 4 to 3 to 2 to 1 to 0
Truth to preserve / Cost target
Truth to preserve
parent links stay inside the same component and every find returns its representative
Cost target
O(n alpha(n)) amortized for all finds
Find follows parent links until it reaches a self-parent root. While unwinding, redirect every visited node straight to that root so future operations traverse a much shorter path.
Your call · What should guide every step of this algorithm?