SirirNicheBirirDokan's blog

GP of Eurasia 2018-2019
By SirirNicheBirirDokan, 6 years ago, In English

Let's discuss problems.

How to solve the geography problem?

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

Comments Comments (40)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

How to solve problem 2, 11?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    The last problem: if after 6 hours the rocket is higher than the eclyptic, send it then; else the rocket crosses eclyptics, and that moment can be found with binary search; to find the position after t seconds, rotate point (0,-cos(phi),sin(phi)) by t/day_length*2pi around z-axis, then rotate it by -alpha around y-axis, and z-coordinate will be oriented distance to the eclyptic

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    Problem 11. Trigonometry. Find ratio between A1-L and A2-L (tangets). Then calculate arcsine.

    → Reply
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

How to solve 2, 6 and 7?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    2) Just determine time when item starts decoding and time when it's leaving the buffer than you get segments [enters_buffer, exits_buffer]. After just found point in time where maximum segments intersects. How to find this "enters_buffer": iterate from the end to begin and keep time when current item enters buffer, when iterating just update this smth like enters_buffer = min(enters_buffer, i * d); enters_buffer -= time_of_decoding[i]. There is a case when we have "IBBI" we know that 3 must be decoded before 1 so in our loop we skip 3 and update "enters_buffer" after iterating 1. So how to find "exits_buffer": for every item u iterate for each item v where v depends of u and choose maximum of enters_buffer[v] + time_of_decoding[v]

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    6) First of all, parse all input and calculate number of fields which take 1, 2, 4 and 8 bytes.

    For minimal size we can order fields in non-increasing order and then add padding so that the total size is divided by max-size field.

    Maximal and average sizes can be found using dynamic programming. Let's consider dp[r][c1][c2][c4][c8] be avg/max size of current structure where r is current size mod 8 and cX -- number of remaining fields with size X. When calculating average we also maintaining probability to get to each state. Transitions are done by inserting fields of all possible sizes. Then, for maximum we need to find max for all r among dp[r][0][0][0][0] and average equals sum of all dp[r][0][0][0][0] + probability[r] * padding(r) where padding(r) -- is padding we need to add to the resulting structure having remainder r.

    The dynamics can be optimized by using only two layers

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      But i thought that numbers can be very big when we calculating avg so we can have loss of precision. Why they are remaining small?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As long as we have only 100 fields, maximal total size is 800 and average is less or equals to it

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, but probability equals to x over y, I thought that y can be very large, and x very small

          → Reply
»
6 years ago, # |
  Vote: I like it +61 Vote: I do not like it

I don't have ever seen single interesting problem, which is related to computer architecture with long description of buffer or memory, and I think this time is no exception...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I don't have ever seen single interesting problem with long description, and I think this time is no exception...

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 3?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Kuhn or flows. With one of them it’s an easy task

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Discard all packages that has at least one version that doesn't make conflict with any other package.
    Now you are left with some packages where all versions make conflict with some other package. You want to choose exactly one version from each package, such that you also choose no more that 1 version from a conflict set. That is exactly like finding a matching, where all left nodes are included.
    So, for this part, make a bipartite graph, with left nodes representing packages, and right nodes representing conflict sets. Add and edge between X and Y, if package X is in conflict set Y. Then answer is Yes, iff max bipartite matching = number of packages.
    Solution can be constructed by looking at matched edges, and taking a version that is in both package and conflict set.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1.At first, check if there are any versions, which are not included in any conflict. Update answer for those programms.

    2.Then, make a bipartite graph with conflicts in the left part and programms(which you don't have answers yet) in the right(and write a version on the every edge for output). Find maximum matching in that graph. That's it.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Greedy algorithm with random.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 9?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    for each i = 0, 1, ..., n / s memorize the segments that are near point i * s, to answer the query with point x look at these ssegments at x / s - 1, x / s and x / s + 1; i took s as 4

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Actually I only make all the coordinate 1E6 times larger and use a Segment Tree and Pass the problem. So I am wondering what's the official solution idea, Since my solution has nothing to do with the randomability.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm, interesting. What kind of Segment Tree did you use? Don't you need to squeeze coordinates before?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        My Segment Tree's range is [-1E11,2E11]. You don't have to squeeze coordinates if you maintain the Segment Tree by the way that only generates necessary nodes.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well... The canonical solution is to build a segment tree with standard segment-nodes [k;k + 2s) for 2s|k. For each input interval, first find the best matching level s, then save its index into one or two segment-nodes which it intersects in this level. For a point query, go through all the nodes containing the point, and check all the intervals in it. This gives O(N) space in worst case and average O(NlogN) time with the provided distribution.

      The much simpler solution is the one described by polingy below, which needs O(NlogN) time and space on average.

      Of course, all sorts of other segment trees work as well.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    We solved it with "naive" algorithm.

    For every interval, [L, R] add it to vector for indices , to answer point query x, look at the vector corresp. to and just check how many intervals x lies inside.

    It's not hard to show that expected runtime is ; I don't know how to show that it's quick with high probability.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      it is quick because the average length of any interval is 4

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      It was said in the statement that radius of a segment R is generated with this — . So expected value of R is —

      .

      So, sum of lengths of segments is ~ .

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We solved it with "interval tree"

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can also be solved with Binary Search Tree. Notice that number of segments that contains X = total number of segments — (number of segments that has right side  < X + number of segments that has left side  > X). So we can use two BSTs, one for storing left sides another for right, and keep sub-tree sum for the ids and size of sub-trees in each node. Since the data is random, so we don't need BBST like Splay-Tree / Treap, normal BST is enough.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone WA on 8th testcase of problem 7?

And I am also wondering is this Gp of Eurasia or Gp of Siberia? Quite comfusing.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I could pass the 8th test only by rewring computation from floating numbers to integers. But unfortunetaly, couldnt have time to squeze in TL.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

About testcases in 4:

Store the sets for each component with indexes of bad irredeemable connection. When you need to merge it, first check from smaller set that there is no intersection. Then add small set to biggest. This solution should got TL, but during checking if we break inside the loop, when we found intersection got to AC.

But it is easy constract test case where it should have O(n^2) comparison. Isnt it?

I thought key idea would be dont compare two components more than once. But to get AC it is not needed. Is it bad testcases?

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve 4?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use dsu, but while unioning sets, append one with lesser sets of conflict vertices to one with bigger; after unioning sets, if you appended B to A, then for each conflict vertex in B's set change B to A in that set

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have two solutions of problem F that differ only in the following lines:

Solution 1:

scanf("%*[^;]");
scanf(";");

Solution 2:

scanf("%*[^;];");

The first solution gets OK while the second fails on test 1. Can someone explain that?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 10?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Dijkstra on hex graph: build graph -> don't forget to add reverse edges for rivers -> run Dijkstra -> AC.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the state of vertex?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        dist[x][y] = (minimal number of steps, maximum energy left)

        → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Thanks problemsetters for beautiful combination of ML and TL in problem 6 !!!11!11 I can't use neither static array nor vector) Screenshotfrom2018-10-0200-33-28.png

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    You can emulate many dimensional arrays on 1-dimensional. It is very easy.

    → Reply