Codeforces Round #823

Codeforces Round #823 — editorial

1730A - Planets

To solve the problem, it was enough to count the number of planets with the same orbits $c n t_{i}$ and sum up the answers for the orbits separately. For one orbit, it is advantageous either to use the second machine once and get the cost $c$ , or to use only the first one and get the cost equal to $c n t_{i}$ .

Jury solution: 173498496

1730B - Meeting on the Line

There are many solutions to this problem, here are 2 of them.

1) Let people be able to meet in time $T$ , then they could meet in time $T + ε$ , where $ε > 0$ . So we can find $T$ by binary search. It remains to learn how to check whether people can meet for a specific time $T$ . To do this, for the $i$ -th person, find a segment of positions that he can get to in time $T$ : if $T < t_{i}$ then this segment is empty, otherwise it is $[x_{i} - (T - t_{i}), x_{i} + (T - t_{i})]$ . Then people will be able to meet only if these segments intersect, that is, the minimum of the right borders is greater than or equal to the maximum of the left borders. In order to find the answer by the minimum $T$ , you need to intersect these segments in the same way (should get a point, but due to accuracy, most likely, a segment of a very small length will turn out) and take any point of this intersection. Asymptotics is $O (n \log n)$ .

2) If all $t_{i}$ were equal to $0$ , then this would be a classical problem, the solution of which would be to find the average of the minimum and maximum coordinates of people. We can reduce our problem to this one if we replace the person ( $x_{i}$ , $t_{i}$ ) with two people: ( $x_{i} - t_{i}$ , $0$ ) and ( $x_{i} + t_{i}$ , $0$ ). Proof. Let the meeting be at the point $y$ . Let $x_{i} \leq y$ . Then this person will need $t_{i} + y - x_{i}$ of time to get to her, and the two we want to replace him with — $y - x_{i} + t_{i}$ and $y - x_{i} - t_{i}$ . it is easy to see that the first value is equal to the initial value, and the second is not greater than the initial value, then the maximum of these two values is equal to the initial value. The proof is similar for the case $y \leq x_{i}$ . Then for any meeting point, the time in the original problem and after the replacement does not differ, which means that such a replacement will not change the answer and it can be done. Asymptotics is $O (n)$ .

binary search: 173497901

classic: 173497940

1730C - Minimum Notation

We leave all suffix minimums by the digits $m n_{i}$ (digits less than or equal to the minimum among the digits to the right of them), remove the rest and replace them with $min (d + 1, 9)$ (using the described operations) and add to lexicographically minimum order on the right (due to the appropriate order of operations, this is possible). The suffix minimums $m n_{i}$ should be left, because no matter what digit we leave after $m n_{i}$ , it will be no less than $m n_{i}$ , and therefore will not improve the answer. The rest must be removed at the end with operations, since there is a number to the right less than this one, i.e. if you remove everything before it (put $m n_{i}$ at the current position), the answer will become less than if you leave another digit at this position.

Jury solution: 173498569

1730D - Prefixes and Suffixes

If you reflect the second string and see what happens, it is easy to see that the elements at the same positions in both strings after any action remain at the same positions relative to each other. Let's combine them into unsorted pairs and treat these pairs as single objects. Now we need to compose a palindrome from these objects. This is always possible with the help of these actions, if there is a palindrome consisting of these objects (pay attention to odd palindromes, there must be a pair of the form (a, a) in the center).

Proof of possibility:

Let's make an array of pairs, in one action we expand some prefix of this array and the elements in the pairs of this prefix are swapped. Let's prove that we can change the order of the pairs in the array as we like. We will build from the end. Let all the pairs after position $i$ already stand as we want, and now the pair that we want to place in position $i$ at position $j \leq i$ . Let's do the following:

$1.$ $k = j$ — will move the pair from position $j$ to the beginning.

$2 * .$ $k = 1$ — swap elements within a pair if needed (so pairs are considered unsorted).

$3.$ $k = i$ — move the pair from the beginning to position $i$ .

(* the $2$ action is optional if you don't want to change the order of the elements in the pair)

With this construction, we can get any permutation of these pairs and a palindrome, if it is possible. If you divide the final palindrome into two strings and expand the second one back, you get the first string.

Example:

From the test suite from the condition:

$s_{1} = b b c a a$ , $s_{2} = c b a a b$ , expanded $s_{2} = b a a b c$ .

Couples:

$(b, b)$ , $(b, a)$ , $(c, a)$ , $(a, b)$ , $m a t h t t (a, c)$ .

Pairs unordered:

$(b, b)$ , $(a, b) \cdot 2$ , $(a, c) \cdot 2$ .

Pairs in a palindrome:

$(a, b)$ , $(a, c)$ , $(b, b)$ , $(a, c)$ , $(a, b)$ .

Real couples:

$(a, b)$ , $(a, c)$ , $(b, b)$ , $(c, a)$ , $(b, a)$ .

Strings: $s_{1} = a a b c b$ expanded $s_{2} = b c b a a$ , $s_{2} = a a b c b$ .

!!! The pair $(b, b)$ !!!

Jury solution: 173498668

1730E - Maximums and Minimums

Let's introduce some new variables: $l g e_{i}$ - the position of the nearest left greater or equal than $a_{i}$ ( $- 1$ if there is none). $r g_{i}$ - position of the nearest right greater than $a_{i}$ ( $n$ if there is none). $l l_{i}$ - position of the nearest left lower than $a_{i}$ ( $- 1$ if there is none). $r l_{i}$ - position of the nearest right lower than $a_{i}$ ( $n$ if there is none). All this can be calculated, for example, using a stack in $O (n)$ or using binary search and sparse table in $O (n \log n)$

Let's iterate over the position $i$ of the leftmost maximum of the good segment. Then the $i$ -th element will be the maximum on the segment [l, r] if $l g e_{i} < l \leq i$ and $i \leq r < r g_{i}$ $(1)$ . For the segment to pass the test, the minimum must be a divisor of the maximum. Let's iterate over this divisor $d$ and find the number of segments where the maximum is $a_{i}$ and the minimum is $d$ . Consider positions of occurrence of $d$ $j_{1}$ and $j_{2}$ — the nearest left and right to $i$ (they can be found using two pointers). Let's find the number of segments satisfying the condition $(1)$ , in which the element $j_{1}$ is a minimum. To do this, similar conditions must be added to $(1)$ : $l l_{i} < l \leq j_{1}$ and $j_{1} \leq r < r g_{i}$ . Intersecting these conditions, we obtain independent segments of admissible values of the left and right boundaries of the desired segment. Multiplying their lengths, we get the number of required segments. Similarly, the number of segments satisfying $(1)$ , in which $j_{2}$ is the minimum, is found, but in order not to count 2 times one segment, one more condition must be added: $j_{1} < l$ . The sum of these quantities over all $i$ and divisors of $a_{i}$ will give the answer to the problem.

To enumerate divisors, it is better to precompute the divisors of all numbers in $O (A \log A)$ , where $A$ is the constraint on $a_{i}$ . So the whole solution runs in $O (A \log A + n D)$ , where $D$ is the maximum number of divisors.

Jury solution: 173498009

1730F - Almost Sorted

Let's build a permutation $q$ from left to right. If the current prefix contains the number $i$ , let's call the element $p_{i}$ used, otherwise — unused. Consider the smallest unused element $m n = p_{j}$ . All elements greater than $m n + k$ must also be unused, and all elements less than $m n$ must be used. Then the current state can be described by the number $m n$ and the mask, $i$ -th bit of which indicates whether the element with the value $m n + i$ is used.

Let's solve the problem by dynamic programming: $d p [m n] [m a s k]$ is the minimum number of inversions. We can continue building a permutation by adding the number $i$ such that $m n \leq p_{i} \leq m n + k$ and $p_{i}$ hasn't been used yet. New inversions can be divided into two types: those formed with indices of elements less than $m n$ (they can be counted using Fenwick tree) and those formed with indices of elements not less than $m n$ (but their number is not more than $k$ ).

The time complexity is $O (n \cdot 2^{k} \cdot k \cdot (k + \log n))$ .

Jury solution: 173498327

Search This Blog

Md Shoriful Islam Ashiq