Codeforces Round 893 (Div. 2) ABCD Solutions (Java/C++)

A. Buttons

Solution:

Both players will prioritize button $c$. So, Anna can win an additional point if and only if $c$ is odd. Then, it only matters if $a-b$ is greater than zero. If it's less than or equal to 0, Anna will definitely lose; otherwise, she will win.

Code:

Java

C++

B. The Walkway

Solution:

Since he will definitely eat a cookie every d minutes at least, the influence of removing one seller is only between two adjacent sellers.
So, removing a seller $i$ changes the calculation from $\lfloor\frac {s_{i+1}-s_{i}} d\rfloor + \lfloor\frac{s_i - s_{i-1}} d\rfloor + 1$ to $\lfloor\frac {s_{i+1}-s_{i-1}} d\rfloor$.
Therefore, we only need to check which seller's removal has a bigger impact.

Code:

Java

C++

C. Yet Another Permutation Problem

Solution:

Firstly, it's not difficult to realize that there can be at most $\lfloor \frac n 2 \rfloor$ different results.
Assuming there exists $x>\lfloor \frac n 2 \rfloor$, the best scenario would be $a_i=x$ and $a_{i+1}=2\cdot x$, which $a_{i+1}>n$.

From this, it can be guessed that there are at most $\lfloor \frac n 2 \rfloor$ different results. So, let's try to find a way to construct them.

It's not hard to see that $\lfloor \frac n 2 \rfloor$ must be adjacent to $2\cdot \lfloor \frac n 2 \rfloor$. Because $3\cdot \lfloor \frac n 2 \rfloor>n$.
Similarly, $\lfloor \frac n 2 \rfloor - 1$ must be adjacent to $2\cdot (\lfloor \frac n 2 \rfloor - 1)$.
For example, if $n=21$, then 10 is adjacent to 20, and 9 is adjacent to 18.

Thus, through this method, we can construct up to around $\lfloor \frac n 4 \rfloor$. For example, 20 can be constructed to be adjacent to 6 and 12. But making 5 adjacent to 10 is not obvious, as 10 is already adjacent to 20.
However, it can be observed that 4 doesn't need to be adjacent to 9; instead, it should be adjacent to $2\cdot 4=8$.
In this way, each number $a_i$ only needs to be adjacent to $2\cdot a_i$.

For $n=21$, it would be $[1,2,4,8,16]+[3,6,12]+[5,10,20]+[7,14]+[11]+[13]+[17]+[19]+[21]$. In simpler terms, it's similar to the Sieve of Eratosthenes algorithm for finding primes.

Code:

Java

C++

D. Trees and Segments

Solution:

Firstly, considering the data constraints, $n^2=9\cdot 10^6 \approx 10^7$.

Because the importance of $l_0$ and $l_1$ is not linear with the increase of a, for instance, $l_0=1, l_1=100$ and $l_0=2, l_1=90$ versus $l_0=5, l_1=30$, the choice would differ as a changes.
For $a=1$, $1\cdot 1 + 100= 101$ is optimal, but for $a=20$, $20\cdot 2 + 90 = 130$ is optimal. For $a=100$, $100\cdot 5 + 30=530$ is optimal.

So, if we can calculate the maximum $l_0$ for any given $l_1$, we can obtain the result within the range of $n^2$. In other words, we need to calculate a $dp[l_1]=\max(l_0)$.

The idea pauses here for now.
Obviously, $l_0$ can be calculated within $n\cdot k = n^2$ as the longest contiguous substring of 0s that can be modified at most k times. That is, $dpLeft[i][j]$ represents the longest contiguous substring for the i-th tree from left to right, modified at most j times.
Similarly, you can maintain a $dpRight[i][j]$ representing the longest contiguous substring for the i-th tree from right to left, modified at most j times.

Now, integrate all the parts together.
It can be considered that the longest contiguous 1s can be enumerated within $n^2$.
Suppose the interval being considered is $[left, right]$, and the number of operations required to change all numbers in any interval to 1 can be maintained as a prefix sum, denoted as $count[right]-count[left-1]$.
Let $remian=k-(count[right]-count[left-1])$, then $dp[right-left+1]=\max(dpLeft[left-1][remain], dpRight[right+1][remain])$.

Code:

Java

C++