155A - I_love_\%username\%

You should do what is written: go through the sequence and count the elements which are greater or less than all of its predecessors. We don't even have to store the whole sequence, just the current minimum and maximum. Complexity — O(N), but squared still works fine.

155B - Combination

Clearly, we can play the cards with b_i > 0 first as each of them gives at least one extra move. After that, the number of extra moves left doesn't depend on the order of playing. The left cards all have b_i = 0, so we play those of them which have larger a_i. Simpler version of this solution: sort all the cards by decrease of b_i, if equal — by decrease of a_i, and then go through the sorted array from beginning to end, simulate the counter and sum up the points. Remember not to fall over the edge of array if the sum of b_i's is larger than the number of cards. Complexity — O(n log n) (or O(n^2), if using bubblesort, which is still accepted).

155C - Hometask

154A - Hometask

Constriction saying that no letter occurs in more than one forbidden pair lets us to use the greedy solution. Without the constriction the problem is quite hard.

Let's look at all occurences of letters from some pair. They form several continuous substrings divided by some other letters. We can note that in optimal solution the substrings cannot merge, 'cause we can leave at least one letter in each of such parts. So, for each of these substrings problem is solved independently. To resolve conflicts within a substring, one has to remove all letters of some kind, 'cause while there are letters of both kinds there will be conflicts. Clearly, from each continuous substring of forbidden letters we remove all letters of the kind which number is less than another.

The answer can be counted in O(kN) with k runs through the string.

155D - Colliders

154B - Colliders

The clueless solution ''store all the enabled numbers and compare each new number with each of them'' works too slow, as we can add all the prime numbers below n, number of which is O(n / log n).

We can note that for each number k > 1 at any time no more than one collider is turned on which number is divided by k. Let us store an array which has in k-th element the number of turned-on collider which is divided by k, on 0 if there is no such at the moment. To enable the collider with number q we can look over q's divisors and check whether all the array's elements with these numbers have 0's. If some of them has a positive integer, that's the number of collider we conflict with — we can just print it and go on. Otherwise, we have to put q into all the overlooked elements.

This works in O(M sqrt(N) + N). There's faster solution as we can store all of the above only for prime divisors. Total size of the prime divisors list for number from 1 to N is O(N log log N). Thus we have a solution with complexity O(N log log N + M log N), as the number of prime divisors of k doesn't exceed log k (exact upper bound — log k / log log k * (1 + o(1)).

155E - Double Profiles

154C - Double Profiles

We want to count the number of pairs of vertices in a undirected graph which neighbours' sets are equal up to these vertices. To count the pairs which sets of neighbours are equal we can hash these sets (for instance, count the polynomial hash of adjacency matrix row) and sort the hashes. Than we have to add the pairs of doubles which have an edge between them.

We can note that there are no more such pairs than there are edges in the graph. So we can iterate through edges and check hashes for equivalence considering the presence of the edge (in case of polynomial hash we just add some degrees to them and then compare them). Other solution was to count another version of the previous hash, now adding a loop to each vertex, and to count the number of pairs just like in the previous case.

Moreover, we could try and sort the whole lists of adjacencies (which previuosly should be sorted too). As their total size is 2M, this works fine too, but needs an accurate realization. Hash solution complexity — O(N log N + M).

154D - Flatland Fencing

As the moves choices are symmetrical for both players, if one player can reach another in one move from some disposition, the other player also can reach the first. So, if we are allowed to stand in one place (i.e. a <= 0 <= b), we can just stand still and wait for another player to come. If she wants to win, she will have to step within our reach before that so that we can get her. So, if the first player doesn't reach the second initially, there is a draw as no one can ensure her victory. Thus we finished the case a <= 0 <= b: either the first player wins in one move, or there is a draw.

Now, let a and b have the same sign. Denote d = x2 — x1. If a <= b < 0, we can go to the situation with (d, a, b) = (-d, -b, -a), which is similar to the initial. So later on 0 < a.

So we have the following game: there are integers d and 0 < a <= b. In one move each player can substract an arbitrary integer number from segment [a; b] from d. The player who gets d = 0 after her move wins. If at some point d < 0, a draw is proclaimed (as no one can win anymore).

The interesting case is d > 0. Note that if d mod (a + b) = 0, the second player can use the symmetrical strategy: for every first player's move x of she can make a move a + b — x, and support the condition d mod (a + b) = 0. As d decreases, the second player eventually moves to 0 and wins. So, if d mod (a + b) = 0, the second player wins. Thus, if d mod (a + b) is in [a; b], the first player wins, as he can reduce the game to the previous case by letting the second player move in the losing situation.

What about all the other situations? Turns out all the other position are draws. We prove that by induction: let d = k(a + b) + l, where l in [0; a + b). Case l = 0, as we just proved, is losing, cases l in [a; b] are winning. If l is in [1; a — 1], we cannot move to losing position (we use the induction assumption for lesser k), but after the move a, we move to the draw position (if k = 0, we move to the negative number, otherwise we get into [(k — 1)(a + b) + b + 1; k(a + b) — 1] segment, every position from which is a draw by assumption). Similarily for l = [b + 1; a + b — 1], move to a draw — b.

154E - Martian Colony

We have to find the area of intersection of all circles containing the given set of points (it's clear that the intersection has the least area, and we have an unlimited number of circles). First, what shape does such an intersection have? Its border contains some circle arcs of radius R meeting at some points of convex hull. If we determine which points are present in the border, we can count the total area as the sum of polygon area and several circle segments.

So, how to determine those points? It's clear that if there is a circle of radius R containing all the points and having some of them on its border, then this particular point is present in the border of the intersection. If we fix the circle and move it in some direction, it eventually will run into some point — so we can find at least one point. Then we can perform something similar to ''present wrapping'' — go around the convex hull and support the set of the border points while controlling the relative position of the arcs. While this solution is fast, it is very hard to write and it was not assumed that it should be written during the contest.

There is much simpler solution based on quite different idea. We build the convex hull of the set so that no three points lie on the same line. Let us take the very large R so that every point of convex hull is present in the intersection border. As we gradually decrease R, some points will start to disappear from the border. How to determine which point falls out first? For point u in the convex hull denote its left and right neighbours l(u) and r(u). It's clear, that the first point to disappear will be such point u which has the largest radius of circle going through u, l(u) and r(u) (when R becomes equal to this radius, two arcs will merge into one in point u, while all the other will have joints in them; we will call this radius critical for u). Then we remove u from convex hull and do not take it into account. We repeat while the largest critical radius is larger than R. The rest points will be exactly the points forming the border.

How to do this fast? Note that when we remove some point from the set the critical radii will change only for its two neighbours. Let us store a priority queue containing critical radii along with point numbers. On every iteration we extract the largest critical radius, remove the corresponding point from the set, and refresh the information about the neighbours in the queue. We repeat while the largest radius is greater than R. As we just simulate the process of R decreasing, everything works correctly. The complexity of this procedure is O(n log n), as we have no more than n iterations and on every iteration we perform the constant number of operations with the queue of size at most n.

There is an unclear case, when the border contains only two points. Then on the last phase we have three points in the set and the algorithm doesn't have a clue which one to remove as they have equal critical radii. But we know that the triangle with vertices in these points is obtuse-angled, as we cannot shrink the circumcircle of an acute-angle triangle, as that would contradict with the circle existence condition. So we have to remove the point with the obtuse angle.