TheScrasse's blog

Italian Olympiad in Informatics (OII) 2023 — Online Contest
By TheScrasse, history, 14 months ago, In English

For the eighth time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate! There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

  1. The problem statements will be available in both English and Italian.
  2. Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
  3. The only language allowed is C++.
  4. The time window for the practice contest (featuring original problems) will start on 2023 September 30th, 00:00 CET and will end on 2023 October 10th, 23:59 CET.
  5. The time window for the main contest will start on 2023 October 13th, 10:00 CET and will end on 2023 October 14th, 15:00 CET.

The contests' timing will be USACO-like: you can decide when to start your 5-hours time window (after the login), but the contest will end at the given time regardless of your time window.

If you want to participate, you must:

  1. Visit the contest website: https://mirror.oii.olinfo.it
  2. Click the link "register", fill out the form and then click on the register button and then "back to login"
  3. You can now log in with the same username and password you used to sign up
  4. If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  5. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  6. Good luck and have fun!

Ranking: The ranking of the online contest will be available at https://mirror.oii.olinfo.it/ranking when the contest starts.

Upsolving: After the end of the contest, tasks will be uploaded in the Italian training website https://training.olinfo.it (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).

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

Comments Comments (38)
| Write comment?
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Great, thank you for notifying! USACO formula is very comfortable, my Friday 13th night is booked for OII

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

Mirror clashes with RMI 2023

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

    Indeed

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

    It's an unfortunate coincidence, but we planned the nationals before knowing about RMI and at this point we can't do much to avoid it. We always hold the mirror in parallel to the onsite contest, but the tasks will be made available on our training platform soon after the end.

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

    Can you share website or other information about RMI?

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

      there is no website at the moment

      Only data I have is:

      • It will be held 11-14 October
      • 12 and 13 are contest days, on the evening of 13 the closing ceremony will be held
      • Organizer provided accomodation will very most certainly be at Moxa Students' Complex
      • problems will be cringe
      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Привет, Демид. Ты в последнее время очень сильно похудел. У тебя всё хорошо? Может, нужно чем помочь?

      → Reply
»
13 months ago, # |
  Vote: I like it +34 Vote: I do not like it

BestCrazyNoob will win!

→ Reply
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Hi sir, which strength is pretest? I dont want fail systest!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The first contest is over! We will upload the tasks in the next few days on training.olinfo.it, and the scoreboard of the public mirror somewhere (link coming soon).

Best of luck for the next contest, which should start at 10AM CEST at mirror.oii.olinfo.it.

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

According to the blogpost, the contest window will last for a day and 5 hours. However, the contest website shows that the contest will end after 5 hours. I think there is a mistake when setting the date of the ending time. Is anyone able to fix it?

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

    it also states that " Every user is allowed to compete (i.e. submit solutions) for a uninterrupted time frame of 3 hours. "

    When it is written in the blog that : " When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window! "

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

      Sorry if I didn't make it clear, but I meant that the contest should end at 15:00 CET on Oct.14, while currently it is ending at 15:00 CET on Oct.13.

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

        We should have fixed the issue, please let me know if this is not the case.

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

Hey! I'll love to participate in the mirror, but it is impossible for me as I'm not at home(yesterday was a Spanish Festivity so I took a day out today), when it will be possible to re-do the virtual after the window ends?

→ Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Tasks are up on training.olinfo.it!

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I can't see myself in Rankings, can you please check?

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

    This is a known problem, the ranking doesn't pick up new users until we manually do it. I will update it when I get back home.

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

    I couldn't see myself before either, but it updated recently so check now :)

    → Reply
»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

What's the solution to P4 (disegno)?

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

    A solution PDF (Italian only, sorry!) has been published at wiki.olinfo.it/it/2023/nazionali

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

    First, in fact, there are $$$O(N \log N)$$$ subgrids (= rectangular areas) which is valid. For example, if the drawing is a "complete grid", the only valid subgrid are $$$2^k \times 2^k$$$ grid, which is only $$$\sum (L-2^k+1)^2 = O(L^2 \log L)$$$, which is $$$O(N \log N)$$$. One can prove that this property holds for any drawing.

    The strategy is to enumerate all of them by merging, like the following:

    1. The grid is separated into some region. First, compute all of the regions and check if it is all rectangular (if some are not, it's an invalid grid). Let $$$S$$$ be the set of rectangles.
    2. Repeat the following while we can make progress:
      • Choose 4 rectangles $$$R_1, R_2, R_3, R_4 \in S$$$. If we can make a larger rectangle by merging $$$4$$$ rectangles which the "center of the cross" is the same, add the larger rectangle to $$$S$$$.
    3. Finally, if the entire grid $$$[0, L] \times [0, L] \in S$$$, the grid is valid. Otherwise, the grid is invalid. The reconstruction of the answer when the grid is valid can be done by following:
      • For any rectangle $$$R \in S$$$, record the index of rectangles $$$R_1, R_2, R_3, R_4$$$ that made up $$$R$$$ in Step 2.
      • Then, we can construct the answer by running DFS.

    The main part is Step 2, as the naive solution takes $$$O((N \log N)^4)$$$, which is impossible to get 100 points. However, there is a following convenient property on set $$$S$$$:

    • Suppose $$$[x_l, x_r] \times [y_l, y_r] \in R$$$ and $$$[x'_l, x'_r] \times [y'_l, y'_r] \in R$$$. If $$$(x_l, x_r, y_l) = (x'_l, x'_r, y'_l)$$$, then $$$y_r = y'_r$$$.
    • This property, of course, also holds for the other $$$3$$$ directions.

    So, when a new rectangle $$$R$$$ is added to set $$$S$$$, and if the "center of cross" is determined (one of $$$4$$$ choices), the other rectangles $$$R_2, R_3, R_4$$$ for merging, when $$$R_1 = R$$$, can be uniquely determined. This process can be done in $$$O(1)$$$ time if we use hashmap.

    Therefore, this problem can be solved in $$$O(N \log N)$$$. The constant factor can be somewhat large, but I think it at least gets 87 points.

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

      Thanks for the solution!

      A question
      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        The answer for your question is that, it doesn't prevent picking the "center of cross" at $$$(8, 6)$$$ at all :) It indeed creates a larger rectangle $$$[6, 10] \times [1, 7]$$$ and is put in $$$S$$$. But $$$[6, 10] \times [1, 7] \in S$$$ does not make more larger rectangle, so it doesn't contribute for making $$$[0, 10] \times [0, 10]$$$.

        At a first glance, it seems like a waste to put such rectangle to $$$S$$$, but even if doing so, the number of rectangles is bounded by $$$O(N \log N)$$$.

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

Wil you share the on-site results?

→ Reply