abc — APIO contest
Task type: interactive | Time limit: 10 s | Memory limit: 2048 MB | Difficulty: 24
Algorithms: multiplexer, bitmask, constructive

# Alice, Bob, and Circuit

![APIO2023 Tasks English (ISC)](_page_0_Picture_0.jpeg)

The Cyberland Circuit Foundation consists of $n$ members. Each member has his/her favorite number and a unique name (the favorite numbers may not be distinct).

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

Each member calculates the sum of the contents (senders' favorite numbers) they received and takes the modulo of 65536 (i.e., $2^{16}$) as his/her result number.

Your task is to determine all result numbers.

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 $n$ 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 $10^5$.
- Bob knows all $m$ 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 $10^5$.
- Circuit can receive binary strings sent by Alice and Bob, and subsequently generate a binary string comprising $16n$ 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 $l_A + l_B$ input gates, labeled from 0 to ($l_A + l_B - 1$), where $l_A$ and $l_B$ are the lengths of the strings from Alice and Bob, respectively.
    - For $0 \le i < l_A$, the output of the $i$-th gate is the $i$-th bit of the string from Alice;
    - For $0 \le i < l_B$, the output of the $(i + l_A)$-th gate is the $i$-th bit of the string from Bob.
- Computation gates have two inputs and represent the computation process.
    - The labels for computation gates start from $(l_A + l_B)$.
- For each computation gate, you should provide labels of two dependent gates for input, and the operation type $p$ (0 ≤ $p$ ≤ 15).
    - 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 $x_0$ and $x_1$ respectively ($x_0, x_1 \in \{0, 1\}$), then the output of the computation gate is:

$$f(p, x_0, x_1) = \left\lfloor \frac{p}{2^{x_0 + 2x_1}} \right\rfloor \mod 2$$

Here are some examples that may be useful for you:

| $x_0$ | $x_1$ | $x_0 \text{ AND } x_1$ <br> $f(8, x_0, x_1)$ | $x_0 \text{ OR } x_1$ <br> $f(14, x_0, x_1)$ | $x_0 \text{ XOR } x_1$ <br> $f(6, x_0, x_1)$ | $\text{NOT } x_0$ <br> $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] to a[n-1] are valid data, accessing indices beyond that range may cause an out-of-bounds error.
- All strings are terminated by a null character \0.

You should implement the following procedures:

## Alice

```c++
int alice(const int n, const char names[][5],
 const unsigned short numbers[], bool outputs_alice[]);
```

| Direction | Value | Length | Meaning                     | Constraint                                                                                                                       |
|-----------|-------|--------|-----------------------------|----------------------------------------------------------------------------------------------------------------------------------|
| Input     | n     | 1      | n                           | $0 \le n \le 700$                                                                                                                |
|           | names | n      | The name of each member.    | All names are distinct, consisting of lowercase English letters only, and have a maximum length of 4 characters.                |
|           | numbers | $n$    | The favorite number of each member.   | Each number is in the range from 0 to 65535.                                                                                      |
| Output    | outputs_alice | $l_A$ | The binary string is sent to Circuit. |                                                                                                                  |
|           | (Return value) | 1      | $l_A$                         | You need to make sure that $l_A$ does not exceed $10^5$ and when $n$ is the same, $l_A$ must be fixed.               |

## Bob

```c++
int bob(const int m, const char senders[][5],
 const char recipients[][5], bool outputs_bob[]);
```

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

### 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 output the circuit structure.

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

| Direction | Value           | Length | Meaning                                                                    | Constraint                                                                                                                                                                                          |
|-----------|-----------------|--------|----------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Input     | la              | 1      | $l_A$                                                                      |                                                                                                                                                                                                    |
|           | lb              | 1      | $l_B$                                                                      |                                                                                                                                                                                                    |
|           | operations      | $l$    | The type of operation performed by each gate in the circuit.               | An integer from 0 to 15.                                                                                                                                                                           |
|           | operands        | $l$    | The operand used by each gate in the circuit.                              | The number must be less than the label of the current gate.                                                                                                                                        |
| Output    | outputs_circuit | $n$    | The gate label of the circuit output.                                      | `outputs_circuit[i][j]` denotes the *j*-th bit (counting from the least significant bit) of the final result for the *i*-th member. The members are ordered according to Alice's input. |
|           | (Return value)  | 1      | $l$, which represents the total number of gates (including input gates). | You need to ensure that $l \le 2 \times 10^7$                                                                                                                                                      |

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

# Example

Consider the following calls:

```c++
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 3 members, the member with the name `alic` has a favorite number 10000, etc. A possible output for alice() is that,
    - The return value of alice() is 2, representing $l_A = 2$.
    - Inside alice() function, set `outputs_alice[0]` = 1, `outputs_alice[1]` = 0, representing that the result binary string is 10.
- Bob knows there are 5 letters, the first letter is from `alic` to `circ`, etc. A possible output for bob() is that,
    - The return value of bob() is 3, representing $l_B = 3$.
    - Inside 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:

```c++
circuit(2, 3, operations, operands, outputs_circuit);
```

#### A correct output for this function would be

- The return value of circuit() is 7, meaning that we add two computation gates, labeled 5 and 6.
- 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 that,

- Add a type 8 computation gate, with input from gate 0 and gate 4. The output of gate 0 is the 0-th bit of the string from Alice, which is 1; The output of gate 4 is the 2-nd bit of the string from Bob, which is 0. So the output for gate 5 is $f(8, 0, 1) = 0 \text{ AND } 1 = 0$.
- Add a type 14 computation gate, with input from gate 2 and gate 5. The output of gate 2 is the 0-th bit of the string from Bob, which is 1; The output of gate 5 is 0. So the output for gate 6 is $f(14, 1, 0) = 1 \text{ OR } 0 = 1$.
- `output_circuit[0]` represents the final result of `alic`, which is (0100111000100000)$_2$ = 20000. Since `alic` only receives a letter from `bob`, the final result of `alic` is 20000.
- The final result of `bob` should be 0, since he receives no letter; The final result of `circ` should be $(10000 + 20000 + 30000 + 30000) \mod 65536 = 24464$.

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

# Constraints

For all test cases:

- $0 \le n \le 700$, $0 \le m \le 1000$.
- All names are distinct, consisting of lowercase English letters only, and have a maximum length of 4 characters.
- The favorite number of each member is in the range of 0 to 65535.
- The names of all senders and recipients appear in Alice's input array `names`.
- alice() and bob() have a memory limit of 2048 MiB and a time limit of 0.02 seconds, respectively.
- circuit() has a memory limit of 2048 MiB and a time limit of 7 seconds.

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

# Subtasks

Subtask Type A (12 points)

Subtask 1,2,3 are in subtask type A, where $n = 1$.

Each subtask has the following additional constraints:

- Subtask 1 (4 points): $m = 0$.
- Subtask 2 (4 points): $0 \le m \le 1$.
- Subtask 3 (4 points): $0 \le m \le 1000$.

## Subtask Type B (54 points)

Subtask 4,5,6 are in subtask type B, where:

- $0 \le n \le 30$, $\frac{n}{3} \le m \le n^2$.
- 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).

Each subtask has the following additional constraints:

- Subtask 4 (24 points): $n = 26$, All members' names are single lowercase letters, and in Alice's input, they appear in order from a to z.
- Subtask 5 (24 points): $n = 26$.
- Subtask 6 (6 points): No special restrictions.

## Subtask Type C (34 points)

Subtask 7,8,9 are in subtask type C, where $0 \le n \le 700$, $0 \le m \le 1000$.

Each subtask has the following additional constraints:

- Subtask 7 (18 points): $n = 676$, all members' names are two lowercase letters, and in Alice's input, they appear in lexicographical order (e.g., aa, ab, ac, ..., az, ba, ..., bz, ca, ..., zz).
- Subtask 8 (10 points): $n = 676$.
- Subtask 9 (6 points): No additional constraints.

# Sample Grader

The sample grader reads the input in the following format:

- Line 1: $n$ $m$
- Line 2 + $i$ (0 ≤ $i$ ≤ $n$ − 1): $names_i$ $numbers_i$
- Line 2 + $n$ + $i$ (0 ≤ $i$ ≤ $m$ − 1): $senders_i$ $recipients_i$.

The sample grader outputs in the following format:

- If the program finishes successfully, the sample grader will output $n$ 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 $l_A$, $l_B$, $l$ 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 $n/m$, $l_A/l_B$ must be equal.**

Starter code:
grader.cpp: #include "abc.h"
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
using namespace std;

const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;

void fatal(const string& msg) {
    cerr << msg << endl;
    exit(1);
}

void ensureImpl(bool condition, const char* conditionStr) {
    if (condition)
        return;
    fatal("Condition does not satisfy: " + string(conditionStr));
}

#define ensure(x...) ensureImpl(x, #x)

template <typename F>
void timed(const string& name, const F& func) {
    cerr << "Running " << name << "..." << endl;
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::nanoseconds>(end - start);
    cerr << name << " took " << fixed << setprecision(6) << (double) duration.count() / 1e9 << " seconds" << endl;
}

int main() {
    freopen("abc.log", "w", stderr);
    // ==================== Read Input ====================
    int n, m;
    cin >> n >> m;
    ensure(0 <= n && n <= 700);
    ensure(0 <= m && m <= 1000);

    auto readUshort = [&]() {
        string s;
        cin >> s;
        stringstream ss(s);
        unsigned short x;
        ss >> x;
        if (s != to_string(x))
            fatal("Invalid input for unsigned short: " + s);
        return x;
    };
    vector<pair<string, unsigned short>> students;
    map<string, unsigned short> studentsMap;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        if (name.empty())
            fatal("Expected name");
        if (name.size() > 4)
            fatal("Name too long: " + name);
        bool ok = true;
        for (char c : name)
            if (c < 'a' || c > 'z')
                ok = false;
        if (!ok)
            fatal("Invalid name: " + name);
        unsigned short number = readUshort();
        students.emplace_back(name, number);

        if (studentsMap.count(name))
            fatal("Duplicate name: " + name);
        studentsMap[name] = number;
    }

    auto readExistingName = [&] {
        string name;
        cin >> name;
        if (!studentsMap.count(name))
            fatal("Unknown name in Bob's input: " + name);
        return name;
    };
    vector<pair<string, string>> messages;
    for (int i = 0; i < m; i++) {
        string sender = readExistingName();
        string recipient = readExistingName();
        messages.emplace_back(sender, recipient);
    }

    // ==================== Call Alice ====================
    char (*aliceNames)[5] = new char[n][5];
    memset(aliceNames[0], 0, n * 5);
    unsigned short* aliceNumbers = new unsigned short[n];
    bool* aliceOutputs = new bool[MAX_LA];
    memset(aliceOutputs, 0, MAX_LA);
    for (int i = 0; i < n; i++) {
        strcpy(aliceNames[i], students[i].first.c_str());
        aliceNumbers[i] = students[i].second;
    }
    int la;
    timed("Alice", [&]() {
        la = alice(n, aliceNames, aliceNumbers, aliceOutputs);
    });
    cerr << "la = " << la << endl;
    ensure(0 <= la && la <= MAX_LA);

    // ==================== Call Bob ====================
    char (*bobSenders)[5] = new char[m][5];
    memset(bobSenders[0], 0, m * 5);
    char (*bobRecipients)[5] = new char[m][5];
    memset(bobRecipients[0], 0, m * 5);
    bool* bobOutputs = new bool[MAX_LB];
    memset(bobOutputs, 0, MAX_LB);
    for (int i = 0; i < m; i++) {
        strcpy(bobSenders[i], messages[i].first.c_str());
        strcpy(bobRecipients[i], messages[i].second.c_str());
    }
    int lb;
    timed("Bob", [&]() {
        lb = bob(m, bobSenders, bobRecipients, bobOutputs);
    });
    cerr << "lb = " << lb << endl;
    ensure(0 <= lb && lb <= MAX_LB);

    // ==================== Call Circuit ====================
    int* circuitOperations = new int[MAX_L];
    memset(circuitOperations, 0xff, MAX_L * sizeof(int));
    int (*circuitOperands)[2] = new int[MAX_L][2];
    memset(circuitOperands[0], 0xff, MAX_L * 2 * sizeof(int));
    int (*circuitOutputs)[16] = new int[n][16];
    memset(circuitOutputs[0], 0xff, n * 16 * sizeof(int));
    int l;
    timed("Circuit", [&]() {
        l = circuit(la, lb, circuitOperations, circuitOperands, circuitOutputs);
    });
    cerr << "l = " << l << endl;
    ensure(0 <= l && l <= MAX_L);

    bool* values = new bool[l];
    memcpy(values, aliceOutputs, la * sizeof(bool));
    memcpy(values + la, bobOutputs, lb * sizeof(bool));
    for (int i = la + lb; i < l; i++) {
        int op = circuitOperations[i];
        if (op < 0 || op > 15)
            fatal("Invalid operation: " + to_string(op) + " at Circuit index " + to_string(i));
        int a = circuitOperands[i][0];
        int b = circuitOperands[i][1];
        if (a < 0 || a >= i)
            fatal("Invalid operand 0: " + to_string(a) + " at Circuit index " + to_string(i));
        if (b < 0 || b >= i)
            fatal("Invalid operand 1: " + to_string(b) + " at Circuit index " + to_string(i));
        bool x0 = values[a];
        bool x1 = values[b];
        values[i] = op >> (x0 + 2 * x1) & 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 16; j++)
            if (circuitOutputs[i][j] < 0 || circuitOutputs[i][j] >= l)
                fatal("Invalid output: " + to_string(circuitOutputs[i][j]) + " at Circuit index " + to_string(i) + ", " + to_string(j));
    vector<unsigned short> answers;
    for (int i = 0; i < n; i++) {
        unsigned short ans = 0;
        for (int j = 0; j < 16; j++)
            ans |= (unsigned short) values[circuitOutputs[i][j]] << j;
        answers.push_back(ans);
    }

    // ==================== Calculate Reference Answer ====================
    map<string, unsigned short> referenceMap;
    for (int i = 0; i < m; i++)
        referenceMap[messages[i].second] += studentsMap[messages[i].first];
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (answers[i] != referenceMap[students[i].first]) {
            ok = false;
            cerr << "Wrong answer for " << students[i].first << ": expected " << referenceMap[students[i].first] << ", but got " << answers[i] << endl;
        }
    if (ok)
        cerr << "Your answer seems correct" << endl;

    // ==================== Print Answer ====================
    for (int i = 0; i < n; i++)
        cout << answers[i] << '\n';

    return 0;
}

abc.h: #ifndef ABC_H
#define ABC_H


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs[]
);


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs[]
);


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs[][16]
);


#endif // ABC_H

abc.cpp: #include "abc.h"

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1


// Alice
int // returns la
alice(
    /*  in */ const int n,
    /*  in */ const char names[][5],
    /*  in */ const unsigned short numbers[],
    /* out */ bool outputs_alice[]
) {
    outputs_alice[0] = 1;
    outputs_alice[1] = 0;
    return 2;
}


// Bob
int // returns lb
bob(
    /*  in */ const int m,
    /*  in */ const char senders[][5],
    /*  in */ const char recipients[][5],
    /* out */ bool outputs_bob[]
) {
    outputs_bob[0] = 1;
    outputs_bob[1] = 1;
    outputs_bob[2] = 0;
    return 3;
}


// Circuit
int // returns l
circuit(
    /*  in */ const int la,
    /*  in */ const int lb,
    /* out */ int operations[],
    /* out */ int operands[][2],
    /* out */ int outputs_circuit[][16]
) {
    operations[5] = 8;
    operations[6] = 14;
    operands[5][0] = 0; operands[5][1] = 4;
    operands[6][0] = 2; operands[6][1] = 5;
    int final_results[] = {20000, 0, 24464};
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 16; ++j)
            outputs_circuit[i][j] = 5 + (final_results[i] >> j & 1);
    return 7;
}