Opening this thread to discuss Romanian Masters of Informatics (RMI) 2020 Problems & Results.
Hope everybody had a great competition!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.11.2024 13:13:12 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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)
Wait, How do you know your place today?
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.
Update: 20 points off from silver medal -_-
High bronze.
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
88.77 on nicelines is megaorz
btw what happened on the first day that made you not take testcases on q2 and q3?
I was trying to get 100 on brperm, but I failed.
That problem is fucked up, 83 is n^2 bruteforce, broken testcases
I knew it only at the end of the contest.
how to 88.77 on nicelines
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.
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.
My results are:
brperm 83, floppy 100, peru 0 -- 183 day1
zerosum 100, nicelines 0, arboras 24 -- 124 day2
307 total
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 :/
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.
I thought of saving the results of running maz stack but that was nlogn. not the insertions and deletions themselves. smart idea!
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.
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)
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)$$$
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.
How to solve day1 problem3 Peru?
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
how do you solve day2 problem1 ZeroSum?
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.
Thanks, had a similar idea but somehow messed it up for the query part
You never know true pain until you get 13 on bperm because you didn't try N^2 for subtask 2
Missed bronze because of that =(
I feel you my man
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.
What was the intended solution for brperm?
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?
Yes and yes. This year there were more people than usual because it was online.
Where can you download the tests/graders/upsolve the tasks?
You can solve all problems here: https://oj.uz/problems/source/452
Please fix Peru. All subtasks have N=2.5 million, even the one supposed to have N<=2000. I wasn't able to find another OJ to submit the problem :(