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

A. Stone Game

Solution:

Let us find the position of minimum and maximum value.
Then there are 4 ways to remove:
remove from left to right.
remove from right to left.
remove the maximum value from left to right and remove the minimum value from right to left.
remove the maximum value from right to left and remove the minimum value from left to right.

Code:

Java

C++

B. Friends and Candies

Solution:

Count the total number of all candies. If not divisible by n, then there is no solution:

Otherwise, then obviously, we collect the candies from people who have more than average candies than others. And reassign to others.

Code:

Java

C++

C. Number of Pairs

Solution:

Sort the a. For any i, we can find j which j<i and $l\leq a_j+a_i\leq r$.
So for any i, we have $l-a_i\leq a_j\leq r-a_i$. Now we can binary search to get the range of j within $O(log(n))$.

Code:

Java

C++

D. Another Problem About Dividing Numbers

Solution:

First, we notice that: the biggest number that after we changed a and b to same number is the GCD of a and b.

So, if $\frac{a}{gcd}$ and $\frac{b}{gcd}$ not 1. Then we can use 2 steps to make a and b to 1. If any one of it is 1, then it even no need 2 steps. So, if k is less than this, then there is no solution. And this is the minimum value of k.

And, if (the number of prime factors of a) + (the number of prime factors of b) is less than k. Then even we just divide only one prime factor every time, it still not enough, so there is no solution for this case. Now we get the maximum value of k.

Now, we already get the minimum and maximum value of k. If k is within this range, then there are some solutions for it. But there is one case:
If a and b is the same, and we ask k=1, then there is no solution. For example, 2 2 1 in the sample data. This is the only one exception.

Code:

Java

C++

E. Funny Substrings

Solution:

We maintain the first 3 characters and the last 3 characters, the length and the number of matches of the string corresponding to each variable.

Now, if we concatenate two variables, the number of matches is the sum of the number of matches of each variable and the number of matches of the string which is the concatenation of the last 3 characters of first variable and the first 3 characters of second variable.

Code:

Java

C++

F. Interesting Function

Solution:

We can get the number of changes from 0 to r and changes from 0 to l. Just subtract the two numbers.

And we know that for any x, from 0 to x, ones have changed x times, tens changed $\frac{x}{10}$ times, and hundreds changed $\frac{x}{100}$ times, and so on...

Code:

Java

C++

G. Gift Set

Solution:

For the two options, we use p1 and p2 to denote the the number of each option. So, $p1\cdot a + p2 \cdot b \leq x$ and $p1\cdot b + p2 \cdot a \leq y$.

And p2 is determined by p1 actually. So, $p2=\min(\frac{(x - p1 * a)} {b} , \frac {(y - p1 * b)} {a})$. So the total number of gifts is: $p1+\min(\frac{(x - p1 * a)} {b} , \frac {(y - p1 * b)} {a})$.
So, the slope of f(p1) is $1-\frac a b$ or $1-\frac b a$. And the sign of the slope depends on the size of a and b.

Therefore, the image of f(p1) can be drawn in 4 possibilities: monotonously increasing, monotonously decreasing, upwardly convex curve, and downwardly concave curve.
For monotonously increasing, monotonously decreasing and downwardly concave curve, the answer should be all in p1 or all in p2.
For upwardly convex curve, we can get the maximum value by binary search the slope.

So, the answer is we max of all in p1, all in p2, and the maximum value find by binary search.

Code:

Java

C++