Codeforces Round #891 (Div. 3) ABCDEFG Solutions (Java/C++)

A. Array Coloring

Solution:

It is only possible to divide the array into two groups with the same parity if the total sum is even.

Code:

Java

C++

B. Maximum Rounding

Solution:

Round from right to left sequentially.

Code:

Java

C++

C. Assembly via Minimums

Solution:

Firstly, let's consider the scenario where $a$ contains no duplicate elements.
Obviously, $\min(a_i)$ will appear $n-1$ times, the second smallest $a_i$ will appear $n-2$ times, and so on. The second largest number will appear 1 time, and the largest number won't appear.

Next, consider the scenario with possible duplicates. There is no difference. Because, for example, if there are two identical numbers both being the second smallest one, then it can be considered as the second smallest and the other as the third smallest.

In summary, count the occurrences of each number in $b$.
Then, iterate from smallest to largest. Suppose the $b_i$ is the $j$-th smallest number. Subtract $n-j$ from $count[b_i]$. If $count[b_i]$ doesn't become 0, it means the $(j+1)$-th smallest number is the same as the $j$-th smallest number.

Code:

Java

C++

D. Strong Vertices

Solution:

$a_u-a_v \geq b_u-b_v$ is equivalent to $a_u-b_u \geq a_v-b_v$.
So, directly compute $a_i-b_i$ for any point $i$. The maximum $a_i-b_i$ is the answer.

Code:

Java

C++

E. Power of Points

Solution:

Firstly, it's not difficult to realize that the essence of $\sum\limits_{p=1}^{10^9}f_p$ is the sum of lengths of all intervals.
For each $p$, if it lies in $[s, x_i]$, it will add 1 to the result. So, every number within the interval will be added exactly once.

Now, it's easy to see that we can sort the $x_i$. This way, we can enumerate $s$ from small to large.
When $s$ changes from $x_i$ to $x_{i+1}$, the length of all intervals on the left side (including $i$) increases by $x_{i+1}-x_i$. The length of all intervals on the right side (excluding $i$) decreases by $x_{i+1}-x_i$. So, $ans[i+1]=ans[i]+i\cdot(x_{i+1}-x_i)-(n-i)\cdot(x_{i+1}-x_i)$.

Finally, sort $ans$ back based on the indices.

Code:

Java

C++

F. Sum and Product

Solution:

Substituting $a_j=x-a_i$ into $a_i\cdot a_j=y$ results in $a_i^2-x\cdot a_i+y=0$. So, $a_i=\frac {x\pm\sqrt{x^2-4\cdot y}} {2}$.
Therefore, it only needs to check if $a_i$ has integer solutions and count how many such $a_i$ exist.

Note that $a_j$ calculated might be equal to $a_i$. Also, $a_i$ might have two solutions, but it could also have only one solution.

Code:

Java

C++

G. Counting Graphs

Solution:

Consider the process of constructing the minimum spanning tree; we consider adding each edge to the tree sequentially.

When merging two subsets of the disjoint set union (DSU), besides the edge connecting the two subsets, there could also be $size[u]\cdot size[v] - 1$ edges can be added. These edges could have $s-w$ possible lengths (where $w$ represents the length of the new added edge). Count in no add any more edges, each possible edge could have $\max(s-w+1, 1)$ possibilities.
So, merging two subsets could result in $\max(s-w+1, 1)^{size[u]\cdot size[v] - 1}$ possibilities.

Therefore, when adding the $i$-th edge, the new subset could have $ans[u]\cdot ans[v] \cdot \max(s-w+1, 1)^{size[u]\cdot size[v] - 1}$ possibilities (where $ans[u]$ represents the number of possibilities of subset $u$).

Code:

Java

C++