Codeforces 1163B1. Cat Party (Easy Edition) and 1163B2 Cat Party (Hard Edition)

Problem link

Problem link


We can iterate over all streaks and check for each streak if we can remove one day so that each color has the same number of cats.

There are 4 cases where we can remove a day from the streak to satisfy the condition:

There is only one color in this streak.
All appeared colors in this streak have the occurrence of 1 (i.e. every color has exactly 1 cat with that color).
Every color has the same occurrence of cats, except for exactly one color which has the occurrence of 1.
Every color has the same occurrence of cats, except for exactly one color which has the occurrence exactly 1 more than any other color.
All of these four conditions can be checked using counting techniques.

Complexity: O(n).

A solution in c++