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

A. Two Vessels

Solution:

The data size is very small, all within 100. So, you can simply simulate pouring water from the larger vessel to the smaller one step by step.

Code:

Java

C++

B. The Corridor or There and Back Again

Solution:

Obviously, once you pass a trap, you must return after $\lfloor{\frac{s-1}{2}}\rfloor$ steps.
So, we only need to calculate the maximum value of k for each trap that is stepped on and returned to, and then take the minimum.

Code:

Java

C++

C. Non-coprime Split

Solution:

Assuming a and b exist, and their greatest common divisor is g. Then, $(a+b)=g\cdot(\frac a g + \frac b g)$. In other words, a+b must be divisible by g, and $\frac a g + \frac b g > 1$.

So, we only need to find any composite number between l and r. In this way, we choose one of its factors as g, set a=g, and $b=\frac x {g} - 1$.

Code:

Java

C++

D. Plus Minus Permutation

Solution:

Clearly, the least common multiple of x and y corresponds to a number that does not affect the final result. So, we just need to make the remaining numbers corresponding to x as large as possible, and the remaining numbers corresponding to y as small as possible.

Code:

Java

C++

E. Data Structures Fan

Solution:

I'm not entirely sure if there is a simpler way to solve this problem. I directly used a segment tree, maintaining the XOR sum of intervals corresponding to g=0 and g=1.

Each update operation involves swapping the XOR sums of g=0 and g=1. Finally, you can query the XOR sum of the entire interval.

Code:

Java

C++

F. Selling a Menagerie

Solution:

Consider the fear value $a_i$ of animal i as a directed edge from i to $a_i$. This gives us a directed graph, where each point in this graph can have only one outgoing edge and any number of incoming edges. The structure of this graph should roughly resemble something like the following:

Naturally, for points with no incoming edges, removing them has no effect on the income. So, we prioritize removing points with an in-degree of 0.
This leaves us with several cycles.
For these cycles, we choose to remove the point with the minimum value. Therefore, we find the point x with the minimum value on the cycle and remove $a_x$.

Code:

Java

C++

G. Replace With Product

Solution:

First, if $a_i\geq 2$, then choosing multiplication over addition is obviously better. So, the fundamental problem lies in how to handle $a_i=1$.

It's clear that the 1s at the far left and far right must be excluded from the range [l, r]. So, we can assume that the beginning and end of the array are not 1s.
In that case, the remaining situations are [2,1,1,1,1,1,1,2] and [3,1,3], where there are many 1s in between. In such cases, addition is better than multiplication.
However, the maximum number of 1s in between can be at most $10^5$, which means the total sum of 1s in between can be at most $10^5$. So, as long as there are approximately 20 occurrences of 2, multiplication will always be better no matter how you choose the range (excluding the leftmost and rightmost 1s). This is because $2^{20}>10^5$.
So, the general idea is that when the product of the non-1 numbers in the array reaches a certain threshold, you can simply choose the largest possible interval for l and r (excluding the leftmost and rightmost 1s). Otherwise, you can brute force the positions of l and r.

It's worth noting that the threshold should not be $10^5$. For example, it could be something like $[2, 1, 1, ..., 1, 5\cdot 10^4]$. The result of choosing multiplication would be $10^5$, but the result of addition would be $(10^5-2)+2+5\cdot 10^4=1.5 \cdot 10^5$.
The exact threshold value I didn't calculated, it's simply given as $10^6$. In any case, $2^{32} > 10^9$, which means that it's less than 32 numbers no matter what.

Code:

Java

C++