527A - Playing with Paper

It’s easy to see that described process is equivalent to the following loop:

while a > 0 and b > 0:
    if a ⩾ b:
         a = a - b
    else:
         b = b - a
    ans = ans + 1

But such naive approach will obviously lead to verdict TLE, since it makes ~10, 2015 - 03 - 19¹² operations even on the third sample test. The key idea is to replace repeating subtraction operations with integer division operations. This leads to the logarithmic-time solution that looks similar to the Euclid algorithm:

while a > 0 and b > 0:
    if a ⩾ b:
        ans = ans + a div b
        a = a mod b
    else:
        ans = ans + b div a
        b = b mod a

527B - Error Correct System

The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease at all.

The decrease by two is possible if there are two positions with the same two letters in two strings but that appear in different order (like “double” <-> “bundle”).

If there are no such positions, then we just need to check that we may decrease the distance. This can be done by just “fixing” the character that stands on the wrong position, like in “permanent” <-> “pergament” (here n stands in wrong pair with m, and there is also unmatched m, so we may fix this position).

Otherwise, the answer is to keep everything as it is. Implementation can be done by keeping for each pair (x, y) of symbols position where such pair appears in S and T and then by carefully checking the conditions above.

528A - Glass Carving

Obviously the largest glass piece at any moment is the one that is product of the largest horizontal segment by the largest vertical segment. One of the possible solutions is to carefully implement what described in the statement and keep all horizontal segments and all vertical segments in priority queue or std::set, or some logarithmic data structure. This solution works in .

But there is also a nice linear solution if we answer all queries in reverse order. Suppose segments are not cutting, but merging. In this case we may keep the horizontal and vertical cut lines in double-linked lists and track the current maximum (that can only increase and become equal to the newly-merged segment each time). This solution works in O(k + n + m).

528B - Clique Problem

One may think that this task is about graph theory, but it after some investigation and several equivalent changes in task statement it can be reduced to the well-known greedy problem.

Initially you have that points may lie together in a set if they are not too close, i. e. |x_i - x_j| ≥ w_i + w_j. This is obviously equivalent to the following condition. Let’s consider interval of radius w_i with center in point x_i and call this interval to be the interval of point i. Then the statement actually says that no two such intervals should be intersecting.

This task is well-known and can be solved greedily after sorting segments in ascending order of right endpoint:

Sort segments S in ascending order of S.x + S.w

last = 0
ans = 1
for i = 1..n - 1:
    if S[i].x - S[i].w ⩾ S[last].x + S[last].w:
        last = i
        ans = ans + 1

It’s easy to prove that this solution is correct. Among all ways to choose first k segments, the best way is the one that minimizes x-coordinate of the right endpoint of the last segment (since it restricts us in the least possible way).

528C - Data Center Drama

Problem legend asks you to add minimum number of edges to the given connected undirected graph (possibly, with loops and duplicating edges) and choose direction for its edges so that both the incoming and outgoing degrees of all vertices are even.

First idea is that the resulting graph before we choose the direction (but after we added some edges) will contain Euler circuit, since all degrees are even. That’s almost what we need: if we have an Euler circuit that contains even number of edges, we may direct them like following: a <- b -> c <- d -> e … It’s easy to see that each vertex appearance in this cycle adds 2 to its ingoing or outgoing degree, so the resulting degrees will be even.

But if the Euler circuit is odd (meaning that there is odd number of edges in the graph), we must add some extra edge to the graph before we continue, the easiest way is to add a loop from vertex 0 to itself, since it doesn’t affect the Euler tour, but now tour length is even, so everything is ok.

Now we should think how to add edges optimally. It’s easy to see that the optimal way is to first fix all odd degrees of vertices (i. e. combine all odd vertices by pairs and put an edge in each pair), and then, possibly, add an extra loop as described above. The last part is to actually find an Euler circuit, and to print the answer.

528D - Fuzzy Search

There were issues with this task. Intended constraints were actually n, m, k ≤ 500000, and the intended solution was using Fast Fourier Transformation, that leads to running time. But unfortunately the statement contained wrong constraints, so we reduced input size during the tour. Nevertheless, we will add the harder version of this task and you will be able to submit it shortly.

Key idea is to reduce this task to a polynomial multiplication. Let’s solve the task in following manner. For each position i of the S for each character c from “ATGC” we will calculate match(c, i) that is equal to the number of c characters that have matching symbol in S if we put string T in position i. Then the criteria for us to have an occurrence at position i is that match(A, i) + match(T, i) + match(G, i) + match(C, i) == |T| (that means exactly that each character from T being put at position i has a corresponding character in S).

Now let’s find out how to calculate match(c, i). Let’s keep only c characters and “not c” characters in both strings and denote them by 1 and 0 respectively. Let’s also spread each 1 in string S by the distance k to the left and to the right. For example, k = 1 for the sample string AGCAATTCAT and the character A corresponding bit vector will be 111110111, and for the character C it will be 0111001110. This bitvector can be calculated in O(n) by putting two events “+1” and “-1” in string S in positions x - k and x + k for each 1 in original string S and then sweeping from left to right over the string S and processing those events.

Now our task is reduced to searching all positions where the bitvector T is the submask of the bitvector S. In constraints n, m, k ≤ 200000 this can be done by using bitsets in O(m(n - m) / 32). Nevertheless, this task can be seen as calculation of polynomials S and reversed(T) product. We will keep this as an exercise for those who decide to submit the harder version of this task.

528E - Triangles 3000

Let’s draw a bounding box that contains all intersection points. Let’s fix a triangle and consider three angles shown on the picture. Calculate area of intersection of those area with the bounding box and call this area to be the “area of an angle”. Then it’s easy to see, that those three angles are complement to the triangle itself in the bounding box, i. e. triangle area is bounding box area minus three angle areas.

This leads us to the idea how to solve this task by carefully calculating for each possible formed angle on the plane, how much times does it appear in total answer if we sum all values like (S - angle_area(a, b) - angle_area(b, c) - angle_area(c, a)) over all triples (a, b, c) of lines.

Actually, the angle is considered as many times, as many lines there are that intersect both sides of its right adjacent angle. So, our task is reduced to calculate for each angle on plane how much lines intersect its sides (i. e. its rays).

This can be done in by fixing the first side of the angle and then adding lines in ascending order of polar angle, and then by keeping the number of lines that intersect the base line to the left and that intersect the base line to the right. Key idea is that the exact of four angles formed by the pair of lines (a, b) that is crossed by some third line c, can be determined by two numbers: its polar angle alpha and its crossing with a coordinate x. Further details are shown on the picture below.

There is also a nice short O(n²) solution from enot110 here.