Codeforces Round #740 Div 2 ABCDE Solutions (Java/C++)

A. Simply Strange Sort

Solution:

This question can be simulated according to the requirements of the question.

Code:

Java

C++

B. Charmed by the Game

Solution:

First, if k is one of the answer, then n-k must also be one of the answer. Because by changing the serving person at the beginning, two different answers can be obtained for the same arrangement.

Then, consider the construction of the smallest k: Obviously, we can greedily allocate it.
Taking a=7 and b=4 as an example, we separate the odd field from the even field. We specify that Alice will not break when appearing in the odd field, and Borys will not break when appearing in the even field, so we can assign as follows:

Then, based on the above figure, we can exchange A and B in turn, as shown in the following figure:

Combining n-k, we can get all the possibilities.

Code:

Java

C++

C. Deep Down Below

Solution:

Obviously, we can easily get the minimum initial level required for each cave. Then sort them according to the lowest level required by the cave, pass in order, and update the required initial level.

Code:

Java

C++

D. Up the Strip

Solution:

Let dp[x] denote that there are dp[x] ways to go to x. Obviously dp[1] is the answer we want, dp[n]=1. We can calculate dp from n to 1 in turn.

In fact, it is not difficult to find that: $dp[x]=\sum_{i=x+1}^ndp[i]+\sum_{j=2}^{x\cdot j <=n}{\sum_{i=j\cdot x}^{j\cdot(x+1)-1}dp[i]}$.

First consider the relatively simple $\sum_{i=x+1}^ndp[i]$ part. This part is to consider the first operation. Take x=5 as an example. Obviously, all numbers after 5 can reach 5 through the first operation.

Then consider $\sum_{j=2}^{x\cdot j <=n}{\sum_{i=j\cdot x}^{j\cdot(x+1)-1}dp[i]}$ , Which is the second operation. We consider that each number reaches x by dividing by j.
Obviously when $j\cdot x \leq y\leq j\cdot(x+1)-1$, $\lfloor \frac{y}{j} \rfloor=x$.
Take x=5 and j=2 as an example. Obviously, 10 and 11 can be divided by 2 to reach 5. Taking x=3 and j=3 as an example, 9, 10, 11, and 12 can all be divided by 3 to reach 3.

So obviously, we maintain the suffix sum of dp, denoted as f[x]. The original dp formula can be simplified to $dp[x]=f[x+1]+\sum_{j=2}^{x\cdot j <=n}(f[j\cdot x]-f[j\ cdot (x+1)])$.
It is not difficult to find that for every x, j has $\frac n x$ possibilities. So a total of $\frac{n}{1}+\frac{n}{2}+\dots+\frac{n}{n-1}+\frac{n}{n}$ needs to be calculated, so its complexity Is $O(n\cdot log(n))$.

Code:

Java

C++

E. Bottom-Tier Reversals

Solution:

Obviously, because p can only choose odd numbers. Therefore, the parity of the index before and after sorting must not change. Therefore, if the parity is found to be inconsistent, just output -1 directly.

At the same time, it is not difficult to find that we must sort from right to left, and when we restore the value of an odd position to the correct value, his previous even position must also be restored to the correct value at the same time. Therefore, we can infer the following five cases in turn:

1. As shown in the figure below, the two numbers have been in reverse order at the beginning. In this case, we can just reverse it directly to p=7.

2. As shown in the figure below, the two numbers are arranged in an incorrect position in order. Then we set p=5, we can get the 1st case.

3. As shown in the figure below, if two numbers are in a certain position in reverse order. Let p=7, we can get the 2nd case.

4. As shown in the figure below, if two numbers are not consecutive, and the odd number is in the first place. Let p=5, we can get the 3rd case.

5. As shown in the figure below, if the two numbers are not consecutive, and the odd number is not in the first place. Let p=3, we can get the 4th case.

Therefore, a maximum of 5 steps are required. And every time you finish these 5 steps, you will definitely be able to recover two number. Therefore, it must be completed in $\frac 5 2 n$ steps.

Code:

Java

C++