Andrei1998's blog

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

rmi2021_logo

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

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

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

What is the solution to the first task (Gardening)?

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

    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 :).

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

    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.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

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

When will be day1 results published? Andrei1998

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

    Tonight they will be up. Thanks for the patience!

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

      Could you mention the cause of the delay? Is there any pretesting?

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

        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!

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

          Thank you for the results and for the information! Have a nice day.

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

          Will judging be faster today?

          UPD: yes, it was much faster.

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

My solution for Speedrun (with penalty $$$n-2$$$, better than intended $$$2n$$$):

Encoding: root the tree at node $$$1$$$. For each node,

  • if it's not a leaf, save the previous node and the next node in the dfs order;
  • if it's a leaf, save the next node in the dfs order and its parent.

Speedrun:

  • Go up to the root. You have to visit at most $$$1$$$ leaf, so the maximum penalty is $$$n-2$$$.
  • Visit the nodes in dfs order. The information on the nodes guarantees that you always know what are the next node in dfs order and its parent.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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?

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

      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.

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

Can someone explain his solution on Present? Is it some kind of binary search?

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

    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.

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

    dorijanlendvaj: your solution was really nice, do you mind describing it here?

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

      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.

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

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

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

Will there be a mirror contest held anywhere for Day 2?

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

    Unfortunately, most likely no.

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

      Oh okay. Is it possible to upsolve the tasks somewhere later? Like on oj.uz or something?

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

        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.

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

Will the results for the second day be posted tonight?

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

Andrei1998 Can you estimate the cuts?

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

    Estimation: ~369 for gold, ~217 for silver, ~122 for bronze. Take them as preliminary until the final standings are out in the next hours.

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

      I was stressing even before seeing the preliminary results, but now I am worrying even more since I am exactly at 122 (

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

LMAOO did you set such a fucking tight time limits to speed up the testing? LOOL XD

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

    We really didn't try to make any problem tight on time. Which one did you experience difficulty with?

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

      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.

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

        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

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

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -37 Vote: I do not like it

            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

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

              for the contestants to understand that the running time of their solution is judged based on its code, not on its complexity

              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.

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

                Please consider the difference between "judged based on" and "given by" / "mapped from"

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

You can solve all Day 1 problems here: https://oj.uz/problems/source/590

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

    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.

    → Reply