RMI 2021 is taking place on December 15-17. Day 1 was today, tasks are here:
Feel free to discuss and give feedback here.
The scientific committee preparing the tasks: proflaurian, alexandra_udristoiu, petrescu, AndreiCotor, georgerapeanu, Ionel-Vasile Pit-Rada, tinca_matei, PopescuMihai, MirceaDonciu, popovicirobert, Ruxandra985, tamionv, VladGavrila, spatarel, Cristian Francu and myself.
Edit: Editorials published. Link to Day 2
What is the solution to the first task (Gardening)?
Well I can tell you my solution. I implemented this thing hoping to get 78 but it got 100, so you can already tell how good of a solution this is :). Let can[n][m][k] = 1 if can paint a garden having n row, m columns with k colours. Let's also assume that n < m, because the other case is the same. How do I calculate this? We can split by line, by column or add a border. So can can[n][m][k] = 1 if and only if there is an i and k1 so that can[i][m][k1] = can[n — i][m][k — k1] = 1 and the same should be if we split by column. We are left with adding a border, which is simply check if can[n — 2][m — 2][k — 1] = 1. A small observation to speed this up: if n or m is odd, then there is no solution, so we can only split in an even amount of rows/columns. Having this thing calculated we can easily construct the solution.
Idk why this works fast enough :).
First an observation: N, M are even, and max(N/2, M/2) <= K <= NM/4. Furthermore K != NM/4 — 1, and when N = M, K != N / 2 + 1.
Now the solution: If K = NM/4 there is an easy solution; suppose thus that K <= NM/4 — 2. Imagine a garden with one rectangle frame with one type flower, otherwise with 2x2 patches with a flower type each. If the frame is 4x4 then there are NM/4 — 2 flowers, and if it is NxM there are (N-2)(M-2)/4 + 1 flowers. By increasing the frame 2 by 2 we can get all numbers of flowers between these values. If we want (N-2)(M-2)/4 — 2 flowers or fewer then we put a frame and solve recursively; there is a trick for (N-2)(M-2)/4 — 1 flowers. In this case we make a (N-2)*M rectangular frame (or N*(M-2)), and put a 4x4 frame inside of that one. The rest of the garden is filled with 2x2 patches with one type of flower.
How did you come up with this approach? When (n — 2, m — 2, k — 1) is not ok, I try to change it to (n — 2, m — 2, k — (n + m — 1), not to (n — 2, m, k — (m / 2)). But it is wrong
When will be day1 results published? Andrei1998
Tonight they will be up. Thanks for the patience!
Could you mention the cause of the delay? Is there any pretesting?
The results are now posted: https://rmi.lbi.ro/rmi_2021/contest/results/ No, the tests in the contest are the final ones used for grading and creating the final leaderboard. The delay was purely organizational: initially, there was a queue and we waited for it to be cleared, and then it took a bit more time before we got to publish the standings since we prioritized other commitments to make the second contest run as smoothly as possible. Hope this was for a good measure!
Thank you for the results and for the information! Have a nice day.
Will judging be faster today?
UPD: yes, it was much faster.
My solution for Speedrun (with penalty $$$n-2$$$, better than intended $$$2n$$$):
Encoding: root the tree at node $$$1$$$. For each node,
Speedrun:
I think our solution also uses only $$$n + O(1)$$$ failed calls to
goTo, but we decided to be lenient on this since it didn't matter all that much (it is more relevant that the number of fails is $$$O(n)$$$ as long as hints use only $$$2\log n$$$ bits).Open problem: can this problem be solved with less than $$$2 \log n$$$ hint bits?
You can store the XOR of the two values (a trick similar to the XOR linked list). Once you know one of the two values you can decode the other one.
Can someone explain his solution on Present? Is it some kind of binary search?
Im not sure about solution but you can write O(K * log K) naive solution for K <= 1e6. And just precalc every 1e6 th permutation. (~5e3 permutations) and just use naive solution for second subgroup.
dorijanlendvaj: your solution was really nice, do you mind describing it here?
The maximum element is at most 37(which can be found using the rest of the solution). If we can count the number of sets where certain numbers have to be included and some others don't have to be included, then we can go from i=37 to 1, say that i mustn't be included; if the resulting number of sets is >=k then keep that decision for the future, otherwise subtract the resulting number of sets from k and force i to be included in the future.
In order to count the number of sets like that, we first precompute all of the good sets of even numbers <=37 and then all of the good sets of odd numbers <=37. Then, since gcd(odd, even)=odd, we can try all of the good sets of odd numbers, and for each of them we precompute which even numbers can be included and which ones can't based on the rule that, for an even number x to be included, gcd(x, y) must be in the set of odd numbers for each y in the set of odd numbers. and use SOS DP to count the number of good sets of even numbers which can be added to that set of odd numbers. This can, of course, easily handle the restrictions of some numbers having to be included and some elements having to not be included.
Auto comment: topic has been updated by Andrei1998 (previous revision, new revision, compare).
Will there be a mirror contest held anywhere for Day 2?
Unfortunately, most likely no.
Oh okay. Is it possible to upsolve the tasks somewhere later? Like on oj.uz or something?
We will try to have them added onto oj.uz. Also, they will likely be added to the Romanian CS website (infoarena.ro) quite soon.
Will the results for the second day be posted tonight?
Andrei1998 Can you estimate the cuts?
Estimation: ~369 for gold, ~217 for silver, ~122 for bronze. Take them as preliminary until the final standings are out in the next hours.
I was stressing even before seeing the preliminary results, but now I am worrying even more since I am exactly at 122 (
LMAOO did you set such a fucking tight time limits to speed up the testing? LOOL XD
We really didn't try to make any problem tight on time. Which one did you experience difficulty with?
I submitted an n^2 solution to the problem B and it gave TLE until I made some formulas shorter. Also, I submitted n^2 log n solution to the problem C and it only passed first two subtasks(and should pass third and forth subtasks, at least third). I may had a bad constant but anyway, 0.2sc and 0.3sc time limit is not cool.
Dear contestant,
Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.
Thanks for the feedback,
Author of Nom
I don't think the contestants are obligated to know all kinds of cache-level micro optimizations. And even with the same code, my local machine consistently fluctuates about 10~50 ms. I guess it's your problem and it's up to you to have a view that the score of a contestant should be affected by these what I view as "dice rolls", but please don't state as if your view is unanimous among all programming competitions, because it certainly isn't.
It's good practice:
for the contestants to understand that the running time of their solution is judged based on its code, not on its complexity
for the committee to assume the contestants hope this isn't so
If it were actually the case, I would agree with you. However, it isn't actually the case.
Even if we're given the code and the full compiler info, we can't uniquely map it to a number representing a runtime. The only way we can fully determine whether our code will pass or not is to actually submit the code on the judge. Of course we can estimate it, but it has its limitation. So most of the problems on programming contests sets large TL margin to compensate for it.
Again, your point does make sense if such mapping exists, which is the case in interactive problems, since "maximum # of queries asked on all possible inputs" is well-defined given your code and compiler. And interactive problems does frequently have such tight limit.
Please consider the difference between "judged based on" and "given by" / "mapped from"
You can solve all Day 1 problems here: https://oj.uz/problems/source/590
Thank you so much for adding both days! Just as a general update: all problems, translations, results, editorials, test data/managers/checkers, and announcements + code submitted during the contest for both competition days are now available on the competition website here: problems, results, solutions and editorial.