RMI 2021 is taking place on December 15-17. Day 2 was today, tasks are here:
Feel free to discuss and give feedback here! Edit: results are out, congrats everyone, especially Ormlis for the perfect score!
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.
Editorials published. Link to Day 1.
I hope you liked the problems :)
Yeah, the task Weirdtree was my favorite one))
Was your solution like ours?
Yes, it was))
I almost forgot that RMI is incomplete without stupidly strict time limits until today. I got 68 instead of 100 on paths because my solution ran in about 450 ms and the TL was 300 ms.
Bruh aren't you the same guy who squeezed in a quadratic algorithm on a graph problem with cache misses magic last year
Edit: lol yeah http://codeforces.me/blog/entry/85285?#comment-729736
Also gratz on the best solution!!!
That's true, but in this case it was possible to, for example, double the constraint on n and set the time limit to 1 second; that would make it harder for quadratic solutions to pass and make it easier for n*log solutions to pass. The only possible disadvantage to this is judging time.
Problem A got me.Twice..
Don't get upset!
Auto comment: topic has been updated by Andrei1998 (previous revision, new revision, compare).
Problem B was interesting for me. I didn't manage to solve it during the contest, but after it, my friend (kitsune) told me his idea for it, which he couldn't implement during the contest.
When we put same number on indexes $$$i$$$ and $$$j$$$, this must hold
Or we can say like this
So if we take all indexes from 0 to 2 * n - 1 modulo m, then we need to divide them into n pairs with the above condition. First of all, let's group indexes with the same value modulo m. For example if n = 3 and m = 2, we have indexes
if we take values modulo m, then it will become
and we will group indexes with the same value,
So now, we have ranges with the same value, and for some elements, we can't choose its pair from its own range, and we can do dp with it.
dp states will go like this
dp[i][j]= number of variants if we match sets from 1 to i and j elements will remain not paired. When we do a transition fromitoi + 1, we choosexelements from a setiand pair them withxunpaired elements from previous sets. When we counted the number of different pairings, we multiply it byN! * (2 ^ N), because we can put values to those indexes inN!ways, and we can color them in2 ^ Nways.And the time complexity is
So it should pass if we are not mistaken. Very upset that I didn't come up with the idea, and kitsune, hadn't enough time to write it. Here is code.
Thank for reading. By the way, where can we upsolve the problems?
Thank you for sharing your ideas and experience!
Re upsolving: https://infoarena.ro/arhiva?display_entries=6&first_entry=2296 — note there are some differences with respect to the contest, such as: file I/O instead of standard; possibly different scoring; possibly tighter time limits; statement language :-)
Thank you