Andrei1998's blog

RMI 2021 Day 2 Discussion
By Andrei1998, history, 2 years ago, In English

rmi2021_logo

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.

  • Vote: I like it
  • +72
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I hope you liked the problems :)

→ Reply
»
2 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    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!!!

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem A got me.Twice..

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Andrei1998 (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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 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

$$$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?

→ Reply