Editorial for Technocup 2022 — Elimination Round 2 and Codeforces Round #755 (Di...

We have the equation:

Let's multiply the left and right parts by .

Received: .

After opening the brackets and simplifying, we have: .

One of the solutions to this equation is ,

Rectangles after cutting will be painted in a chess coloring. So, if the area is even, then the number of cells of different colors is the same, and if it is odd, then it differs by exactly .

Let's find out what part the colored cells occupy in relation to all of them. For an even area, this ratio is always . For odd . The smaller the odd area, the smaller the ratio. An area equal to cannot be obtained, so the best ratio is and is achieved with an area equal to .

Then we get the lower estimate for the answer: . Great!

We know that the answer is integer, so if we manage to construct such a cut that it is necessary to color exactly such a of cells that, then will be the answer. After all, is the minimum integer value satisfying the estimate.

If one of the sides is divisible by , then it is obvious how to cut into rectangles and get the perfect answer.

If the remains of sides and or and , then you can cut into rectangles and one rectangle with an area of , in which you need to paint over cells. Then the answer also fits the assessment.

If the remains of sides and , then after cutting into rectangles, a rectangle will remain , in which you need to paint one cell. The answer also fits the assessment.

For all pairs of remains, there is a way to construct an answer satisfying the inequality. Therefore, the answer is

Let's sort the arrays first.

Let's check the two smallest elements in the arrays and investigate their behavior. First, obviously, if (as nothing can be matched with ) or (as nothing can be matched with ) the answer is No. Then, it's possible that . In this case, we have to have at least one in the array at the end. Hence, we can leave untouched, as it already suits to . It's also possible that . Here we have to increase by . In both cases, the task is reduced to the smallest one.

Going to the exact solution from this logic, we just have to sort both arrays and check that for each it's or .

The complexity of the solution is .

Note that the number of inversions on decreasing sequence of length is .

As we reversed two non-overlaping subsegments, the number of inversions on each subsegment is equal to sum of number of inversions of parts of reversed subsegments, which are decreasing.

First of all, let's find — total number of inversions in sequence. We use 1 question for that.

Now let's look on the number of inversions on subsegment [, ]. If this number is less than A, then not both reversed subsegments fit entirely, so , otherwise .

Now we can apply binnary search to find . We use questions here.

Now let's ask the number of inversions on subsegment [, ], let's call this number B. We use question here. From the structure of sequence: = = = .

Now we can find , and , due to the definition of A, we find .

Finaly, we can solve quadratic equation for and get .

Overall, we used questions, but we gave you a bit more, in case your solution uses few more questions on some stage.

This game has greedy strategy: look at first pile, all its stones have to be matched with stones from next pile, because it is its only adjacent pile. If pile is non-empty and there are no next pile, or next pile is smaller than current, Bob loses. Otherwise, Bob makes current pile empty, and remove corresponding number of stones from next pile. Now Bob plays the same game as if had one pile less, we can remove first pile without changing game. Bob wins if at the moment he reduced game to one pile it's already empty.

Now let's iteratively define array , where — number of stones left in the -th after removing piles, according to greedy strategy. Let , then .

If array contains only positive numbers, then it means that Bob is able to remove piles all the way over. Otherwise, let be the first moment with , this means that Bob was able to remove piles until he meet -th pile and happened, so Bob loses. To check that last pile is empty, we need to check if .

So we have criteria of winning subsequence: for all , .

Let's expand recursive notation of : .

We will solve problem separately for different — left bound of subsegment. Let's define sequence , . It has similar array . We will find first position of negative number in — (). And then count how may zeros are on prefix [, ]. This will give us number of winning subsegemtns with form , sum over all will give us answer for the problem.

Note, that .

Note, that if and only if . Let's divide problem by parity of indexes. Now to find first position of negative number in we should find first position of "number less than x" on suffix of . This can be done many ways, for example, by descending through segment tree (segment tree for each parity).

Note, that , if and only if . Same division of problem by parity. Now to count number of zeros on subsegment of we should count number of "equals to x" on subsegment of . This can be done by storing all positions of each in some container (one for each parity) and binnary search.

Overall complexity of the solution :

Let's define efinegraph with vertexes (, ), where denoting some character, ans is -bit mask of occasions (-th bit is set to if and only if we consider second occasion of in -th string). Not all are possible for some since there could be less than occasions. Note: vertex define choise of character and positions of this character in all strings.

Note, that graph has vertices.

Let's define strict comparison (<) of vertices:(, ) < (, ) if and only if positions chosen by first vertex are stricly lefter than ones chosen by second (for all strings). Let's define another comparison () the same way, but allow some position to be equal. Note: strict comparison is anti-reflexive, both comparison are transitive and this stands ( < < ).

Graph contains directed edges from one vertex to another, if and only if first is smaller by defined comparison. Note: graph is acyclic, because of transitivity of pair comparison.

Note: that for every common subsequence there is unique corresponding path in defined graph and vice versa. So we need to find longest path in this graph. Vertex-length of path will be equal to the length of corresponding subsequence.

We want to calculate (, ) – length of longest path starting from this vertex. This is easy to calulate on DAG, but number of edges is too big. We want to remove some edges without changing values of . Note: if removal of edge doesn't change of its starting point, when it doesn't change at all.

Let's look at arbitrary vertex , that has at least one outgoing edge and some longest path starting from it (it has at least one edge): []. Suppose there exists mask , such that: (c, mask) < (, ) (, ). By the qualities of defined comparisons, we can change second vertex in longest path to (, ).

Now let's find mask for fixed which correspond to choise of leftmost positions righter than positions chosen by (, ). It can be found in time. As we notices earlier, without loss of generality, longest path (with fixed ) goes through this vertex , so we can harmlessly remove all edges going from current vertex to the vertices with character , but diffrent mask. This can be done for every character.

Now graph each vertex has outgoing edges, so can be calculated fast enough. Subsequence itself can be easily found now.

Note: there is no need for graph in solution, it's just abstraction for better understanding.

Note: we don't have to calculate for all vertices, we only need to find for all , it can be proven by applying same logic.

Overall complexity:

The distance from point to segment is equal to the maximum of the distance from point to ray and the distance from point to ray .

Let's fix a point . Now we have to find all points such that distance from every point to the ray is less than .

For every point let's build two tangents from point to the circle with the center in the point and radius . These tangents form an angle . The distance from the point to the ray is less than iff the ray lies inside the angle . So we can build all these angles and intersect them, after that, we only have to check that the ray lies inside the intersection of all angles for all .

Time complexity: .