Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### Andrei1998's blog

By Andrei1998, history, 8 months ago,

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.

• +72

 » 8 months ago, # |   +21 I hope you liked the problems :)
•  » » 8 months ago, # ^ |   +1 Yeah, the task Weirdtree was my favorite one))
•  » » » 8 months ago, # ^ |   0 Was your solution like ours?
•  » » » » 8 months ago, # ^ |   0 Yes, it was))
 » 8 months ago, # |   +68 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.
•  » » 8 months ago, # ^ | ← Rev. 3 →   +11 Bruh aren't you the same guy who squeezed in a quadratic algorithm on a graph problem with cache misses magic last yearEdit: lol yeah http://codeforces.com/blog/entry/85285?#comment-729736Also gratz on the best solution!!!
•  » » » 8 months ago, # ^ |   +16 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.
 » 8 months ago, # |   +8 Problem A got me.Twice..
•  » » 8 months ago, # ^ |   -13 Don't get upset!
 » 8 months ago, # |   0 Auto comment: topic has been updated by Andrei1998 (previous revision, new revision, compare).
 » 8 months ago, # |   +29 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 $j - i \neq 0 \mod{m}$Or we can say like this $j \neq i \mod{m}$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 $0, 1, 2, 3, 4, 5$if we take values modulo m, then it will become $0, 1, 0, 1, 0, 1$and we will group indexes with the same value, $0, 0, 0, 1, 1, 1$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 thisdp[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 from i to i + 1, we choose x elements from a set i and pair them with x unpaired elements from previous sets. When we counted the number of different pairings, we multiply it by N! * (2 ^ N), because we can put values to those indexes in N! ways, and we can color them in 2 ^ N ways. And the time complexity is $O(M * \frac{N}{M} * N) = O(N * N)$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?
•  » » 8 months ago, # ^ |   +28 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 :-)
•  » » » 8 months ago, # ^ |   +5 Thank you
 » 8 months ago, # |   0 You can solve all Day 2 problems here: https://oj.uz/problems/source/591