P8491 [IOI 2022] Prisoner Challenge

### Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem. This is an interactive problem. You only need to implement the function required in the code. Your code does not need to include any additional header files, and you do not need to implement the `main` function.

A prison holds $500$ prisoners. One day, the warden gives them a chance to regain freedom. He places two bags of coins, A and B, in a room. Each bag contains some number of coins, in the range from $1$ to $N$ (inclusive). The numbers of coins in the two bags are **different**. The warden gives the prisoners a challenge: determine which bag contains fewer coins. Besides the bags, there is a whiteboard in the room. At any time, a single number is written on the whiteboard; initially it is $0$. The warden sends the prisoners into the room one by one. Each prisoner entering the room does not know how many prisoners have entered before, nor which ones. Each time a prisoner enters the room, they look at the current number on the whiteboard. After that, they must choose between bag A and bag B. Then, they **inspect** the chosen bag and learn how many coins it contains. After that, the prisoner must choose one of the following two **actions**: * Rewrite the number on the whiteboard to a non-negative integer, and leave the room. Note that they may change it to a new number or keep the current number. Then the challenge continues (unless all $500$ prisoners have already entered the room). * Identify which bag contains fewer coins. This immediately ends the challenge. A prisoner who has already entered the room will not be allowed to enter again. If some prisoner correctly identifies the bag with fewer coins, the prisoners win the challenge. If the identified bag is incorrect, or if after all $500$ prisoners have entered no one has attempted to identify the bag with fewer coins, then the prisoners lose. Before the challenge begins, the prisoners meet in the prison hall to discuss a common **strategy**, consisting of the following three steps: * They choose a non-negative integer $x$, which will be the maximum number they might write on the whiteboard. * For each number $i$ ($0 \le i \le x$), they decide which bag a prisoner should inspect if they enter the room and see $i$ on the whiteboard. * They decide what action a prisoner should take after learning the number of coins in the chosen bag. More precisely, for every whiteboard number $i$ ($0 \le i \le x$) and every observed coin count $j$ in the chosen bag ($1 \le j \le N$), they decide one of the following: - Which number between $0$ and $x$ (inclusive) should be written on the whiteboard; or - Which bag should be identified as the one with fewer coins. If they win the challenge, the warden will release them after they continue serving their sentence for $x$ more days. Your task is to propose a strategy that guarantees the prisoners win the challenge (no matter how many coins are in bags A and B). Your score depends on the value of $x$ (see the Subtasks section).

You need to implement the following function: ```go int[][] devise_strategy(int N) ``` - $N$: the maximum possible number of coins in each bag. - The function must return an array $s$, where each element is an integer array of length $N + 1$, representing your strategy. The value of $x$ is the length of $s$ minus one. For each $i$ satisfying $0 \le i \le x$, array $s_i$ describes what a prisoner should do when they enter the room and see the number $i$ on the whiteboard: 1. If the prisoner should inspect bag A, then $s_{i, 0}$ is $0$; if they should inspect bag B, then it is $1$. 2. Let $j$ be the number of coins in the chosen bag. The prisoner should take the following action: - If $s_{i, j}$ is $-1$, the prisoner should identify that bag A contains fewer coins. - If $s_{i, j}$ is $-2$, the prisoner should identify that bag B contains fewer coins. - If $s_{i, j}$ is a non-negative integer, the prisoner should write that number on the whiteboard. Note that $s_{i, j}$ can be at most $x$. - This function is called exactly once.

Consider the following call: ```go devise_strategy(3) ``` Let $v$ be the number written on the whiteboard when a prisoner enters the room. The following is one correct strategy: - If $v = 0$ (including the initial number), inspect bag A. - If it contains $1$ coin, identify that bag A contains fewer coins. - If it contains $3$ coins, identify that bag B contains fewer coins. - If it contains $2$ coins, write $1$ on the whiteboard (overwriting the previous $0$). - If $v = 1$, inspect bag B. - If it contains $1$ coin, identify that bag B contains fewer coins. - If it contains $3$ coins, identify that bag A contains fewer coins. - If it contains $2$ coins, write $0$ on the whiteboard (overwriting the previous $1$). Note that this case cannot actually happen, because then both bags would contain $2$ coins, which is not allowed. To produce the strategy above, the function should return `[[0, -1, 1, -2], [1, -2, 0, -1]]`. The returned array has length $2$, so $x$ is $2 - 1 = 1$.

### Constraints - $2 \leq N \leq 5000$. ### Subtasks 1. (5 points) $N \le 500$, and $x$ must not exceed $500$. 1. (5 points) $N \le 500$, and $x$ must not exceed $70$. 1. (90 points) $x$ must not exceed $60$. For any test case, if the array returned by `devise_strategy` is invalid, then your score for that subtask is $0$. Subtask 3 has partial scoring. Let $m$ be the maximum value of $x$ among all test cases in this subtask. Your score is computed according to the table below: | Condition | Score | | :-: | :-: | | $40 \leq m \leq 60$ | $20$ | | $26 \leq m \leq 39$ | $25 + 1.5 \times (40 − m)$ | | $m = 25$ | $50$ | | $m = 24$ | $55$ | | $m = 23$ | $62$ | | $m = 22$ | $70$ | | $m = 21$ | $80$ | | $m \leq 20$ | $90$ | ### Sample grader The sample grader reads input in the following format: * Line $1$: $N$ * Line $2 + k$ ($0 \le k$): $A_k \; B_k$ * Last line: $-1$ Except for the first and last lines, each line represents one scenario. Call the scenario on line $2 + k$ scenario $k$. In scenario $k$, bag A contains $A[k]$ coins, and bag B contains $B[k]$ coins. The sample grader first calls `devise_strategy(N)`. The value of $x$ is the length of the returned array minus one. If the sample grader detects that the array returned by `devise_strategy` does not satisfy the constraints described in the implementation details, it prints the following error message and exits: * `s is an empty array`: $s$ is an empty array (meaning the strategy is invalid). * `s[i] contains incorrect length`: there exists an index $i$ ($0 \le i \le x$) such that the length of $s_i$ is not $N + 1$. * `First element of s[i] is non-binary`: there exists an index $i$ ($0 \le i \le x$) such that $s_{i,0}$ is neither $0$ nor $1$. * `s[i][j] contains incorrect value`: there exist indices $i, j$ ($0 \le i \le x, 1 \le j \le N$) such that $s_{i, j}$ is not between $-2$ and $x$. Otherwise, the sample grader produces two outputs. First, the sample grader prints the output of your strategy in the following format: * Line $1 + k$ ($0 \le k$): the output of your strategy for scenario $k$. If your strategy leads some prisoner to identify bag A as having fewer coins, it outputs the character `A`. If your strategy leads some prisoner to identify bag B as having fewer coins, it outputs the character `B`. If no prisoner identifies which bag has fewer coins, it outputs the character `X`. Second, the sample grader writes a file `log.txt` in the current directory in the following format: * Line $1 + k$ ($0 \le k$): $w_{k,0} \; w_{k,1} \; \ldots$ The sequence on line $1 + k$ corresponds to scenario $k$ and describes the numbers written on the whiteboard. Specifically, $w[k][l]$ is the number written after the $(l + 1)$-th prisoner enters the room. ### Notes In the statement, when giving the function interface, generic type names `void`, `int`, `int64`, `int[]` (array), and `int[][]` (array of arrays) are used. In C++, the grader will use appropriate data types or implementations as shown in the tables below: | `void ` | `int` | `int64` | `int[]` | | ------- | ----- | ----------- | ------------------ | | `void ` | `int` | `long long` | `std::vector` | | `int[][]` | Length of array `a` | | ------------------------------- | ------------------- | | `std::vector` | `a.size()` | Translated by ChatGPT 5