lior5654's blog

[Discussion Thread] RMI 2020

By lior5654, history, 3 years ago, In English

Opening this thread to discuss Romanian Masters of Informatics (RMI) 2020 Problems & Results.

Hope everybody had a great competition!

http://rmi.lbi.ro/rmi_2020/

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

»
3 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

My results:

brperm — 83

floppy — 27

peru — 49

total (d1) — 160 (49th/198th)

zerosum — 61

nicelines — 11

arboras — 24

total (d2) — 96 (58th/198th)

total — 256 (??th/198th)

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

    Wait, How do you know your place today?

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

      One of my coaches sent me the table from the system some time after the contest ended. ofcourse, second day is not final because of jury. these are unverified results, but most likely wont change.

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

    Update: 20 points off from silver medal -_-

    High bronze.

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

My results:

brperm — 0
floppy — 100
peru — 0
total (d1) — 100

zerosum — 22
nicelines — 88.76
arboras — 24
total (d2) — 134.76

total — 234.76

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

    88.77 on nicelines is megaorz

    btw what happened on the first day that made you not take testcases on q2 and q3?

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

      I was trying to get 100 on brperm, but I failed.

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

        That problem is fucked up, 83 is n^2 bruteforce, broken testcases

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

    how to 88.77 on nicelines

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

      Let $$$k = 20001$$$.
      The graph of $$$query(k, y+1) - query(k, y)$$$ contains $$$n+1$$$ horizontal segments; a new segment begins if there's a line that goes through $$$(k, y)$$$. So you can get all $$$a[i]$$$ and $$$b[i]$$$ with binary search on the endpoints of those segments. That's around $$$3000$$$ queries.

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

        It's not about 1500 queries. My solution uses 2400 queries and gets about 93 points. My idea is the same as yours but I did some constant factor optimizations on the binary search which allowed me to squeeze 5 more points.

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

My results are:

brperm 83, floppy 100, peru 0 -- 183 day1

zerosum 100, nicelines 0, arboras 24 -- 124 day2

307 total

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

    floppy 100 with a cartesian tree? I wish I knew what that is before the contest. on the go I invented a similar concept but wasn't full and good enough :/

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

      I generated the max stack (1 = insertion, 0 = removal), then a "valid" permutation with a topological sort on the graph generated by the max stack.

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

        I thought of saving the results of running maz stack but that was nlogn. not the insertions and deletions themselves. smart idea!

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

      To save the data in 2n bits, I found the highest value and used it as the root of a tree, then I divided the array recursively into left and right subtree, always choosing the highest value of the interval. Then, for each node of the tree in bfs order, I would save two bits, one is 1 if the node has a left child, the other is 1 if the current node has a right child. I would then reconstruct the tree, knowing that each node has a higher value than its children and its in-order traversal gives the original order of the array. For range max queries, I used a sparse table. I can send you a picture of the code if you want.

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +43 Vote: I do not like it

My results:

bperm — 83; floppy — 28; peru — 18; total(d1) — 129

zerosum — 22; nicelines — 11; arboras — 24; total(d2) — 57

total — 186 (bronze)

Just to clarify — I am 14 years old (7th grade)

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

So during the contest I came up with this solution for Arboras. However, I couldn't code it in time, so I don't know whether it's correct of not, so if someone could comment who knows the solution, would be appreciated.

First, it's not hard to see that all the values that change in a query lie on a path from the changed edge upwards. So let's apply heavy-light decomposition on the tree. For each chain, we keep a set of positions, where the longest path to a leaf starting from this vertex doesn't go through the heavy edge. Let's call this positions breaking-points.

When updating a vertex, go upwards from the changed edge. Call a vertex interesting if it is either the vertex where we change the chain when going upwards, or if it's a breaking-point. We can calculate the value-change on this points seperately. The value-change of the points between these interesting vertices can be updated easily, since the value-change of all of them is the same.

There are $$$\mathcal O(log \, n)$$$ interesting vertices of the first type on the path upwards. But we may encounter many vertices of the second type. Now comes the insight: Each time we encounter a point of interest of the second type, we either remove it from the set, or there isn't any value to change above it (since there is another longer path we could take). In the beginning, there can be at most $$$\mathcal O(n)$$$ breaking points, and in each update, we only add at most $$$\mathcal O(log\,n)$$$ breaking points, because we only change the chain (of the heavy-light decomposition) at most $$$\mathcal O(log \, n)$$$ times, and we can only add a breaking-point in an update when switching the chain. So, amortized, we check at most $$$\mathcal O(n \, log \, n)$$$ interesting points. With a segtree, the values can be maintained in $$$\mathcal O(log\,n)$$$, giving us a total complexity of $$$\mathcal O(n\, log^2 \, n)$$$

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

    An arguably easier way to get 100 on Arboras: Code an $$$O(q \cdot height)$$$ with various constant factor optimizations and breaks, most notably using hld dfs order to only have $$$O(n$$$ $$$log$$$ $$$n)$$$ cache misses and the unroll loops pragma. My first submission that wasn't WA only TLEd on test 8 of the last subtask, which I fixed by removing 1 array and slightly reducing the number of operations I do which allowed me to pass it in 2.871 s.

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

How to solve day1 problem3 Peru?

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

    If you know a data structure that supports:

    insertion from 1 aide (like a stack) deletion from both sides (like a doubly linked list) max query

    in O(q) then I have 100

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

how do you solve day2 problem1 ZeroSum?

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

    First of all, you must notice that the subarray between $$$a_i$$$ and $$$a_j$$$ has sum zero iff the sum of the elements between $$$a_1$$$ and $$$a_{i-1}$$$ is equal to the sum of those between $$$a_1$$$ and $$$a_j$$$. Hence we can reduce our problem to an easier one. We replace our array with its prefix sums array, i.e. $$$b_i=\sum_{j=1}^ia_j$$$. What we must do now is, for each interval, finding the maximum amount of pairs $$$f_i,s_i$$$ such that $$$b_{f_i-1}=b_{s_i}$$$ and the segments $$$f_i,s_i$$$ and $$$f_j,s_j$$$ don't intersect for every $$$i,j$$$ such that $$$i\neq j$$$. This is a quite known problem and can be solved greedily, by simply taking the pairs of equal elements which has the leftmost right element and repeating this process over and over until we reach the end of the queried segment. Although, this has a time complexity of $$$O(N)$$$ for each query, which gives TLE. We can speed up this procedure. For every index $$$i$$$ we store the minimum index $$$j>i$$$ such that $$$b_i = b_j$$$. This can be done easily in $$$O(NlogN)$$$ using a set. What we can do next is building a sparse table on those values and binary search the answer for each query. Unfortunately, using a standard sparse table causes MLE, so you must use a sparse table with a base greater than 2 (My solution using base 4 uses 20.0 MiB of memory, which is just enough to get 100/100). If you have any doubt feel free to ask.

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

      Thanks, had a similar idea but somehow messed it up for the query part

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

You never know true pain until you get 13 on bperm because you didn't try N^2 for subtask 2

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

My results: floppy — 28
bperm — 100
peru — 49
zerosum — 100
nicelines — 11
arboras — 100
total — 388

Personal opinion: I like problem bperm, but it completely ruined the contest. There are way to many people, who solved it with some O(N^2) solution + optimizations for subtask 3.

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

    What was the intended solution for brperm?

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

Wow I didn't know an RMI existed :O just knew of the RMM (math version).

Similar to RMM, is participation by the top individuals from the countries? And are they highschoolers like RMM?

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

    Yes and yes. This year there were more people than usual because it was online.

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

Where can you download the tests/graders/upsolve the tasks?

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

You can solve all problems here: https://oj.uz/problems/source/452

→ Reply