Codeforces Round #713 Div3 Solutions

Problem F is interesting because it need DP and Greedy at same time. Problem G is just brute force to build a prepared data table. So not very funny. Problem a little bit complex to implement. Nothing special for other problems.

G. Short Task

Solution

Build a prepared data table before handle any input. We calculate the sum of factor for all numbers between 1 to $10^7$. And scanning all numbers to get the minimum number of each query.

Code

F. Education

Looks like knapsack problem or DP problem. But if solve as knapsack problem or dp only. Then will get trouble on the remain money after upgrade position. So this problem also need greedy strategy. If need upgrade position, then upgrade as soon as possible. And then, it become a easy problem.

E. Permutation by Sum

Solution

Let's define $len=r-l+1$, which means the length between $l$ and $r$. The minimum sum can be constructed is $\sum_{i=1}^{len}i$. The maximum sum is $\sum_{i=n-len+1}^{n}i$. All the $s$ between min and max sum can be constructed.

We start from the minimum one. At beginning we put 1 to $len$ into $l$ to $r$.

Base on this one, we check the value one by one. For each value, we try to change it to the largest possible value.

After the change, if the sum still less than s. Then we update our result.

Otherwise this value is the last value who is needed to be changed. So change it to some sensible number. And after that, the sum $s$

Code

D. Corrupted Array

Solution

It's very clear that: $b_{n+1}$ is the sum of $a$. So $b_{n+1}$ must be the maximum value in $b$ or the second maximum value ($x$ take the maximum value). So just need try these two.

Code

Be careful on Arrays.sort() in Java. Refer to this page, should use Long rather than long in java.

C. A-B Palindrome

Solution

Match the palindrome first. And we can determine some of 0 and 1.

After that, the '?' is also match palindrome. Then we change ? to the one which is larger between $a$ and $b$.

Only thing need to be careful is: if the length is odd, then we need some special logic for it.

Code

B. Almost Rectangle

Solution

Find 2 pairs of x and y coordinates directly. If get same x/y from the two poinsts, then +1 for that directly. If it more than $n$ then change it to 0.

Code

A. Spy Detected!

Solution

Find the number that appears only once. Output index.

Code