Skip to content
CCC Python Course

Compressed data and values you cannot expand

Stage
4
Module
M4.14
Lessons
1

In this module

  • Identify when a value is too large to store or iterate over directly.
  • Use coordinate compression to map large values to a smaller range.
  • Understand when expansion is possible and when it is not.
  • Apply compression to solve problems where naive expansion would time out.

Before this module

M3.4String processing II: tokenizing with stateM3.8Clock and calendar arithmetic, modulo and periodicity

Lessons

  1. 1Coordinate compression

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2015 J4
    Wait Time (opens on DMOJ in a new tab) DMOJ

    Track events over a wide time range using a dictionary keyed by time, not a huge array.

    Why DMOJ: An older problem where a dictionary keyed by time stands in for full coordinate compression.

  2. 2022 J5
    Square Pool (opens on WMOJ in a new tab) WMOJ

    Narrow a huge coordinate plane down to a small set of candidate points worth checking.