Insects
Step 1: Count distinct types Insert insects one by one. After each insertion, if press\_button() > 1, remove the insect (it is a duplicate). The number of insects remaining in the machine equals the number of distinct...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
There are $N$ insects, each of some unknown type. A machine supports three operations:
$\texttt{move\_inside}(i)$: place insect $i$ in the machine.
$\texttt{move\_outside}(i)$: remove insect $i$ from the machine.
$\texttt{press\_button}()$: return the maximum frequency among all types currently in the machine.
Determine the cardinality of the rarest insect type.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Step 1: Count distinct types
Insert insects one by one. After each insertion, if $\texttt{press\_button}() > 1$, remove the insect (it is a duplicate). The number of insects remaining in the machine equals the number of distinct types $d$. Then clear the machine.
This step uses at most $2N$ operations ($N$ insertions + at most $N$ removals + $N$ button presses + $d$ removals to clear).
Step 2: Binary search on the answer
Binary search on $k \in [1, \lfloor N/d \rfloor]$, testing whether the minimum type frequency is at most $k$.
Check for a given $k$.
Insert insects one by one, rejecting any insect whose insertion would cause $\texttt{press\_button}() > k$. After processing all $N$ insects, the machine contains exactly $\min(k, \mathrm{count}(t))$ insects of each type $t$. The total inside is $T = \sum_t \min(k, \mathrm{count}(t))$.
If $T < d \cdot k$, then some type has fewer than $k$ insects, so the minimum frequency is $\le k$. Otherwise every type has count $\ge k$ and we set $\mathrm{lo} = k + 1$.
Each check uses $O(N)$ operations. The binary search has $O(\log(N/d))$ iterations.
Total operation count
$O(N \log(N/d))$ operations overall. For the IOI limits ($N \le 2000$), this is at most roughly $2000 \times 11 \approx 22000$, well within the allowed budget.
Complexity
Operations: $O(N \log(N/d))$ where $d$ is the number of distinct types. Each binary-search iteration uses $O(N)$ move/press calls.
Space: $O(N)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader functions
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
// Step 1: Find number of distinct types
vector<bool> inside(N, false);
int num_types = 0;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
} else {
inside[i] = true;
num_types++;
}
}
// Clear machine
for (int i = 0; i < N; i++)
if (inside[i]) {
move_outside(i);
inside[i] = false;
}
// Step 2: Binary search on answer k
int lo = 1, hi = N / num_types;
while (lo < hi) {
int mid = (lo + hi) / 2;
// Check: is minimum frequency <= mid?
// Add insects allowing at most 'mid' per type
int total_inside = 0;
vector<bool> in_machine(N, false);
for (int i = 0; i < N; i++) {
move_inside(i);
total_inside++;
if (press_button() > mid) {
move_outside(i);
total_inside--;
} else {
in_machine[i] = true;
}
}
// If total_inside < num_types * mid, some type has < mid insects
bool has_rare = (total_inside < (long long)num_types * mid);
// Clean up
for (int i = 0; i < N; i++)
if (in_machine[i]) {
move_outside(i);
in_machine[i] = false;
}
if (has_rare) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.