## APIO '23 P3 - Alice, Bob, and Circuit

View as PDF

Points: 45 (partial)
Time limit: 10.0s
Memory limit: 1G

Problem types
Allowed languages
C++

The Cyberland Circuit Foundation consists of members. Each member has a favorite number and a unique name (the favorite numbers are not necessarily distinct).

letters have been sent between the members. Each letter has a sender and a recipient, and the content of each letter is the sender's favorite number.

Each member calculates the sum of the contents (senders' favorite numbers) they received and takes this value modulo () as his/her result number.

However, the situation is not as straightforward as it seems. Alice, Bob, and Circuit decide to solve this problem in a slightly more complicated way:

• Alice knows all members (name and favorite number), but knows no information about letters. She needs to send a binary string to Circuit with a length of no more than .
• Bob knows all letters (sender and recipient's name), but knows no information about members. He needs to send a binary string to Circuit with a length of no more than .
• Circuit can receive binary strings sent by Alice and Bob, and subsequently generate a binary string comprising bits as output. However, due to its limited computational power, Circuit is only capable of performing basic logical operations (e.g., AND, OR, NOT).

In the following, we will introduce how the circuit works in detail.

#### Circuit Details

The gate is the basic element of a circuit. A gate consists of zero or two boolean inputs (depending on the type of gate), and one boolean output. There are two types of gates: input gates and computation gates.

• Input gates have no input and represent the bits from binary strings sent by Alice and Bob.
• There will be input gates, labeled from to , where and are the lengths of the strings from Alice and Bob, respectively.
• For , the output of the -th gate is the -th bit of the string from Alice.
• For , the output of the -th gate is the -th bit of the string from Bob.
• Computation gates have two inputs and represent the computation process.
• The labels for computation gates start from
• For each computation gate, you should provide labels of two dependent gates for input, and the operation type, .
• To prevent circular dependencies, the labels of the two dependent gates must be smaller than the label of the computation gate.
• If the outputs of its two dependent gates are and respectively (), then the output of of the computation gate is:

Here are some examples that may be useful for you:

AND
OR
XOR
NOT
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

• All array indices start from . For example, if is an array of length , then to are valid data, accessing indices beyond that range may cause undefined behaviour.
• All strings are terminated by a null character \0.

You should implement the following procedures:

##### Alice
int alice(const int n, const char names[][5], const unsigned short numbers[], bool outputs_alice[]);

Direction Value Length Meaning Constraint
Input n
names The name of each member. All names are distinct, consisting of lowercase English letters only, and have a maximum length of characters.
numbers The favorite number of each member. Each number is in the range from to .
Output outputs_alice The binary string sent to Circuit.
(Return value) You need to make sure that does not exceed and when is the same, must be fixed.
##### Bob
int bob(const int m, const char senders[][5], const char recipients[][5], bool outputs_bob[]);

Direction Value Length Meaning Constraint
Input m
senders The sender's name on each letter. All names appear in Alice's input.
recipients The recipient's name on each letter.
Output outputs_bob The binary string sent to Circuit.
(Return value) You need to make sure that does not exceed and when is the same, must be fixed.
##### Circuit

To ensure that the computation process of the Circuit is like a general circuit, you cannot directly obtain the binary strings sent from Alice and Bob to Circuit. You only know the lengths of these two strings and must output the circuit structure.

int circuit(const int la, const int lb, int operations[], int operands[][2], int outputs_circuit[][16]);

Direction Value Length Meaning Constraint
Input la
lb
Output operations The type of operation performed by each gate in the circuit. An integer from to .
operands The operands used by each gate in the circuit. These must be less than the label of the current gate.
outputs_circuit The gate label of the circuit output. outputs_circuit[i][j] denotes the -th bit (counting from the least significant bit) of the final result for the -th member. The members are ordered according to Alice's input.
(Return value) , which represents the total number of gates (including input gates). You need to ensure that .

Although you can modify the information of gates with indices less than in the operations and operands arrays, the grader would ignore such modification.

#### Example

Consider the following calls:

alice(3, {"alic", "bob", "circ"}, {10000, 20000, 30000}, outputs_alice);
bob(5, {"alic", "bob", "bob", "circ", "circ"}, {"circ", "circ", "alic", "circ", "circ"}, outputs_bob);


It represents the following scenario:

• Alice knows there are members, the member with the name alic has a favorite number , etc. A possible output for alice() is that,
• The return value of alice() is , representing .
• Inside the alice() function, set outputs_alice[0] = 1, outputs_alice[1] = 0, representing that the result binary string is 10.
• Bob knows there are letters, the first letter is from alic to circ, etc. A possible output for bob() is that,
• The return value of bob() is , representing .
• Inside the bob() function, set outputs_bob[0] = 1, outputs_bob[1] = 1, outputs_bob[2] = 0, representing that the result binary string is 110.

Based on previous outputs for alice() and bob(), there will be the following call:

circuit(2, 3, operations, operands, outputs_circuit);


A correct output for this function would be

• The return value of circuit() is , meaning that we add two computation gates, labeled and .
• Inside circuit(), set operations, operands, and outputs_circuit in the following way:
• operations = {-1, -1, -1, -1, -1, 8, 14}, where 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 a bit long, you can check abc.cpp in the attachments for the full array.

According to the output, the computation procedure is,

• Add a type computation gate, with input from gate and gate . The output of gate is the -th bit of the string from Alice, which is . The output of gate is the -nd bit of the string from Bob, which is . So the output for gate is .
• Add a type computation gate, with input from gate and gate . The output of gate is the -th bit of the string from Bob, which is . The output of gate is . So the output for gate is .
• output_circuit[0] represents the final result of alic, which is . Since alic only receives a letter from bob, the final result of alic is .
• The final result of bob should be , since he receives no letter.
• The final result of circ should be .

abc.cpp in the attachment can pass this example, but we do not guarantee that it can pass other test cases.

#### Constraints

For all test cases:

• m.
• All names are distinct, consisting of lowercase English letters only, and have a maximum length of characters.
• The favorite number of each member is in the range of to .
• The names of all senders and recipients appear in Alice's input array names.
• alice() and bob() have a memory limit of MiB and a time limit of seconds, respectively.
• circuit() has a memory limit of MiB and a time limit of seconds.

For the final evaluation, alice() and bob() may be called multiple times in a single test case. The time limit of seconds is for each call.

##### Subtask Type A (12 points)

• Subtask 1 (4 points): .
• Subtask 2 (4 points): .
• Subtask 3 (4 points): .
##### Subtask Type B (54 points)

• .
• There are no two letters with the same sender and recipient.
• All member names appear in Bob's input (i.e., each member either sends at least one letter or receives at least one letter).

• Subtask 4 (24 points): , All members' names are single lowercase letters, and in Alice's input, they appear in order from a to z.
• Subtask 5 (24 points): .
• Subtask 6 (6 points): No special restrictions.
##### Subtask Type C (34 points)

• Subtask 7 (18 points): , all members' names are two lowercase letters, and in Alice's input, they appear in lexicographical order (aa, ab, ac, , az, ba, , bz, ca, , zz).
• Subtask 8 (10 points): .

• Line 1:
• Line :
• Line :

The sample grader outputs in the following format:

• If the program finishes successfully, the sample grader will output lines, each containing an integer, representing the final result calculated by functions you implement for each member.
• Otherwise, the grader would output nothing to stdout and prints the error messages to the file abc.log in the directory.
• Additionally, the sample grader will output values of , , and the running time of each function to abc.log.

The sample grader will not check the memory limit and the restriction that for the same / , / must be equal.

#### Attachment Package

The sample grader along with sample test cases are available here: abc.zip.