TheScrasse's blog

Italian Olympiad in Informatics (OII) 2022 — Online Contest
By TheScrasse, history, 2 years ago, In English

For the seventh 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 2022 September 13th, 00:01 CET and will end on 2022 September 17th, 23:59 CET.
  5. The time window for the main contest will start on 2022 September 23th, 10:00 CET and will end on 2022 September 24th, 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
  • +181
  • Vote: I do not like it

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

The time window for the practice contest has started.

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

How to A???? I tried a treap of dfus of ffts but it just wont pass the last tc Someone told me to find the diameter so i just did float d = ((float)N-1f)/atan(1) but from there im stuck. Maybe i need to find the modular form of the elliptic curve of the graph but i dont know how to do it. asked for an hint and the staff replied: “sei meravigliosa come una ragazza gotica” idk what that means, mabye some italian ds

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

as a wise man once said,

/*
if there were a little good in the world
and everyone considered each other as brothers
there would be less worries and less pain
and the world would be a lot better
*/

now I don't know where I'm going with this, but what I'm sure of is that franfill will win this year's OII

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

How to solve statue and sets? TheScrasse

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

    Triplets

    Its easy to see that all three statues should be placed at the leaves. Then all you need to do is find a non-leaf node with (upto) 3 farthest leaf nodes.

    You can do the above using brute force if you dfs from all inner nodes. But the brute force solution will TLE. So you need to solve this using dp + dfs.

    Use DFS1 to store the distance to the farthest leaf node.
    Use DFS2 to get the farthest leaf node from the parent and then combine it with farthest leaf nodes from children to get 3 farthest leaf nodes. 2 * (sum of distances) is the contribution of this particular node to the answer. Just max all the contributions to get the final answer.

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

      Sets

      My solution for this problem was only partially correct. :(

      Step 1: Find the maximum number of numbers that can be removed in one pass. This can be solved using dp.

      Keep repeating Step 1, as long as you can remove some numbers. (You have > 2 values and number of numbers removed was > 0).

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

        You first solution is not for statues, it is for triplets. Also, by my questions I meant to know full solutions

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

    I have no idea whether my solution to sets is right, but it did get 100 points.

    First $$$O(n^3)$$$ dp is trivial: let $$$f(l,r)$$$ be whether you can erase everything in range $$$[l,r]$$$.

    Note that

    • only when the xor sum of $$$[l,r]$$$ is 0, $$$f(l,r)$$$ might be 1.
    • The transitions look like enumerate $$$k$$$ and then check if both $$$[l,k],[k+1,r]$$$ can be erased. When doing so, use an array to store all $$$k$$$ such that $$$f(l,k)=1$$$ and only try those $$$k$$$-s.
    • if now $$$f(l,r)=1$$$, break; immediately.

    With the two optimizations, it passes $$$n=10^4$$$ in 0.3 seconds.

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

I'm curious about how other countries do the IOI selection, is this the definitive selection? in September?

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

    Last year we did 7 contests (OII is the first of them).

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

When will the problems be uploaded to the page for upsolving?

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

Is it IOI???????

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

iam from egypt can i participate?

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

Is the ranklist down?

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

    Looks like it, maybe they will only open it after the time window for a fairer mirror? or maybe they just forgot to turn it on

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

    Fixed

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

Hi Valerio! Are you sure https://mirror.oii.olinfo.it/ranking is supposed to be open to all now? It contains problem difficulty spoilers...

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

    Yes, the SC decided to leave the ranking open. (Feel free not to open it)

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

What strategies did adaptive judge use? Picking binary search midpoint using DP always made my results worse. I think it's too weak.

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

Last problem is same as https://oj.uz/problem/view/IOI16_dna lol

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

    When the problem author asked for feedback, we thought the statement was too simple to be new, but we didn't find the problem on Google.

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

Hi! Anybody knows how solve problems coda and dna?

→ Reply