Codeforces Round #766 ABCDE Solutions (Java/C++)

A. Not Shading

Solution:

Obviously if (r, c) is originally black, then output 0. Output 1 if row r or column c is black. Output 2 if black is present. If not even black, output -1.

Code:

Java

C++

B. Not Sitting

Solution:

Obviously Rahul will choose the middle seat as much as possible, and Tina will hide in the 4 corners as much as possible. And when the middle position is painted pink, then Rahul will choose the position closest to the 4 corners (the maximum distance from the 4 corners).

So we calculate the distance from each point to the 4 corners, and then sort and output.

Code:

Java

C++

C. Not Assigning

Solution:

Obviously, the edge weight of each edge must be a prime number, and there must be exactly one edge between two adjacent edges whose edge weight is 2. Therefore, there is a solution if and only if the tree is actually a chain.

Therefore, it is only need to verify whether the tree is a chain, and then fill in 2 and 3 in turn.

Code:

Java

C++

D. Not Adding

Solution:

For a certain number X, if the GCD of all multiples of X in the final array is X, then X must be in the final array also.

Because if these numbers are multiples of X, there are only two possibilities for their GCD: 1. equal to X; 2. greater than X.
For the case greater than X, we give an example to illustrate. [8, 12, 13]. When X is 2, we find that the GCD is 4. Then it means that 4 should also be in the final result array. But not 2.

So we enumerate each number in order from large to small, and check it as above.

Code:

Java

C++

E. Not Escaping

Solution:

Clearly a DP problem. It's just that the code implementation is slightly cumbersome.

Since k is at most $10^5$, there are actually only at most $2\cdot 10^5 + 2$ points (include the start and end points) that have an impact.
So we can build a map based on these points, and then DP on the map.

We let DP[i][j] denote the minimum cost for the i-th floor to walk to the j-th room.
Obviously, if we know the final cost of floor a, we can update the value of DP[c][d] with DP[a][b] according to the situation of the ladder.
But at this time the value of DP[c][d] is not the final cost, because it is possible to go from DP[c][e] to DP[c][d] to obtain a smaller cost. So,$$\text{DP[c][d]} =
\begin{cases}
\text{dp[c][e]}+\text{x[c]}\cdot|d-e|,  & d > e\\
\text{dp[c][e]}+\text{x[c]}\cdot|e-d|,  & e > d
\end{cases}$$Therefore, we only need to traverse from left to right and from right to left twice to get the final value of DP[c][d].

In the end we just need to output the value of the end point.

Code:

Java

C++