FiveSixFiveFour's blog

By FiveSixFiveFour, history, 5 months ago,

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/

• +60

 » 5 months ago, # | ← Rev. 3 →   +23 My results:brperm — 83floppy — 27peru — 49total (d1) — 160 (49th/198th)zerosum — 61nicelines — 11arboras — 24total (d2) — 96 (58th/198th)total — 256 (??th/198th)
•  » » 5 months ago, # ^ |   +13 Wait, How do you know your place today?
•  » » » 5 months ago, # ^ |   +13 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.
•  » » 5 months ago, # ^ |   +15 Update: 20 points off from silver medal -_-High bronze.
 » 5 months ago, # | ← Rev. 3 →   +1 My results:brperm — 0 floppy — 100 peru — 0 total (d1) — 100zerosum — 22 nicelines — 88.76 arboras — 24 total (d2) — 134.76total — 234.76
•  » » 5 months ago, # ^ |   +5 88.77 on nicelines is megaorzbtw what happened on the first day that made you not take testcases on q2 and q3?
•  » » » 5 months ago, # ^ |   0 I was trying to get 100 on brperm, but I failed.
•  » » » » 5 months ago, # ^ |   +21 That problem is fucked up, 83 is n^2 bruteforce, broken testcases
•  » » » » » 5 months ago, # ^ |   +2 I knew it only at the end of the contest.
•  » » 5 months ago, # ^ |   0 how to 88.77 on nicelines
•  » » » 5 months ago, # ^ | ← Rev. 4 →   +5 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.
•  » » » » 5 months ago, # ^ |   +25 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.
 » 5 months ago, # |   +27 My results are:brperm 83, floppy 100, peru 0 -- 183 day1zerosum 100, nicelines 0, arboras 24 -- 124 day2307 total
•  » » 5 months ago, # ^ |   +13 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 :/
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » » 5 months ago, # ^ |   0 I thought of saving the results of running maz stack but that was nlogn. not the insertions and deletions themselves. smart idea!
•  » » » 5 months ago, # ^ |   +13 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.
 » 5 months ago, # | ← Rev. 4 →   +43 My results:bperm — 83; floppy — 28; peru — 18; total(d1) — 129zerosum — 22; nicelines — 11; arboras — 24; total(d2) — 57total — 186 (bronze)Just to clarify — I am 14 years old (7th grade)
 » 5 months ago, # | ← Rev. 3 →   +36 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)$
•  » » 5 months ago, # ^ |   +39 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.
 » 5 months ago, # | ← Rev. 2 →   +24 How to solve day1 problem3 Peru?
•  » » 5 months ago, # ^ |   -10 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 queryin O(q) then I have 100
 » 5 months ago, # |   +8 how do you solve day2 problem1 ZeroSum?
•  » » 5 months ago, # ^ |   +12 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.
•  » » » 5 months ago, # ^ |   +8 Thanks, had a similar idea but somehow messed it up for the query part
 » 5 months ago, # |   +24 You never know true pain until you get 13 on bperm because you didn't try N^2 for subtask 2
•  » » 5 months ago, # ^ |   +13 Missed bronze because of that =(
 » 5 months ago, # |   +29 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.
•  » » 5 months ago, # ^ |   +9 What was the intended solution for brperm?
 » 5 months ago, # |   +8 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?
•  » » 5 months ago, # ^ |   +8 Yes and yes. This year there were more people than usual because it was online.
 » 5 months ago, # |   0 Where can you download the tests/graders/upsolve the tasks?
 » 12 days ago, # |   +3 You can solve all problems here: https://oj.uz/problems/source/452