Codeforces Round #896 (Div. 2) ABCDE Solutions (Java/C++)

A. Make It Zero

Solution:

If we XOR all the numbers together, for each bit, if there were originally an odd number of 1s in that bit, the result will be 1; otherwise, it will be 0.

If n is even, even in the the worst-case scenario, we can set all numbers' bits in a specific position to 1 first, and then XOR them to make them all 0.

If n is odd, the process is similar. We set a specific bit to 1 in the first step, then set the first n-1 numbers to 0, and finally, set the last two numbers to 1 and then to 0.

Code:

Java

C++

B. 2D Traveling

Solution:

Firstly, passing through non-major cities won't yield a better solution. Also, passing through only one main city won't provide a better solution either.
So, except for the direct route from city a to city b, the only possible better solution is to separately find the nearest main cities to a and b.

Enumerate these two main cities, and find the optimal solution.

Code:

Java

C++

C. Fill in the Matrix

Solution:

The main construction method is to shift each row by one position. For example: $$
\begin{bmatrix}
0 & 1 & 2 & 3 & 4 \\
4 & 0 & 1 & 2 & 3 \\
3 & 4 & 0 & 1 & 2 \\
2 & 3 & 4 & 0 & 1 \\
1 & 2 & 3 & 4 & 0 \\
\end{bmatrix}
$$

For m>n, construct it as mentioned above directly. Because the number of columns is greater than the number of rows, any columns beyond n should be filled with 0.

For m less than or equal to n, because the above construction method lacks 0, start from the m-1th row stop shifting the elements.

Code:

Java

C++

D1. Candy Party (Easy Version)

Solution:

Clearly, if the average is not an integer, there is no solution.

Furthermore, if $a_i=avg$, the number of candies given away and received back by $a_i$ must be equal.
Since each person has to give away and receive candies once, those who have the average number of candies don't need to be considered; just skip them.

For the remaining people, whether they receive or give away candies, it's $2^?$ candies. So the binary representation of the difference between his original number of candies and the average must consist of several 1s followed by several 0s. For example, 111100 or 1111.
Therefore, we can determine how many candies each of these people receives or gives away based on the changes in their number of candies.

In the end, the candies given away must correspond to the recipients.

Code:

Java

C++

D2. Candy Party (Hard Version)

Solution:

Different to the Easy version, each person can choose not to give away or not to receive candies.
So, for those whose number of candies is exactly equal to the average, we can ignore them.

For the remaining people, if the binary representation of the difference in candies contains more than one 1, they must both give away and receive candies. Only cases with a single 1 in their binary representation can choose to either give away or receive candies (e.g., 1000 can choose to give or receive, but 1100 cannot).

For those who can choose not to exchange candies, they provide more flexibility.
If a person needs to receive $2^x$ candies, they can choose to receive $2^{x+1}$ candies and give away $2^x$ candies. Conversely, if they need to give away $2^x$ candies, they can do the opposite.
In other words, these people, besides adapting to their demand, can also switch to x when x+1 cannot be accommodated.

So, unlike the Easy version, we need to differentiate between hard and soft constraints. When processing x from large to small, if a hard requirement or supply of x cannot be handled, we need to see if x-1 can be supplemented.
Note: when processing x, if the soft demand or supply hasn't been used for x+1, it will also be converted into a hard demand or supply.

Code:

Java

C++

E. Travel Plan

This problem feels like a mash-up of two classic (or simple) problems, forced into a single question.