C2211 - Henry's Sprint

Subtask 1

You can use a greedy algorithm. In each second, you should make Henry walk the maximum number of steps possible ($K$ m), until the total distance is at least to $D$ m.

Time Complexity: $O(D)$

Subtask 2

Note that the answer given by the greedy algorithm is always $\lceil\frac{D}{K}\rceil$. While this is mathematically correct, floating-point numbers are inaccurate.
You may use an if-statement, output D / K if $D$ is a multiple of $K$, otherwise output D / K + 1.
You can also calculate the answer using (D - 1) / K + 1 because $\lceil\frac{D}{K}\rceil = \lfloor\frac{D - 1}{K}\rfloor + 1$.

Time Complexity: $O(1)$

C2212 - School of Imposture II

You can sort the names using a custom comparator. You should compare the length of the strings first. If they are of equal length, you can compare the strings directly using $<$ as C++ already implements alphabetical order for $<$.

Time Complexity: $O(N \log N)$

C2213 - Pair Programming

Subtask 1

Use a map to store the partner of each programmer. Use another map/set to store if each programmer is working at the office.
After each change, iterate through all pairs of partners to count the number of pairs performing pair programming.

Time Complexity: $O(NQ \log N)$

Subtask 2

The initial answer is $\frac{N}{2}$. Note that after each change, the answer may increase/decrease by 1 or remain unchanged. This depends on where the specified programmer and their partner are working. If before the change both programmer work at the office, then decrease the answer by 1. If after the change both programmers work at the office, then increase the answer by 1.

Time Complexity: $O(Q \log N)$

C2214 - Too Long

Subtask 1

Note that $((a \& b) \& c) = (a \& (b \& c))$, meaning order of bitwise ANDs does not matter. Hence, $((((I \& X_1) \& X_2) \& \dots ) \& X_N) = I \& (((X_1 \& X_2) \& \dots ) \& X_N)$. You can observe this from Sample 2. Therefore you can output "1 AND $(((X_1 \& X_2) \& \dots ) \& X_N)$" is sufficient. But wait. This does not give you AC for subtask 1. What are you missing?
It is the evil $2^{31}-1$: this number has a 31 set bits (1-bits), therefore the bitwise AND of this number with any other number is the other number itself. When all $X_i=2^{31}-1$, you simply output $0.$

Subtask 2

XOR has a similar property with AND, order of operations does not matter. You can still output "1 XOR $(((X_1 \oplus X_2) \oplus \dots ) \oplus X_N)$". ($\oplus$ means XOR)
But when do you need no operations? This time is the evil $0$: no bit is flipped when a number is XOR-ed with 0. Hence, if $(((X_1 \oplus X_2) \oplus \dots ) \oplus X_N)=0$, you output $0$ instead.

Small note

Since the bitwise AND of $2^{31}-1$ and other numbers does not change the other number, we call $2^{31}-1$ an identity element of AND.
Similarly, $0$ is the identity element of XOR. Can you find the identities of other functions? (like bitwise OR, gcd, lcm, max, min...)
You will learn more in group theory.

Subtask 3

The $N \le 9$ hints us brute force. But I could not come up with any brute force solutions. So if you did write one, congratulations, the 20% is yours.

Subtask 4

For this subtask we need an observation. First we simplify the problem. What if $0 \le X_i,I \le 1$? We can run the program for $I=0$ and $1$. Let us call the respective outputs $R_0$ and $R_1$. How do we compress the program according to the outputs?

$R_0$	$R_1$	Most compressed program
0	0	"1 AND 0"
0	1	"0"
1	0	"1 XOR 1"
1	1	"2 AND 0 XOR 1"

It seems like that the length of the shortest program is at most 2. Moreover, remember that bitwise operations treat each bit separately. Therefore, you can try generate all programs of length 1 and length 2.
Remember other bits for the AND operation except the low 4 has to be set, i.e. $11111111111111111111111111110101_2$, for example. Time complexity: $O(N \cdot \max(A_i)^2)$

Subtask 5

Now extending the idea of subtask 4, let us try construct a program of length 2.

$R_0$	$R_1$	Most compressed program
0	0	"2 AND 0 XOR 0"
0	1	"2 AND 1 XOR 0"
1	0	"2 AND 1 XOR 1"
1	1	"2 AND 0 XOR 1"

Basically we just added the identities (AND 1, XOR 0) observed from subtask 1 and 2.
Since each bit is separate, we can treat them separately in the program, meaning for each bit, we can use $R_0$ and $R_1$ for that bit to construct a solution.
For example, if $R_0=01_2$ and $R_1=11_2$, the answer would be "2 AND $(1 \cdots 110)_2$ XOR $(0 \cdots 001)_2$".
Moreover, like the first two subtasks, if the first operation is "AND $2^{31}-1$", it is not needed. Similarly, if the second operation is "XOR $0$", it is also not needed. Time complexity: $O(N \cdot \log(\max(A_i)))$