Module 16 · The STL in Competitive Programming: Which Container for Which Problem
Coordinate Compression and a Budget for Your Algorithm
ProReading
Amara's boxes use labels from several old catalogues. Some labels are tiny, others are huge. She needs one counter per label actually present, not one counter for every possible number. Their relative order matters; the gaps between their numbers do not.
Checking what this lesson needs for you…
What is inside Coordinate Compression and a Budget for Your Algorithm
- Compression changes names, not order
- Sort a copy
- Unique returns a boundary, erase shrinks
- Lower_bound finds a rank or an insertion position
- Choose offline compression or online order
- Input size is a rejection tool
- A flowchart for choosing the pattern
- Measure equivalent work
- Preserve the facts the statement uses