Skip to content
CCC Python Course

Memoisation over floor-division blocks

Stage
6
Module
M6.13
Lessons
1

In this module

  • Recognize when a sum over floor division takes only O(sqrt(n)) distinct values.
  • Jump between block boundaries instead of scanning every divisor.
  • Apply floor-division blocks to divisor-counting sums.

Before this module

M4.11Memoization and introductory dynamic programmingM4.6Number theory I

Lessons

  1. 1Memoisation over floor-division blocks

Practice

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

  1. 2020 S1
    Surmising a Sprinter's Speed (opens on DMOJ in a new tab) DMOJ

    Work with a sprinter's recorded checkpoint times to find a consistent picture of the race.

    Why DMOJ: An older problem whose numeric structure still makes good practice for this module.

  2. 2021 S1
    Crazy Fencing (opens on WMOJ in a new tab) WMOJ

    Cut a fence into pieces while respecting a length-based rule.