For the fifth 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!
1. The problem statements will be available in both English and Italian.
2. Tasks will be IOI-like (with graders) and you will have 5 hours to solve them.
3. The languages allowed are C and C++.
4. The time window for the practice contest (featuring original problems of the same level as the main contest) will start on 2020 November 22th, 00:01 CET and will end on 2020 November 24th, 23:59 CET
5. The time window for the main contest will start on 2020 November 25th, 18:00 CET and will end on 2020 November 26th, 18: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.
Training after the contest
After the end of the contest, tasks will be uploaded in the italian training website (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).
I can't enter the webpage.
same
The server where everything is hosted (the mirror, the real contest, the online judge for upsolving...) is down for mysterious reasons (it was up and working 1 hour ago).
This will be fixed as soon as possible (this is a very rare and unlucky event), but the fact that the region where the server is located is currently in lockdown due to covid does not help.
I will write here as soon as the problem is fixed.
Thanks a lot for your concern :D
The registration webpage is up and running.
Whoever registered before the downtime shall register again.
I can't enter italian training website
Unfortunately the server is still down and will be so at least for few more days. Therefore most of the Italian training platforms are still unavailable. :c
We had to move the mirror to another server, for this reason the previously registered accounts went lost.
What is the expected difficulty of problems? Like in terms of codeforces div2. A/B/C etc?
The contest is IOI-style, so problems have subtasks. For each problem, usually, the easiest subtask is easy (div2B) while the hardest subtask can be quite hard (div1C).
Ok, thank you!
The hardest is only div.1C? Seems much easier than CNOI....
Probably most OI's are much easier than CNOI....
At least I think JOISC do not.
Most is not all.
I guess you might be comparing the national TST with the national olympiad. At least in Romania those are different things (the team selection tests being much harder than the national olympiad).
Unfortunate that Java is not available though, I guess you can't get to IOI in Italy if you just use Java.
Java will not be supported at IOI.
What??? It has been for a few years now???? I literally competed at the IOI in Java like a good month ago???
Can you please give me a source that says they will discontinue Java support at the IOI???
https://ioi2021.sg/rules/
The practice contest just started! GL & HF
Less than 3 days before the contest, good luck to everyone participating!
Only two days to go! Get ready and sharpen your keyboards!
Very nice problems!!
armyalpaca is very strong, he will win OII for sure!
I predict that davi_bart will win OII2020 and that you and Kaey will get into top3 ;)
Why is everybody sleeping on iwannad?
I think there will be a tie between TheScrasse and davi_bart, they are both very strong!!!
I think i will win oii, bc im too strong; armyalpaca suck;
Unofficial top 10 (This ranking is likely incomplete, especially below 160 points, because each contestant can only see their own score and I don't know everyone; hopefully the scores I have are correct though)UPD: The official ranking is now available at https://stats.olinfo.it/contest/2020 . GG for the winner, Davide!
If you were a contestant or you know somebody else's result, please PM me so I can make this scoreboard as accurate as possible.Any tips on how to stop writing code full of bugs? D:
I think taulant has a good chance to win, but for sure it will be a very exiting contest. GL to everyone!
Obviously TheScrasse is gonna win it. Btw good luck to all the others, including me.
I missed the practice contest. Is there any place where I can see/try some of the problems from there? Thanks in advance!
Very soon (should be a matter of hours) the problems of the practice will be uploaded in the Italian training website.
I will comment here as soon as it happens.
By the way, don't miss the real contest! The window to compete starts in 9 hours.
Here are the problems for upsolving:
and now where can we submit those problems?
They are now available here.
Any ideas for practice contest task 3 (sushi)? I did BSTA + subset-sum but that only got 69 points (as expected, I think the complexity is $$$O(NB^2)$$$)
Also interested, I did similar BSTA + bounded knapsack (see here, results in fewer items) but that did not give the last two subtasks, only 94 points.
I'm actually curious about this too. These are the best solutions I know:
I passed during the contest using solution 1. I submitted both of these to the upsolving site, and only solution 2 passes, and in a full 0.93/1.0 seconds. Does anyone else have a better solution?
In the training platform, execution times are higher than the contest, but the time limit was the same until a few minutes ago; now it has been increased to 4.0s (from 1.0).
By the way, I don't know what the official solution does, but I've been told that it runs in O(NBlog(B)/64).
You are right to be curious: in the upsolving platform the time-limit was completely wrong (because the server is much slower compared to the one used for the contest). We raised the time-limit to 4s, now both your solutions should get accepted.
By the way, let me mention that there is another solution to the problem (which was the original one by the author) with complexity is $$$O(NB\log(B)/64)$$$. The code is extremely short and clear (and the solution is cute): https://ideone.com/a9StE3 . If something is not clear, feel free to ask. Before raising the time-limit, not even this "official" solution was getting accepted so the answer to "Does anyone else have a better solution?" is definitely "No".
Finally, let me say that I am glad that you have seen this problem. I truly think that it was a bit too good to be given in a practice contest and I am sure the author will be happy to know that some strong contestants have tried it.
How do we prove that we can safely omit an item? Can't it add bits after few iterations?
Nope, if you think about it, if you wanted to use the item later, you might as well have used it earlier, so it's never going to be necessary later. You could also directly analyze the bitset knowing that if k is set, then k+a is set too.
Ah, yeah, if we drop an item that means all multiples of weight are in knapsack. Much better than keeping the item for $$$B / w[i] $$$ iterations.
Less than 10 minutes to the start! GLHF
I kindly invite everyone to take part in the mirror of the official contest. The time-window will end in 7 hours.
Moreover, the results of the official contest suggests that this year the problems were slightly harder than usual... So, even if you are a strong contestant, you might find something for you in the contest.
How to solve compleanno? I got 100 pts but I can't prove the number of states is reasonably small. I just skipped some divisors which need extra $$$k$$$ > some const steps.
What was your solution? I found an O(N) solution that solved everything for N<=500000 but didn't know how to go about solving it for larger N.
dario2994 shared the code below. My solution is almost the same: iterate $$$d$$$ from $$$2$$$ to some small number. Try to update $$$dp(n)$$$ with value of $$$dp(\lfloor{n/d}\rfloor)$$$. To get 100 I've skipped such $$$d$$$ that $$$n$$$ $$$mod$$$ $$$d > 2$$$ can't reason why it worked but author's solution handles this situtation much better (compares lower bound with current $$$dp[n]$$$).
Oh ok, I see. Thanks!
Our solution for 99 points is the following one: https://ideone.com/FTeTDg.
To get 100 one should just optimize some stuff (i.e. use an array instead of unordered_map for small values and iterate
mulonly over {2, 3, 4, 5, 7, 11, 13, 19, ...}).We do not have a proof that the number of states is small for all numbers $$$n$$$.
On the other hand, it is easy to prove that the number of states is bounded from above by $$$O(\sqrt{n})$$$ and, intuitively, it should be much smaller than $$$\sqrt{n}$$$. Honestly, I think it is fine to give a problem of this kind without a proof of the complexity of the solution, as far the solution behaves fast enough on all testcases one comes up with (and there is no reason to expect the existence of a "very hard testcase"). On the other hand, I would strongly disagree with giving such a problem without a proof of the correctness of the solution (can you prove that the solution provided above is correct?).
Finally, let me leave here two open questions: does it exist a number $$$n$$$ such that the optimal sequence of moves uses a multiplication by $$$23$$$? Can you find one such number below $$$10^{18}$$$?
Some evidence that 23 shouldn't be necessary:
Note that it takes $$$d+1$$$ moves to divide by $$$d$$$, and takes up to $$$d-1$$$ moves to reduce to $$$0$$$ mod $$$d$$$. Thus, the rate to reduce $$$\log(n)$$$ when dividing by $$$d$$$ is somewhere between $$$(d+1) / \log(d)$$$ and $$$2d / \log(d)$$$. Thus, we're roughly trying to minimize $$$(d+1) / \log(d)$$$, up to a factor of 2x.
Now, $$$(d+1) / \log(d)$$$ is minimized when $$$d = 4$$$ at $$$5 / \log(4) \approx 3.6$$$. On the other hand, $$$24 / \log(23) \approx 7.65$$$, which is just over twice the value, which seems to roughly show that multiplying by $$$23$$$ is just outside the range of optimal.
Why are you trying to reduce the log?
I mean, when you try to divide a number by $$$d$$$, you're not exactly going to subtract $$$\log(d)$$$; depending on the original number, it can be that the subtraction is slightly bigger (because you take the floor).
We're just trying to approximate the rate; the rounding you're talking about should be a pretty small error (much less than 1) compared to the actual log. Everything's an approximation anyways.
Will there be an editorial or will at least the task input be available? I'm most curious about the task candela, my djikstra shortest path solution couldn't get any points for some reason and I'm really not sure why (I'm new to c++ so I probably did something stupid and I would like to find out what)
I am sorry, but we do not plan to write the editorials.
In any case, one of the official solutions of Candele uses Dijkstra, so you should be on the right path (and now you can upsolve it if you like).
Can you explain the Dijkstra solution? I used 2 pointers to solve it. But now, after hearing it can be solved by Dijkstra, I am really curious to know the Dijkstra solution :D
Dijkstra is mostly just a fancy name for "don't visit the same state twice"; I'm sure your two pointer solution implicitly uses that constraint.
I see
I disagree with ecnerwala; I think that the Dijkstra solution is truly different from the 2 pointers solution. I will give a short sketch of both solutions:
The second solution is really nice.I optimized the djikstra solution with O(n^2) edges with a lazy segment tree(without implicitly making a graph)
my code- https://ideone.com/YdLRaN
The proof of the 2 pointers solution is precisely the same reason you can eliminate most edges in the Dijkstra solution; the waves in the 2 pointers solution correspond pretty much exactly to the priority queue in Dijkstra. I think the 2 pointers solution is just what you get if you do an extra step of analysis past eliminating redundant edges.
You are right, I was wrong when I said that the two solutions are truly different.
Even if I understand your point, in my mind the two solutions "don't share a prefix" (i.e., one is not easier than the other and knowing one does not help in understanding the other). I think that this has more to do with how I see the solutions than with what the solutions are.
We hope you liked the problems.
For upsolving (you can switch to english using the menu on the top-right):
I leave here a couple of variations of task candele you can ponder over. We (briefly) considered these when discussing the problems, but they were either wrong-targeted or too difficult or open.
Try to:
answer queries of the following type: given a candle $$$x$$$ and a candle $$$y$$$, tell whether, by lighting up $$$x$$$, $$$y$$$ will be lit in a finite amount of time.
answer queries of the following type: given a candle $$$x$$$ and a candle $$$y$$$, tell after how many seconds $$$y$$$ will be lit if we light up $$$x$$$ at time $$$0$$$ (or if it will be never lit).
solve candele provided that candles burn at different rates: candle $$$i$$$ burns at $$$R[i]$$$ seconds per unit, where $$$R[i]$$$ is a positive integer.