← CSES Better

Count Student Subsets with Exactly K Badge Types

ZIO · 2023 · Zonal Informatics Olympiad · P2

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

combinatorics · subsets · frequency-counting

The organizer’s problem statement is available at the official source link.

frequency groups

Choose exactly K represented badge groups

Students are distinct positions; selected students must contain exactly K different badge numbers.

State table
Badge groupChoose positionsContribution
group inone / nonempty subset2^n_i - 1
exactly K groupscombinecount
  1. 1

    Group by badge

    Group student positions by badge value.
  2. 2

    Choose K groups

    Choose exactly K badge groups to represent.
  3. 3

    Count student subsets

    For each chosen group, select a nonempty subset of its positions and combine the counts.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.