Skip to content
CCC Python Course

Counting and combinatorics

Stage
6
Module
M6.9
Lessons
1

In this module

  • Count instead of enumerating to solve combinatorial problems in linear time.
  • Apply complementary counting to avoid hard cases.
  • Use binomial coefficients and products of counts.
  • Maintain counts with a sliding pointer for dynamic constraints.
  • Solve circular and geometric counting problems.

Before this module

M4.3Prefix sums (1D, 2D, prefix/suffix max)M4.15Circular arraysM3.6Frequency arrays and counting

Lessons

  1. 1Counting and combinatorics

Practice

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

  1. 2022 S4
    Good Triplets (opens on WMOJ in a new tab) WMOJ

    Count triplets in a sequence that satisfy a specific ordering condition.

  2. 2017 J5
    Nailed It! (opens on DMOJ in a new tab) DMOJ(same problem as 2017 S3)

    Count pairs of items whose properties combine to meet a target.

    Why DMOJ: An older junior counting problem that still makes good practice for this module.