P8494 [IOI 2022] The Rarest Insects

**This is an interactive problem.** You **do not need and must not** include the `insects.h` header file or the main function in your submitted program. However, in your program you need to declare the following three functions: ```cpp void move_inside(int i); void move_outside(int i); int press_button(); ``` For example, your program can look like this: ```cpp #include using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); int min_cardinality(int N) { // Code Here } ``` # Background

There are $N$ insects around Pak Blangkon’s house, numbered from $0$ to $N - 1$. Each insect has a **type**, represented by an integer ID from $0$ to $10^9$ (including $0$ and $10^9$). Multiple insects may have the same type. Suppose we group the insects by type. We define the cardinality of the **most common** insect type as the number of insects in the largest group. Similarly, the cardinality of the **rarest** insect type is the number of insects in the smallest group. For example, suppose there are $11$ insects with types $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$. In this case, the cardinality of the **most common** insect type is $3$, because the groups of type $9$ and type $11$ both have the largest number of insects, and each group has $3$ insects. The cardinality of the **rarest** insect type is $1$, because the groups of type $7$, type $0$, and type $100$ all have the smallest number of insects, and each group has $1$ insect. Pak Blangkon does not know the types of these insects. He has a one-button machine that can provide information about insect types. Initially, the machine is empty. When using the machine, you can perform the following three operations: 1. Put an insect into the machine. 2. Take an insect out of the machine. 3. Press the button on the machine. Each operation can be performed at most $40\;000$ times. Whenever the button is pressed, the machine reports the cardinality of the **most common** insect type currently inside the machine. Your task is to use the machine above to determine the cardinality of the **rarest** insect type among all $N$ insects around Pak Blangkon’s house. Also, in some subtasks, your score depends on the maximum number of times the machine performs a certain operation (see the Subtasks section for details).

You need to implement the following function: ```go int min_cardinality(int N) ``` - $N$: the number of insects. - This function should return the cardinality of the **rarest** insect type among all $N$ insects around Pak Blangkon’s house. - This function is called exactly once. This function may call the following functions: ```go void move_inside(int i) ``` - $i$: the ID of the insect to be put into the machine. The value of $i$ is between $0$ and $N - 1$ (including $0$ and $N - 1$). - If the insect is already inside the machine, the call will not change the set of insects inside the machine. However, the call is still counted toward the number of such operations. - This function can be called at most $40\;000$ times. ```go void move_outside(int i) ``` - $i$: the ID of the insect to be taken out of the machine. The value of $i$ is between $0$ and $N - 1$ (including $0$ and $N - 1$). - If the insect is already outside the machine, the call will not change the set of insects inside the machine. However, the call is still counted toward the number of such operations. - This function can be called at most $40\;000$ times. ```go int press_button() ``` - This function returns the cardinality of the **most common** insect type inside the machine. - This function can be called at most $40\;000$ times. - The grader is **not adaptive**. That is, the types of all $N$ insects are fixed before `min_cardinality` is called.

Consider a scenario where there are $6$ insects with types $[5, 8, 9, 5, 9, 9]$. The function `min_cardinality` is called as follows: ```go min_cardinality(6) ``` This function calls `move_inside`, `move_outside`, and `press_button` in the following order. | Function call | Return value | Insects in the machine | Insect types in the machine | | :-------------------: | :----------: | :-----------------------------: | :--------------------------: | | | $\\{\\}$ | $[\ ]$ | | | `move_inside(0)` | | $\\{0\\}$ | $[5]$ | | `press_button()` | $1$ | $\\{0\\}$ | $[5]$ | | `move_inside(1)` | | $\\{0, 1\\}$ | $[5, 8]$ | | `press_button()` | $1$ | $\\{0, 1\\}$ | $[5, 8]$ | | `move_inside(3)` | | $\\{0, 1, 3\\}$ | $[5, 8, 5]$ | | `press_button()` | $2$ | $\\{0, 1, 3\\}$ | $[5, 8, 5]$ | | `move_inside(2)` | | $\\{0, 1, 2, 3\\}$ | $[5, 8, 9, 5]$ | | `move_inside(4)` | | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$ | | `move_inside(5)` | | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$ | | `press_button()` | $3$ | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$ | | `move_inside(5)` | | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$ | | `press_button()` | $3$ | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$ | | `move_outside(5)` | | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$ | | `press_button()` | $2$ | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$ | At this point, there is enough information to conclude that the cardinality of the rarest insect type is $1$. Therefore, the function `min_cardinality` should return $1$. In this example, `move_inside` is called $7$ times, `move_outside` is called $1$ time, and `press_button` is called $6$ times.

### Constraints - $2 \le N \le 2000$. ### Subtasks 1. (10 points) $N \le 200$. 2. (15 points) $N \le 1000$. 3. (75 points) no additional constraints. If, on some test case, the number of calls to `move_inside`, `move_outside`, or `press_button` does not satisfy the constraints given in “Implementation details”, or the return value of `min_cardinality` is incorrect, then your score for that subtask is $0$. Let $q$ be the **maximum** of the following three values: the number of calls to `move_inside`, the number of calls to `move_outside`, and the number of calls to `press_button`. In Subtask 3, you may receive partial score. Let $m$ be the maximum value of $\frac{q}{N}$ over all test cases in this subtask. Your score for this subtask will be calculated according to the following table: | Condition | Score | | :---------------: | :---------------------------------------------------: | | $20 \lt m$ | $0$ (CMS reports “`Output isn’t correct`”) | | $6 \lt m \le 20$ | $\frac{225}{m - 2}$ | | $3 \lt m \le 6$ | $81 - \frac{2}{3} m^2$ | | $m \le 3$ | $75$ | ### Example grader Let $T$ be an integer array of length $N$, where $T[i]$ is the type of insect with ID $i$. The example grader reads input in the following format: - Line $1$: $N$. - Line $2$: $T[0] \; T[1] \; \ldots \; T[N - 1]$. If the example grader detects illegal behavior, it will output `Protocol Violation: `, where `` is one of the following: - `invalid parameter`: in a call to `move_inside` or `move_outside`, the value of parameter $i$ is not in the range from $0$ to $N - 1$ (including $0$ and $N - 1$). - `too many calls`: the number of calls to **at least one** of `move_inside`, `move_outside`, and `press_button` exceeds $40\;000$. Otherwise, the example grader outputs in the following format: - Line $1$: the return value of `min_cardinality`. - Line $2$: $q$. ### Notes In the statement, the function interfaces use general type names `void`, `bool`, `int`, `int[]` (array), and `union(bool, int[])`. In C++, the grader will use appropriate data types or implementations, as shown in the following tables: | `void ` | `bool` | `int` | `int[]` | | ------- | ------ | ------| ------------------ | | `void ` | `bool` | `int` | `std::vector` | | `union(bool, int[])` | Length of array `a` | | -------------------------------------- | ------------------- | | `std::variant` | `a.size()` | In C++, `std::variant` is defined in the `` header. A function with return type `std::variant` can return either a `bool` or a `std::vector`. The following sample code shows three functions that return a `std::variant`, and they all work correctly: ```cpp std::variant foo(int N) { return N % 2 == 0; } std::variant goo(int N) { return std::vector(N, 0); } std::variant hoo(int N) { if (N % 2 == 0) { return false; } return std::vector(N, 0); } ``` Translated by ChatGPT 5