← CSES Better

Count Subsets That Can Avoid Equal Neighbors

ZIO · 2024 · Zonal Informatics Olympiad · P4

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 bars

The most common color controls feasibility

For a selected subset, let m be its largest color frequency and r the total number of other balls. It can be arranged without equal neighbors when m <= r+1; the statement also treats empty and one-ball subsets as valid.

State table
Most common colorOther ballsAvailable slots
mrr+1
validm <= r+1no equal neighbors
  1. 1

    Count selected colors

    For a candidate subset, let m be the largest color frequency and r the number of all remaining balls.
  2. 2

    Reserve separators

    The r other balls create r+1 slots around them for the most frequent color.
  3. 3

    Check capacity

    A valid arrangement exists when m ≤ r+1; size-zero and size-one subsets are valid as stated.
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.