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.
- The problem statements will be available in both English and Italian.
- Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
- The only language allowed is C++.
- 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.
- 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:
- Visit the contest website: https://mirror.oii.olinfo.it
- Click the link "register", fill out the form and then click on the register button and then "back to login"
- You can now log in with the same username and password you used to sign up
- 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)
- When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
- 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).
Great, thank you for notifying! USACO formula is very comfortable, my Friday 13th night is booked for OII
Mirror clashes with RMI 2023
Indeed
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.
Can you share website or other information about RMI?
there is no website at the moment
Only data I have is:
Привет, Демид. Ты в последнее время очень сильно похудел. У тебя всё хорошо? Может, нужно чем помочь?
BestCrazyNoob will win!
I think jamesbamber will win, he is too strong
Also franv has good chances
Thanks, but I think AlesL0 will win
Hi sir, which strength is pretest? I dont want fail systest!
pretests = systests
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.
The ranking is now available at ranking.olinfo.it/2023-pre-oii-mirror/, and the second contest started ~15min ago
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?
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! "
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.
We should have fixed the issue, please let me know if this is not the case.
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?
It won't be possible as a virtual contest, but we will upload the tasks on training.olinfo.it
cool, do you know approximately when they'll be uploaded?
In the next few days, as soon as possible
Tasks are up on training.olinfo.it!
I can't see myself in Rankings, can you please check?
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.
I couldn't see myself before either, but it updated recently so check now :)
Yup, I just did the final update :) It should be up to date now, and archived at ranking.olinfo.it/2023-oii-mirror
Amazing! I don't know how I fluked coming first but I'll take it :)
What's the solution to P4 (disegno)?
A solution PDF (Italian only, sorry!) has been published at wiki.olinfo.it/it/2023/nazionali
Thanks!
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:
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$$$:
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.
Thanks for the solution!
Reference to the first sample:
Sorry if I misread your solution, but what prevents Step 2 from picking the center of the cross at $$$(8, 6)$$$ (in which two four chosen rectangles $$$R_1, R_2, R_3, R_4$$$ are $$$[6,8]\times [1,6]$$$, $$$[6,8]\times [6,7]$$$, $$$[8,10]\times [1,6]$$$, and $$$[8,10]\times [6,7]$$$)?
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)$$$.
Wil you share the on-site results?
They are already out at ranking.olinfo.it/2023-oii
Thanks!