wil93's blog

By wil93, history, 9 months ago, ,

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

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:

1. Visit the training website: https://training.olinfo.it (note that the URL was updated since last year)
3. Fill out the form and then confirm
4. Visit the contest list: https://training.olinfo.it/contests
5. Click on the OII 2017 National contest list entry
7. 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)
8. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
9. 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).

•
• +77
•

 » 9 months ago, # |   +10 Will the ranking list contain unofficial participants?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » 9 months ago, # ^ |   +3 Will you also post solutions/analysis after the contest?
 » 9 months ago, # |   0 The ranking isn't working.
•  » » 9 months ago, # ^ |   +11 Please read the last paragraph carefully.
•  » » » 9 months ago, # ^ |   +1 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"?
•  » » » » 9 months ago, # ^ |   +7 Maybe because one shouldn't ask such questions.
•  » » » » » 9 months ago, # ^ |   +1 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?
 » 9 months ago, # |   +10 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.
•  » » 9 months ago, # ^ |   +10 Had the same problem. Use this link instead https://cms.di.unipi.it
 » 9 months ago, # |   +3 How to solve 3rd problem (specchi)
•  » » 9 months ago, # ^ |   +18 Contest is not over yet.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +11 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 .
•  » » » 9 months ago, # ^ |   0 How did you solve Corteo?
•  » » » » 9 months ago, # ^ |   0 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.
•  » » » » » 9 months ago, # ^ |   0 And how did you solve caduta?
•  » » » » » » 9 months ago, # ^ |   0 My solution for 91 points is outlined below if you're interested
 » 9 months ago, # |   0 Would we be able to upsolve the problems anywhere after the contest?
•  » » 9 months ago, # ^ |   0 Yes, we will post them in the main task archive at http://training.olinfo.it
 » 9 months ago, # |   -8 Where can i see and submit last year OII tasks?
•  » » 9 months ago, # ^ |   0
•  » » 9 months ago, # ^ | ← Rev. 2 →   +3 For submitting: https://training.olinfo.it/#/tasks/1?tag=ioi2017,nazionaliThe 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 :)
 » 9 months ago, # |   0 So how does one solve the problems?
 » 9 months ago, # |   0 How to solve first problem (the one with the dominoes)?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +6 Here's the pseudocode of my solution for 91 points get a list of all dominos that aren't knocked down if there are none: return ok let L = index of the first domino not knocked down let R = index of the last for all i from 0 to n-1: for all j from R-height[i]+1 to L-1: swap i and j if all knocked down: return i and j swap back i and j if none found: return impossible 
•  » » » 9 months ago, # ^ |   0 So why does this work fast enough? (It's not clear to me how many times the three inner loops execute.)
•  » » » » 9 months ago, # ^ |   0 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.
•  » » » » » 9 months ago, # ^ |   +3 wut that's a mistery
 » 9 months ago, # |   0 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.
•  » » 9 months ago, # ^ |   0 Heres the PDF. (PS: If organization doesn't allow to share this i will be glad to remove)
•  » » » 9 months ago, # ^ |   0 Thank you, but I would also like to submit my solution. Do you have the link to that?
•  » » » » 9 months ago, # ^ |   0 https://training.olinfo.it/#/task/oii_cadutaIf you're logged in, you will see a "Submissions" tab