For the second 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!
The contest timing will be USACO-like: it will be open for 24 hours but you will be able to compete for up to 5 hours (you can decide when to "start" your time window, after the login). Participation will be available upon registration to the Italian trainings website (localized also in english).
1. The problem statements will be available in both English and Italian.
2. The time window will start on 2017 September 15th, 10:00 CEST and will end on 2017 September 16th, 10:00 CEST.
3. Tasks will be IOI-like (with graders) and you will have 5 hours to solve them.
4. The languages allowed are: C, C++.
Note: you can decide when to start your 5 hour time window, but remember that the contest will end at 10:00 CEST regardless of your time window!
If you want to participate, you must:
- Visit the training website: https://training.olinfo.it (note that the URL was updated since last year)
- Click "Sign up" (if you haven't already done it last year!)
- Fill out the form and then confirm
- Visit the contest list: https://training.olinfo.it/contests
- Click on the OII 2017 National contest list entry
- 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 for the national contest will be available here when the contest ends (now it just shows a 404).
Will the ranking list contain unofficial participants?
Yes.
The ranking that will be available in the published link ( https://training.olinfo.it/contests/oii2017/rws ) will only contain international participants, we have a different ranking for italians who are participating on-site.
Will you also post solutions/analysis after the contest?
The ranking isn't working.
Please read the last paragraph carefully.
Out of curiosity why say that rather than "They mention that the ranking will only be available after the contest at the end of the post"?
Maybe because one shouldn't ask such questions.
He didn't ask a question he just pointed out a link doesn't seem to be working.
It is true the post mentioned this but misreads are inevitable and I don't see how trying to make someone feel bad about what would otherwise be a useful comment (if the organisers intended the link to be working but it in fact wasn't) achieves anything good?
I signed up, and when I try to log in it says "Welcome back Rudy69" and then "Login Error" and doesn't log me in.
Had the same problem. Use this link instead https://cms.di.unipi.it
How to solve 3rd problem (specchi)
Contest is not over yet.
I think that the contest is over so I'll explain my solution (I had a stupid bug so I wasn't able to pass it during the contest).
The main idea is that when we add a mirror we know that there will be two paths which will be split in two and then their parts merged (one of the paths is vertical and the other one is horizontal).
Also the other observation (which is actually pretty obvious) is that if we shoot the laser from point X and it goes to point Y, then if we shoot from Y it will go to point X.
This can be done with link/cut tree. For each component (tree or actually path) we store the two ends of the path. Then for every query we can simply pick the other end which is stored for the query point's component.
Every time we add a mirror we will create a two new nodes which will be the link between the different parts. Also we will add these verices to some sets to easily find which is the closest mirror to the left, right, down and up for the next queries.
This solution is
which runs fast enough.
In the contest I forgot that we can create a cycle with the mirrors. I fixed it in the last minutes but couldn't submit, because the contest was over.
There is another solution which can pass for 100 if implemented well using sqrt decomposition. In short for every mirror we store where we will be after
operations. This way we need to update 
nodes. Then for the query we will make at most 
jumps. The complexity will be 
.
How did you solve Corteo?
Do a bfs from each node to get dist[i][j], the distance between vertices i, j for all pairs (i, j).
Binary search the answer d.
To determine if d is achievable, we do a bfs on the pairs (x, y), where x is the position of the first group and y is the position of the second group. Initially, (s1, s2) can be reached (if dist[s1][s2] ≥ d). From each such pair, we go to all the pairs (x', y) where there is an edge between x and x' (and dist[x'][y] ≥ d) and also all the pairs (x, y') where there is an edge between y and y' (and dist[x][y'] ≥ d). d is valid if and only if (d1, d2) is reachable.
What is the complexity of this bfs? For each edge (u, v), it contributes to the edges between pairs (x, u) and (x, v) and (u, x) and (v, x) for any x. Thus, there are O(MN) edges and O(N2) vertices, so the bfs takes O(MN) time.
The total complexity is
because of the binary search.
And how did you solve caduta?
My solution for 91 points is outlined below if you're interested
Would we be able to upsolve the problems anywhere after the contest?
Yes, we will post them in the main task archive at http://training.olinfo.it
Where can i see and submit last year OII tasks?
https://training.olinfo.it/#/tags/events
For submitting: https://training.olinfo.it/#/tasks/1?tag=ioi2017,nazionali
The statements are Italian only, soon they will be available in English as well. Until we support multi-language, you can find them here: https://drive.google.com/open?id=0B8LJqB-JZyRfY1ZERG96MENWbUkEDIT: ok now you can just open one of the problems on the training website and select the language from the upper right corner! if there is an English version of the PDF it will be loaded, otherwise Italian will appear :)
So how does one solve the problems?
How to solve first problem (the one with the dominoes)?
Here's the pseudocode of my solution for 91 points
So why does this work fast enough? (It's not clear to me how many times the three inner loops execute.)
I'm honestly not sure and was surprised when it passed the subtask with N <= 10^5. Clearly the outer loop is O(N) and the most inner loop is also O(N) (if it gets run), the second loop however is a bit of a mystery. I've tried to come up a worst case test for it but it seems like nearly everytime the second loop is run at all it tends to find a solution. Here's my code if you want to try and test it: https://pastebin.com/Bqp00Cfs.
wut that's a mistery
Can someone please give me a direct link to the problem caduta (pazza gioia) ? Because when I try the links from above to the training website it showes me the tasks from 2016.
Heres the PDF. (PS: If organization doesn't allow to share this i will be glad to remove)
Thank you, but I would also like to submit my solution. Do you have the link to that?
https://training.olinfo.it/#/task/oii_caduta
If you're logged in, you will see a "Submissions" tab