982A - Row

Seating is the maximum when it does not exist two ones or three zeros together. It is also necessary to carefully process the ends of the series — it is necessary to check that you can not put a person on the most right or the most left chairs.

982B - Bus of Characters

Note that the final introvert-extrovert pairs are uniquely determined, and that using the stack, it is possible to recover which extrovert to which introvert will sit (note that the zeros and ones will form the correct bracket sequence). Then one of the solutions may be as follows:

1. Sort the array of the lengths of the rows in ascending order
2. For each introvert write the number of the next free row and add it to the stack
3. For each extrovert write the last number from the stack and remove it from there

982C - Cut 'em all!

Note that if there is an edge that can be removed, we can do it without any problem. Let's consider such edge that in one of the obtained subtrees it is impossible to delete more anything else, and its removal is possible. What happens if we delete it in the tree? Relative to the other end of the edge, the odd-even balance of the subtree has not changed, which means that the edge has not been affected by further deletions. Which means if we remove it, the answer will be better.

This is followed by a greedy solution: in dfs we count the size of the subtree for each vertex, including the current vertex, and if it is even, then the edge from the parent (if it exists) can be removed.

982D - Shark

Let's sort the array and insert the numbers in the sort order from smaller to larger. Using the data structure "disjoint set union" we can easily maintain information about the current number of segments, as well as using the map within the function of union, and information about the current size of segments (locations) too. Then it remains only to update the answer when it's needed.

982E - Billiard

If you symmetrically reflect a rectangle on the plane relative to its sides, the new trajectory of the ball will be much easier. Linear trajectory if be correct. One possible solution is:

1. If the vector is directed at an angle of 90 degrees to the axes, then write the if-s.
2. Otherwise, turn the field so that the impact vector becomes (1, 1).
3. Write the equation of the direct motion of the ball:  – 1·x + 1·y + C = 0. If we substitute the initial position of the ball, we find the coefficient C.
4. Note that in the infinite tiling of the plane the coordinates of any holes representable in the form (k₁·n, k₂·m).
5. Substitute the coordinates of the points in the equation of the line of the ball. The Diophantine equation a·k₁ + B·k₂ = Cis obtained. It is solvable if C | gcd(A, B). Otherwise, there are no solutions.
6. Of all the solutions of this Diophantine equation, we are interested in the smallest on the positive half-axis.
7. By finding k₁, k₂ it is easy to get the coordinates of the corresponding pocket
8. Rotate the field back if required.

982F - The Meeting Place Cannot Be Changed

Let's assume that solution exists and will looking for solution relying on this assumption. At the end will check found "solution" in linear time, and if it is not real solution, then assumption wasn't right.

If solution exists, then intersection (by vertices) of all cycles is not empty. Let's take any one cycle and call it "main cycle". Let's imagine this "main cycle" as circle directed clockwise. And let's mark all required vertices of intersection of all cycles on this circle (this vertices are the answer).

Consider only cycles which leave "main cycle", come back to the "main cycle", and then moves on the "main cycle" to the begining. Every such cycle when comes back to the "main cycle" DOES NOT jump over any marked vertex of the answer, in terms of direction of the "main cycle" (otherwise answer not exists, but we assumed, that it exists) (if cycle comes back to the same vertex, then by definition it jumped over the whole "main cycle", not 0). Draw the arc from the vertex, where cycle comes back to the "main cycle" till the vertex, where it leaves "main cycle", in the direction of the "main cycle". Vertices not covered by this arc can't be the answer. Intersection of all considered cycles is marked by intersection of all such arcs.

Now was not considered only cycles which some times leave "main cycle" and some times comes back to it. But intersection of such cycle with the "main cycle" is the same as intersection of simple cycles from previous paragraph between adjacent leave/comebacks. Therefore such cycles may be ignored.

For searching the answer we must mark arcs between leaves/comebacks of the main cycle. We do this by starting dfs from all vertices of the "main cycle" and trying to come back to it as far as possible (distance measured as the number of vertices of the "main cycle" between leave and comeback). As were noticed early, cycles does not jump over the answer. Therefore dfses started between boundaries of the answer are aspires to this boundary in direction of the "main cycle". Therefore if we selected the most far vertex in one dfs(u) reached from one start point v0, this vertex for dfs(u) reached from other start point v1 will be the most far too. And we can run all dfses with common "used" array, caching the most far vertex in it.

Finally the solution is so: 1) find the "main cycle" and sort vertices in it, 2) start dfses from vertices of the "main cycle" and mark arcs between finish and start, 3) intersect all arcs and take answer from intersection, 4) verify answer by deleting it from graph and trying to find any other cycle, if it founded, then assumption was wrong and solution doesn't exists else print the answer.

Hello, Codeforces!

I'd like to invite you to Codeforces Round #484 (Div. 2). It'll be held on May/17/2018 19:35 (Moscow time) and Div. 1 participants can join it out of competition. Please pay attention that round starts in the unusual time!

Me and Andrey API Pikas prepared the tasks for this round.

Great thanks to Nikolay KAN Kalinin for helping us preparing the contest, to Mikhail MikeMirzayanov Mirzayanov for the great Polygon platform and Codeforces and also to Kirill kittylover Samelyuk, Nikolay Apollon76 Permyakov, Dmitry Krainov_Dmitry Krainov, Andrey GreenGrape Rayskiy and Alexey Um_nik Danilyuk for writing solutions.

You'll have to solve six tasks in two hours. The scoring distribution will be announced later

Good luck!

UPD Score distribution 500-1000-1500-2000-2500-3000

UPD2 Congratulations to the winners of the division 2:

1. Kotori_Is_My_Wife

2. vosptu

3. ez_zkj

4. relativity

5. iordache.bogdan

And also our congratulations to the winners of both divisions:

1. Claris

2. Benq

3. Kotori_Is_My_Wife

4. kmjp

5. vosptu

UPD3 The editorial will be published tomorrow.

UPD4 Editorial

676A - Nicholas and Permutation

All what you need to solve this problem — find the positions of numbers 1 and n in the given array. Let's this positions equal to p₁ and p_n, then the answer is the maximum of 4 values:

Asymptotic behavior O(n).

676B - Pyramid of Glasses

The restrictions in this problem allow to simulate the process. Let the volume of one wineglass equals to 2ⁿ conventional units. So the volume of the champagne surpluses which will stream to bottom level will always integer number. So let's pour in the top wineglass q * 2ⁿ units of champagne, and then we have following case: if in the current wineglass is more champagne than its volume, let's make surplus = V_tek - 2ⁿ, and add surplus / 2 of champagne in each of the two bottom wineglasses.

Asymptotic behavior O(n²).

676C - Vasya and String

This problem can be solved with help of two pointers. Let the first pointer is l and the second pointer is r. Then for every position l we will move right end r until on the substring s_ls_l + 1... s_r it is possible to make no more than k swaps to make this substring beautiful. Then we need to update the answer with length of this substring and move l to the right.

Asymptotic behavior O(n * alphabet).

676D - Theseus and labyrinth

It is easy to understand that we have only 4 states of the maze. How to solve this problem if there is no any buttons? It is just bfs on the maze (on the graph). Because of buttons we need to add to graph 3 additional levels and add edges between this levels. After that we need to run bfs on this graph and find the length of the minimum path if such exists.

Asymptotic behavior O(n * m).

676E - The Last Fight Between Human and AI

In this problem we have two main cases: k = 0,  k ≠ 0.

1. Case when k = 0. Then the division of the polynomial to the x - k depends only of the value of a₀. If a₀ is already known then we need to compare it with zero. If a₀ = 0 then the human wins, otherwise the human loses. If a_i is not known then win who make the move.

2. Case when k ≠ 0. Here we have two cases: all coefficients already known. Then we need to check x = k — is it the root of the given polynomial. Otherwise who will make the last move will win. Let we know all coefficient except one. Let this coefficient is the coefficient before xⁱ. Let C₁ is the sum for all j ≠ i  a_jk^j and C₂ = kⁱ ≠ 0. Then we have the equation a_i * C₂ =  - C₁ which always have the solution. If the human will make the last move he need to write the root to the place of the coefficient, otherwise computer will write any number, but not the root.

Asymptotic behavior O(n).

Thanks to all! It was cool and so interesting!