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.com/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 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

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

You can solve all Day 2 problems here: https://oj.uz/problems/source/591