P9372 [APIO2023] Alice, Bob and Circuit

This is a communication problem and cannot be judged for now.

The Cyberland Circuit Society has a total of $n$ members. Each member has a favorite number and a unique name that is different from everyone else’s name. (It is not guaranteed that everyone’s favorite number is different.) In total, these members have sent $m$ letters to each other. Each letter contains a sender and a recipient. The content of the letter is exactly the sender’s favorite number. After all letters are sent, each member will compute the sum of the numbers contained in the letters they received (the senders’ favorite numbers), take this sum modulo $65536$ ($2^{16}$), and use the result as their final stored number. Your task is to determine the final stored number for each person. However, things are not as simple as they look. Alice, Bob, and Circuit plan to solve this problem in a slightly more complex way. Specifically: - Alice knows all information about the $n$ members (their names and their favorite numbers), but Alice does not know anything about the $m$ letters. She needs to send Circuit a binary string of length at most $10^5$. - Bob knows all information about the $m$ letters (the names of the sender and recipient of each letter), but Bob does not know anything about the $n$ members. He needs to send Circuit a binary string of length at most $10^5$. - Circuit is a circuit that can receive the binary strings sent by Alice and Bob, and then produce a binary string of $16n$ bits as its output. However, its computing power is limited: Circuit can only perform basic logical operations (such as AND, OR, NOT). Below, we describe the working mechanism of the circuit in detail. #### Circuit operation details A gate is the basic component of the circuit. A gate has either zero or two boolean signals as input, and one boolean signal as output. There are two types of gates in the circuit: input gates and computation gates. - Input gates have no input boolean signals, and are used to represent one bit of the binary strings input by Alice and Bob. - There are a total of $l_A + l_B$ input gates, numbered from $0$ to $l_A + l_B - 1$ in order. Here $l_A, l_B$ are the lengths of the binary strings provided by Alice and Bob, respectively. - For any $0\leq i < l_A$, the output of gate $i$ is the $i$-th bit of the binary string provided by Alice. - For any $0\leq i < l_B$, the output of gate $i + l_A$ is the $i$-th bit of the binary string provided by Bob. - Computation gates have two inputs and are used for computation. - The numbering of computation gates starts from $l_A + l_B$. - For each computation gate, you need to provide the indices of two related gates, which represent the boolean signal inputs of this computation gate; and a number $p$ ($0\leq p\leq 15$), which represents the type of this computation gate. - To avoid circular dependencies, the two indices used as inputs must be smaller than the index of this computation gate. - Suppose the outputs of the two related gates are $x_0, x_1$, then the output of this computation gate is: $$ f(p,x_0,x_1)=\left \lfloor \frac{p}{2^{x_0+2x_1}} \right \rfloor \bmod 2 $$ Here are some examples that may be useful: | $x_0$ | $x_1$ | $x_0$ AND $x_1$（$f(8,x_0,x_1)$） | $x_0$ OR $x_1$（$f(14,x_0,x_1)$） | $x_0$ XOR $x_1$（$f(6,x_0,x_1)$） | NOT $x_0$（$f(5,x_0,x_1)$） | |:---:|:---:|:---:|:---:|:---:|:---:| | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | | $0$ | $1$ | $0$ | $1$ | $1$ | $1$ | | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | ### Implementation details Please note: - All array indices start from $0$. For example, if `a` is an array of length `n`, then `a[0]` through `a[n-1]` are valid elements of the array. Accessing an index outside this range may cause an out-of-bounds error. - All strings end with the null character `\0`. You should implement the following procedures: #### Alice ```cpp int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]); ``` | Type | Value | Length | Meaning | Constraints | |:---:|:---:|:---:|:---:|:---:| | Input | n | $1$ | $n$ | $0\leq n\leq 700$ | | Input | names | $n$ | The name of each member. | All member names are distinct. Names contain only lowercase English letters and have length at most $4$. | | Input | numbers | $n$ | Each member’s favorite number. | Favorite numbers are integers from $0$ to $65535$. | | Output | outputs_alice | $l_A$ | The binary string sent to Circuit. | | | Output | (return value) | $1$ | $l_A$ | You must ensure $l_A$ does not exceed $10^5$. Also, when $n$ is the same, $l_A$ must be the same. | #### Bob ```cpp int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]); ``` | Type | Value | Length | Meaning | Constraints | |:---:|:---:|:---:|:---:|:---:| | Input | m | $1$ | $m$ | $0\leq m\leq 1000$ | | Input | senders | $m$ | The sender name of each letter. | All names must appear in Alice’s input. | | Input | recipients | $m$ | The recipient name of each letter. | All names must appear in Alice’s input. | | Output | outputs_bob | $l_B$ | The binary string sent to Circuit. | | | Output | (return value) | $1$ | $l_B$ | You must ensure $l_B$ does not exceed $10^5$. Also, when $m$ is the same, $l_B$ must be the same. | #### Circuit To make Circuit’s computation process the same as a normal circuit, you cannot directly access the binary strings that Alice and Bob send to Circuit. You only need to know the lengths of these two strings, and output the circuit structure based on the lengths. | Type | Value | Length | Meaning | Constraints | |:---:|:---:|:---:|:---:|:---:| | Input | la | $1$ | $l_A$ | | | Input | lb | $1$ | $l_B$ | | | Output | operations | $l$ | The operation type executed by each gate in the circuit. | Each element is an integer from $0$ to $15$. | | Output | operands | $l$ | The indices of the gates providing boolean signal inputs for each computation gate. | Input gate indices are guaranteed to be smaller than the current computation gate index. | | Output | outputs_circuit | $n$ | The indices of the circuit’s output gates. | `outputs_circuit[i][j]` represents the $j$-th bit (counting from the least significant bit) of the final stored number of member $i$. Members are indexed in the order of Alice’s input. | | Output | (return value) | $1$ | $l$, representing the number of gates used in the circuit (including input gates). | You must ensure $l\leq 2\times 10^7$. | Although you may modify the information of gates with indices smaller than $l_A+l_B$ in the `operations` and `operands` arrays, the interactive library will ignore such modifications. ### Example Consider the following sample call sequence: ```cpp alice(3, {"alic", "bob", "circ"}, {10000, 20000, 30000}, outputs_alice); bob(5, {"alic", "bob", "bob", "circ", "circ"}, {"circ", "circ", "alic", "circ", "circ"}, outputs_bob); ``` This sample represents the following scenario: - Alice knows that there are $3$ members. The member named `alic` has favorite number $10000$, and so on. A possible output of `alice()` is: - The return value of `alice()` is $2$, meaning $l_A=2$. - In `alice()`, set `outputs_alice[0] = 1`, `outputs_alice[1] = 0`, meaning the binary string returned by Alice is $10$. - Bob knows that there are $5$ letters. The first letter is sent from `alic` and received by `circ`, and so on. A possible output of `bob()` is: - The return value of `bob()` is $3$, meaning $l_B=3$. - In `bob()`, set `outputs_bob[0] = 1`, `outputs_bob[1] = 1`, `outputs_bob[2] = 0`, meaning the binary string returned by Bob is $110$. Based on the previous outputs of `alice()` and `bob()`, the interactive library will call: ```cpp circuit(2, 3, operations, operands, outputs_circuit); ``` One correct output of `circuit()` is: - The return value of `circuit()` is $7$, meaning we added two computation gates, labeled $5$ and $6$. - In `circuit()`, set the `operations`, `operands`, and `outputs_circuit` arrays as follows: - `operations = {-1, -1, -1, -1, -1, 8, 14}`. Here we use `-1` to represent ignored information from input gates. - `operands = {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {0, 4}, {2，5}}`. - `outputs_circuit = {{5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 5, 5, 6, 5}, ...} `. The array is long; see `abc.cpp` in the attachment for the full array. According to the output of `circuit()`, Circuit’s computation process is: - Add a computation gate of type $8$, numbered $5$, whose inputs come from input gate $0$ and input gate $4$. The output of gate $0$ is the $0$-th bit of Alice’s string, i.e. $1$; the output of gate $4$ is the $2$-nd bit of Bob’s string, i.e. $0$. So the output of computation gate $5$ is $f(8,0,1)=0 \operatorname{AND} 1=0$. - Add a computation gate of type $14$, numbered $6$, whose inputs come from input gate $2$ and computation gate $5$. The output of gate $2$ is the $0$-th bit of Bob’s string, i.e. $1$; the output of gate $5$ is $0$. So the output of computation gate $6$ is $f(14,1,0)= 1 \operatorname{OR} 0=1$. - `output_circuit[0]` represents the final stored number of `alic`, i.e. $(0100111000100000)_2 = 20000$. Since `alic` received only one letter from `bob`, `alic`’s final result is $20000$. - `bob`’s final stored number should be $0$ because he did not receive any letters; `circ`’s final stored number should be $(10000 + 20000 + 30000 + 30000) \bmod 65536 = 24464$. The attached `abc.cpp` can pass this sample, but we do not guarantee that it can pass other test cases. ### Constraints For all test cases: - $0\leq n\leq 700,0\leq m\leq 1000$. - All member names are distinct, have maximum length $4$, and consist only of lowercase English letters. - Each member’s favorite number is an integer between $0$ and $65535$. - All sender and recipient names appear in Alice’s input array `names`. - The memory limit for both `alice()` and `bob()` is $2048$ MiB, and the time limit for both is $0.02$ seconds. - The memory limit for `circuit()` is $2048$ MiB, and the time limit is $7$ seconds. In the final test, `alice()` and `bob()` may be called multiple times in a single test case. The time limit for each call is $0.02$ seconds. ### Subtasks #### Subtask Type A (12 points) Subtasks 1, 2, 3 are of Type A. Type A guarantees: - $n=1$. Each subtask has the following additional constraints: - Subtask 1 (4 points): $m=0$. - Subtask 2 (4 points): $0\leq m\leq 1$. - Subtask 3 (4 points): $0\leq m\leq 1000$. #### Subtask Type B (54 points) Subtasks 4, 5, 6 are of Type B. Type B guarantees: - $0\leq n\leq 30,\frac{n}{2}\leq m\leq n^2$. - There do not exist two letters with the same sender and recipient. - All member names appear in Bob’s input (that is, each member either sent at least one letter or received at least one letter). Each subtask has the following additional constraints: - Subtask 4 (24 points): $n = 26$. All member names are single English letters, and in Alice’s input, the member names are in order from `a` to `z`. - Subtask 5 (24 points): $n = 26$. - Subtask 6 (6 points): No additional constraints. #### Subtask Type C (34 points) Subtasks 7, 8, 9 are of Type C. Type C guarantees: - $0\leq n\leq 700,0\leq m\leq 1000$. Each subtask has the following additional constraints: - Subtask 7 (18 points): $n=676$. All member names are exactly two English letters, and in Alice’s input, member names are sorted in increasing lexicographical order (in other words, in the order `aa`, `ab`, `ac`, ..., `az`, `ba`, ..., `bz`, `ca`, ..., `zz`). - Subtask 8 (10 points): $n = 676$. - Subtask 9 (6 points): No additional constraints. ## Sample ### Sample grader program The sample grader program reads input in the following format: - Line $1$: $n\quad m$. - Line $2+i$ ($0\leq i\leq n-1$): $names_i\quad numbers_i$. - Line $2+n+i$ ($0\leq i\leq m-1$): $senders_i\quad recipients_i$. The sample grader program prints your answer in the following format: - If the program terminates successfully, the sample interactor will output $n$ lines, each containing one integer, representing the final stored number computed by your circuit for each member. - Otherwise, the sample interactor will not output anything to standard output, and will write an error message to the file `abc.log` in the directory. - In addition, the sample interactor will output the values of $l_A, l_B, l$ and the running time of each function to `abc.log`. The sample grader program will not check the memory limit, and will not check the constraint that when $n$ / $m$ are the same, $l_A$ / $l_B$ must be the same.

N/A

N/A

Translated by ChatGPT 5