Educational Codeforces Round 111 ABCD Solutions (Java/C++)

A. Find The Array

Solution:

Just be greedy. Press 1, 3, 5, 7 and so on in sequence, and stop as long as the sum is greater than s.

Code:

Java

C++

B. Maximum Cost Deletion

Solution:

First, the value of a does not affect the result. Because in the final result, the part of a must be $a\cdot n$. The question then becomes how many times b appears. So obviously, if b>0, we want to split into as many substrings as possible; if b<0, we want to split into as few substrings as possible.

For the case of b<0, we only need to count how many consecutive segments there are for 1 and 0 separately, which are recorded as c1 and c0, respectively. Then define $c=\min{(c0,c1)}$. In this case, c+1 operations are required. For example, 100111, c0=1, c1=2, and c=1. Need to operate 2 times, the first time to remove 0, and the second time to remove the remaining 1s.

The final result is $\min{[a\cdot n + b\cdot n, a\cdot n + b\cdot (c+1)]}$.

Code:

Java

C++

C. Manhattan Subarrays

Solution:

First, for $d(p, r) = d(p, q) + d(q, r)$, we can think that point q is actually between p and r. Therefore, let us assume that p<q<r.
When $a_p\leq a_q \leq a_r$: $a_r-a_p+r-p=a_q-a_p+q-p+a_r-a_q+r-q$, this equation is always established. Therefore, a single increase will not work.
When $a_p\geq a_q \geq a_r$: $a_p-a_r+r-p=a_p-a_q+q-p+a_q-a_r+r-q$, this equation is always established. Therefore, a single decrees will not work.

We consider constructing such a string [a,b,c,d,e,...] to make this array good. We construct one by one: let's suppose b>a, and naturally b>c.
Then we can find that d cannot be less than c, otherwise b, c, d will decrease only. d cannot be greater than b, otherwise a, b, and d increase only. So b>d>c.
Then we consider e, and obviously b>e>c immediately. At the same time, we notice that e cannot be greater than d, otherwise c, d, e increase only. e cannot be less than d, otherwise b, d, and e are decrease only. Therefore there is no such e.
In summary, the length of the subarray is 4 at most.

Obviously, a subarray of length 1 and length 2 must meet the requirements. The subarray of length 3 only needs to verify the monotonicity. For a subarray of length 4, we only need to verify that the values of a and d are between b and c.

Code:

Java

C++

D. Excellent Arrays

This question first needs to discover that $F(a)=\left\lfloor \frac{m}{2} \right\rfloor \cdot \left\lceil \frac{m}{2} \right\rceil$.
Then it is not difficult to think that for the same arrangement, the number of possibilities is only determined by the positions of two of the special elements. So we can get a way of $O(n^2)$.
Finally, a series of deformations and splits can be used to reduce the time complexity.