## 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:

- Sort the array of the lengths of the rows in ascending order
- For each introvert write the number of the next free row and add it to the stack
- 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:

- If the vector is directed at an angle of 90 degrees to the axes, then write the if-s.
- Otherwise, turn the field so that the impact vector becomes (1, 1).
- 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*. - Note that in the infinite tiling of the plane the coordinates of any holes representable in the form (
*k*_{1}·*n*,*k*_{2}·*m*). - Substitute the coordinates of the points in the equation of the line of the ball. The Diophantine equation
*a*·*k*_{1}+*B*·*k*_{2}=*C*is obtained. It is solvable if*C*|*gcd*(*A*,*B*). Otherwise, there are no solutions. - Of all the solutions of this Diophantine equation, we are interested in the smallest on the positive half-axis.
- By finding
*k*_{1},*k*_{2}it is easy to get the coordinates of the corresponding pocket - 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.

waiting translation~

I have a slightly different solution for E. We notice that the movements along the X and Y axis are independent. Therefore, instead of solving a 2D problem, we have to solve two simultaneous 1D problems.

We notice that for the X dimension, if the ball first hits a margin of the table at time

`x_i`

(which will be either equal to`x`

or to`n - x`

, according to the direction of the X speed vector), then it will keep hitting the edges at times`x_i + t * n`

, where`t`

is a non-negative integer. We judge the same for Y. The solution of the problem is found when both axis hit an edge at the same time (therefore, a corner). So we need to solve`x_i + t_x * n = y_i + t_y * m`

.Can you explain how to solve the last equation I am having hard time solving it

It's a classic problem, Linear Diophantine Equation. You then have to bring the solutions to positives, you can check out my submission to see how I did that (there's probably multiple ways).

This is a great way to solve it, thank you very much!

Hope that translation will come soon, I have been waiting for the solution that I can understand one day long.

try google translate extension to translate the page

I don't think google translate is good, I can hardly understand the translation by the google translate.

It seems that the English version has been disappeared. o(╥﹏╥)o

I'm sorry for taking so long. It has happened because of onsite contest in another city.

I think D requires more explanations.

D has very simple solution required sort O(nLog(n)) and linear O(n) operations:

`1) sort given array with indexes, i.e. sort b[] = pair(a[i], i ).`

`2) i = 0 .. N-1, add b[i].second to set of intervals - it's required O(1) operation:`

`Let Left[i] - indicated left index of interval which end point is i.`

`Let Right[i] - indicated right index of interval which start point is i.`

`so when add 'u' element to set of intervals, only required update L[u], R[u], Left[u-1] and Right[u+1].`

``

`3) Let cur_i - number of intervals, cur_l - length of last interval, max_l - maximum length of interval's, max_i - number of such maximum intervals.`

`` if cur_i == max_i -- so all interval's have identical length.``

See solution 38374571 (Note: This solution is not my own idea).

please elaborate your approach!! Still not clear

For example:

`We have 7 10 4 5 numbers`

`indexes: 1 2 3 4`

`1) build index pair array : (7, 1) (10, 2) (4, 3) (5, 4)`

`2) sort (1) array : (4, 3) (5, 4) (7, 1) (10, 2)`

`3) we have empty interval set: {}. or imagine no colored line: 0 0 0 0.`

`4) take first element: (4,3) index is 3. to color line[ 3 ] position. line: 0 0 [ 1 ] 0 - number of intervals = 1. length of last interval = 1, number of longest intervals = 1. --> update answer.`

`5) take second element: (5, 4) index is 4. to color line [ 4 ] :`

`0 0 [ 1 ] 1 -- as you see, left side of 4 also colored, so colored interval will be: 0 0 [ 1 1 ]. - number of intervals = 1 , length of last interval = 2. number of longest intervals = 1, -- update ans.`

`6) take third element: (7,1) index is 1: to color line [1] :`

`[ 1 ] 0 [ 1 1] -- number of intervals = 2, length of last interval = 1. number of longest intervals = 1 (think about).`

`7) take last element : (10, 2) index is 2: to color line [ 2 ] :`

`[ 1 ] 1 [ 1 1 ] -- as you see, left and right side also colored, need increase left side and right side, line will: [ 1 1 1 1] - number of intervals = 1. number of longest intervals = 1 --> update ans.`

thanks for your explanation. great job!!

Is there anyway to sovle D using Tenary Search. As i did i tenaried the K,but i came into a problem that the graph may have the plain field where alot of K satisfied the answer, so how can we solve this or this way is just invalid ?

You can't apply any searching algorithm, because there is no available convex or covariance function with k from 1 to inf.

Can C be solved using DP?

I think, To find the number nodes in a subtree of a node is a DP.

Because we use previously computed results and don't repeat it !!

Which is I guess DP, isn't it?

Correct me I am wrong. Or tell, if there is another interesting solution using DP or anything.

waiting the code link of every problem.

A very clever observation for Div2 C problem is that whenever the number of nodes is odd the answer will always -1 ( Think about it, you can't partition odd vertices into 2 groups of Even+Even ). Now the problem reduces to finding the number of nodes in a subtree, starting from a leaf node. If the node has even number of nodes in the subtree then you can remove the edge going towards it( It shouldn't be the leaf node). Count the nodes having an even number of nodes in the subtree, that will be the answer. The link to my code.

Hi.. Can you explain why you started dfs from a leaf node and not from any arbitrary node?

Yeah my bad! You can start from any node.

Okay, the code in the link you provided, when run with the first sample input and dfs starting with node 1 gives answer as 2 when it should have been 1. Can you please clarify? Link

I dont get why cant we put a person of left most and right most seats?

Can someone explain the question D alomg with the sample test cases?

The English contest doesn't link to the announcement or this editorial. I had to switch to Russian to find this blog. Please fix it, thanks.

thx. Fixed

CAN SOMEONE EXPLAIN ME C MORE CLEARLY ??

for problem shark ,why can't we take k=1 every-time and hence all conditions are satisfied this way?

we need to maximize the segments created with a given k.

For k=1 every element in array will be one segment hence there will be n segments maximum

The travelling day is not considered a segment. Eg 1 2 3 3 3 3 2 1 , K=3 , number of segments are 2

OK thanks

i don't know why am i getting WA in 982D

can someone explain

here

first i am sort the array

then i=1 to n-1 put element in dsu array

if left or right segment is available then i will merge that segment with i

and in end of loop i check (number of segment == length_count[length of current segment ]

and i will update k=a[i+1] (in sorted array)

What is subtree in problem C?

Can someone explain D problem more clearly and detailed please?

In problem C, if both subtrees are even, how will this solution work?

`if ((double)clock()/CLOCKS_PER_SEC>0.95) break;`

Why this line is used in prpblem F??