Codeforces Global Round 3 Editorial

The answer is $$$2 * c + min(a, b) + min(max(a, b), min(a, b) + 1)$$$.

First, you can place all "ab" strings together.

Then if there are more "a" strings than "b" strings, you can start adding in the end "a" and "b" strings one by one in an alternating order.

If there are more "b" strings than "a" strings, you can do the same thing but add to the begin of the string.

If $$$k \geq n$$$, we can cancel all flights between A and B, and Arkady won't be able to get to C, so answer will be equal to $$$-1$$$. Otherwise, $$$k < n$$$.

If the subset of canceled flights is chosen, the Arkady's strategy is clear: use the earliest available flight from A to B, arrive to B at some time moment $$$t$$$ and choose the earliest not canceled flight from B to C with a departure time moment greater or equal than $$$t$$$.

Suppose we have chosen $$$x$$$ — a number of canceled flights between A and B. No matter what subset of flights will be cancelled between B and C, we should cancel the first $$$x$$$ flights from A to B. Now we know the exact moment of the Arkady's arrival to B — it is equal to $$$a_{x+1} + t_a$$$. Now our optimal strategy is to cancel the first $$$k-x$$$ flights between B and C, which Arkady can use. If there is no flights remaining, the answer is $$$-1$$$. Otherwise, Arkady will be in C at the $$$b_j + t_b$$$-th time moment, where $$$j$$$ is the index of the earliest flight, which Arkady can use. $$$j$$$ is equal to $$$pos + (k - x)$$$, where $$$pos$$$ is index of the first flight from B to C, which departure time moment is greater or equal than $$$a_{x+1} + t_a$$$.

Now we can just iterate through all possible $$$x$$$ and calculate the biggest time moment. Since array $$$b$$$ is sorted, you can find $$$pos$$$ using binary search. The complexity of this solution is $$$O(n \log n)$$$. Also the array of $$$a_{x + 1} + t_a$$$ values is sorted too, so you can use two-pointers method. This solution will work with $$$O(n)$$$ complexity.

The problem can be solved in $$$4n$$$ swaps in total in the worst case (might be there is a more optimal solution, but it wasn't required). Let's go from left to right through the array. Suppose our current position is $$$i$$$ and position of the number $$$i$$$ is $$$j$$$. If $$$i \ne j$$$, we want to swap them.

If $$$|i - j| \cdot 2 \geq n$$$, you can just swap(i, j).

If $$$\frac{n}{2} \leq i - 1$$$, than you can do swap(i, 1), swap(1, j), swap(i, 1).

If $$$\frac{n}{2} \leq n - j$$$, than you can do swap(i, n), swap(j, n), swap(i, n).

In the last case $$$\frac{n}{2} \leq j - 1$$$ and $$$\frac{n}{2} \leq n - i$$$ and so you do $$$5$$$ swaps: swap(i, n), swap(n, 1), swap(1, j), swap(1, n), swap(i, n).

One can be see, that the last case happens at most $$$\frac{n}{2}$$$ times, since when $$$i \geq \frac{n}{2} + 1$$$ you only need $$$3$$$ swaps or less. And so in total it's no more than $$$5 \cdot \frac{n}{2} + 3 \cdot \frac{n}{2} = 4 n$$$ swaps.

First notice, that there are two types of pairs: one with $$$a_i < b_i$$$ and another one with $$$a_i > b_i$$$.

Note, that we can't form an answer with pairs of different types. Now let's notice that we can take all pairs of fixed type. Suppose the type is $$$a_i < b_i$$$. Then sort pairs by their $$$a_i$$$ in the decreasing order and that is the answer.

For type $$$a_i > b_i$$$ let's sort them by $$$b_i$$$ in increasing order.

Just select the longest of two answers.

Consider original and target position of stones in sorted order.

Note, that we can always construct an answer preserving the original stones order (suppose we have an answer which doesn't preserve the order. It will happen when there are two stones at the same spot, just move the other one).

So now we simplified our problem — we want to move stone $$$s_i$$$ into $$$t_i$$$. So we now can compute $$$\delta_i = t_i - s_i$$$ — the relative movement of each stone.

To begin with, observe that if $$$\sum \delta_i \ne 0$$$ there is no solution, since the operations we can use preserve the sum of the coordinates.

However this is not enough, for example if $$$\delta_1 < 0$$$ (you need to move to the left the leftmost stone), there is clearly no answer. The real condition is that elements $$$\delta_i$$$ should form a "balanced bracket sequence", that is, the sum of every prefix of $$$\delta_i$$$ must be $$$\ge 0$$$. In this and only in this case we can match corresponding right-movements with left-movements.

In order to construct the exact answer we can go from left to right maintaining the stack of not-yet-closed "move-to-the right actions", formally we will put on stack pairs (stone_index, steps_to_move). So when we see stone with $$$\delta_i > 0$$$ we put it on the stack, and when we see stone with $$$\delta_i < 0$$$ we match it with the stones on the stack, removing the elements from the stack if they have moved to the full extent.

Let's solve this problem using the induction method. Let's solve this problem for all objects with masks less than $$$2^{K}$$$.

Base of the induction: $$$K = 1$$$, than we just can multiply price by $$$-1$$$, like adding a single bit into the answer, if the price has the same sign as the initial sum.

Move: we solved the problem for all masks less than $$$2^{K - 1}$$$. Now take a look on all masks smaller than $$$2^{K}$$$ and not less than $$$2^{K - 1}$$$. If the sum of their prices has the same sign as the initial sum, than we add bit $$$K - 1$$$ into the answer and multiply all prices of object with this bit in the mask by $$$-1$$$.

It's important to notice, that when we chose whether we need this bit we go only through numbers where this bit is the biggest one, but when we added it we need to recalculate prices for all object with this bit in the mask.

Firstly, let's discuss how to find the answer in $$$O(N^2)$$$ time. Let's assume $$$k$$$ is even. Pick any set on $$$k$$$ vertices. If it is a clique, just print it as an answer, if it is not, there must be two vertices in this set that don't share an edge. Just remove these two vertices and replace them with 2 arbitrary ones from the rest of the vertices. We can notice that if we remove $$$\frac{k}{2}$$$ such pairs, then removed vertices will form a set where all vertices are not fair.

If $$$k$$$ is odd, then the above algorithm has a problem, because we remove two vertices in one step. To fix it, we can find a triplet of vertices $$$a$$$, $$$b$$$, $$$c$$$ such that there is no edge between $$$a$$$ and $$$b$$$, and there is no edge between $$$b$$$, and $$$c$$$. Now, with this triplet we can get the set with odd size. If there are no such triplet, then, our graph has quite simple structure which we can handle separately.

Now to the $$$O(N \cdot Log \cdot 2^8)$$$ solution.

1. Assume we have a set of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$. We want to find, for how many $$$a_i$$$ have $$$gcd(a_i, x) \neq 1$$$. This can be done using inclusion-exclusion principle. Let $$$p_1, p_2, \ldots, p_k$$$ be distinct prime divisors of $$$x$$$. At first, we want to count how many $$$a_i$$$ is divisible by $$$p_1, p_2, \ldots, p_k$$$, but than $$$a_i$$$'s divisible by both $$$p_1, p_2$$$ are counted twice, so we subtract count of $$$a_i$$$ that is divisible by $$$p_1 \cdot p_2$$$ and so on. We can maintain set $$$a_1, a_2, \ldots, a_n$$$ and answer queries dynamically in $$$O(2^{NumberOfPrimeDivisors})$$$ time. This is the only place where we use the graph structure defined by the edge between two vertices $$$i$$$ and $$$j$$$ exists if only if $$$gcd(a_i, a_j) \neq 1$$$.
2. Like in $$$O(N^2)$$$ solution, let's find a triplet of vertices $$$a$$$, $$$b$$$, $$$c$$$ such that there is no edge between $$$a$$$ and $$$b$$$, and there is no edge between $$$b$$$ and $$$c$$$. Let's remove this triplet from the graph.
3. Let $$$b$$$ be the number of vertices that are connected to all other $$$n - 3$$$ vertices. If $$$b \geq k$$$ we can print any $$$k$$$ of them as a clique. Otherwise, let's remove all of these $$$b$$$ vertices. We can notice that remaining vertices plus removed triplet form an antifair set. Let's estimate size of this set: $$$S = (n - 3) - b + 3 = n - b$$$. Recall that $$$b \le k$$$ and $$$2 \cdot k \leq n$$$, so we have $$$S = n - b \geq k$$$. So, now we get an antifair set of size equal to $$$k$$$ or greater than $$$k$$$. Let's show that we always can construct an antifair set with size strictly equal to $$$k$$$.
4. In the previous paragraph we have estimated the maximum size of an antifair set on vertices $$$1, 2, \ldots, n - 3$$$. Let $$$f(R)$$$ be the maximum size of an antifair set on vertices with indices: $$$1, 2, \ldots, R$$$. Let's find with binary search lowest integer $$$c$$$ such that $$$f(c - 1) + 3 < k$$$ and $$$f(c) + 3 \geq k$$$. Let's look at the vertex $$$c$$$. The size of the maximal antifair set without it is $$$f(c - 1)$$$. The size of the maximal antifair set with it is $$$f(c)$$$. So among vertices $$$1, 2, \ldots, c - 1$$$ there are exactly $$$f(c) - f(c - 1) - 1$$$ of them connected with all vertices from $$$1$$$ to $$$c - 1$$$ and not connected with the vertex $$$c$$$. It is easy to see, that we can delete any $$$f(c) - f(c - 1) - 2$$$ of them or less and the remaining set of vertices will still be antifair. With this observation we can achieve either set of size $$$k$$$ or set of size $$$k + 1$$$. In the first case, we just find the answer. In the second case, remember, that we have reserved triplet and can delete one of it's vertex to make the total size $$$k$$$.

First, let's try to solve it if we know the whole array initially.

Let's move from the last element to the first. When we are in the element $$$i$$$ let's store all segments of right borders ($$$[r', r"]$$$) in the set, so that segment $$$[i, r]$$$ have the same mex value for all $$$r' \le r \le r"$$$. You can see that mex values in those segments are increasing from left to right, so you can recalculate those segments efficiently when you add another element from the left.

How to do so? Suppose we added element $$$k$$$ on the left. Then we must remove the segment with mex $$$k$$$ and replace it (with possibly many) segments of greater mex, the last of those segments might get merge with the segment following the removed one. It's easy to see that we add/remove only $$$O(n)$$$ segments in total since each time we remove exactly once segment, but add quite a lot. Informally, we simply can't add too much segments each time, since all mex's are distinct at every moment.

After that for each segment of the right borders we can compute when it was added to the set and when it was deleted. Then we can see it as a rectangle, where $$$x$$$ coordinates correspond to the left borders and $$$y$$$ coordinates correspond to the right borders. After that the problem is reduced to add value in the rectangle and compute the sum of values in the rectangle of a query.

So after that you need to notice, that those rectangles lay like in different stripes of surface. So they don't have points with the same x coordinates from different rectangles. That's why you can say, that to count total area laying on a query rectangle, you just can keep a segment tree with operations: add number to the segment, count the sum of number on the segment.

That's because there is only one rectangle intersecting your query, but not laying completely inside. So when you meet a rectangle during you scan line, you just add its width to the proper segment. Notice that there are actually $$$O(n)$$$ scan lines, because you need to keep them for every mex value. And for the query you need to get the state of your structure after some prefix of rectangles proceeded. They lay completely inside your query, so you need just to take the sum on the segment in your structure. Also there is one rectangle which can intersect you query, and you need to proceed it by hands. Another case is that in your set, when you proceed queries one by one, there are some current segment of mex, who was not deleted yet, so you need to take care about it too, because it can contain one segment with proper mex value for you query.