AGrigorii's blog

By AGrigorii, history, 3 months ago, translation, In English,

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 (k1·n, k2·m).
  5. Substitute the coordinates of the points in the equation of the line of the ball. The Diophantine equation a·k1 + B·k2 = 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 k1, k2 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.

 
 
 
 
  • Vote: I like it  
  • +24
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +33 Vote: I do not like it

waiting translation~

»
3 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like 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).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try google translate extension to translate the page

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think D requires more explanations.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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).

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please elaborate your approach!! Still not clear

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 5   Vote: I like it +2 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          thanks for your explanation. great job!!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can C be solved using DP?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting the code link of every problem.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah my bad! You can start from any node.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CAN SOMEONE EXPLAIN ME C MORE CLEARLY ??

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OK thanks

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is subtree in problem C?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D problem more clearly and detailed please?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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