### dario2994's blog

By dario2994, 18 months ago,

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!

#### 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:

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

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

• +156

 » 18 months ago, # | ← Rev. 4 →   +4 I can't enter the webpage.
•  » » 18 months ago, # ^ |   0 same
•  » » 18 months ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » 18 months ago, # ^ |   0 Thanks a lot for your concern :D
•  » » » » 18 months ago, # ^ |   +8 The registration webpage is up and running.Whoever registered before the downtime shall register again.
•  » » » » » 18 months ago, # ^ |   0 I can't enter italian training website
•  » » » » » » 18 months ago, # ^ |   +10 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. :cWe had to move the mirror to another server, for this reason the previously registered accounts went lost.
 » 18 months ago, # |   +8 What is the expected difficulty of problems? Like in terms of codeforces div2. A/B/C etc?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +22 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).
•  » » » 18 months ago, # ^ |   +1 Ok, thank you!
•  » » » 18 months ago, # ^ |   -46 The hardest is only div.1C? Seems much easier than CNOI....
•  » » » » 18 months ago, # ^ |   +28 Probably most OI's are much easier than CNOI....
•  » » » » » 18 months ago, # ^ |   -14 At least I think JOISC do not.
•  » » » » » » 18 months ago, # ^ |   +18 Most is not all.
•  » » » » » » 18 months ago, # ^ |   +29 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).
 » 18 months ago, # |   0 Unfortunate that Java is not available though, I guess you can't get to IOI in Italy if you just use Java.
•  » » 18 months ago, # ^ |   +27 Java will not be supported at IOI.
•  » » » 18 months ago, # ^ |   +8 What??? It has been for a few years now???? I literally competed at the IOI in Java like a good month ago???
•  » » » 18 months ago, # ^ |   +8 Can you please give me a source that says they will discontinue Java support at the IOI???
•  » » » » 18 months ago, # ^ |   +22
 » 18 months ago, # |   +41 The practice contest just started! GL & HF
 » 18 months ago, # |   +59 Less than 3 days before the contest, good luck to everyone participating!
 » 18 months ago, # |   +35 Only two days to go! Get ready and sharpen your keyboards!
 » 18 months ago, # |   +12 Very nice problems!!
 » 18 months ago, # |   +25 armyalpaca is very strong, he will win OII for sure!
•  » » 18 months ago, # ^ |   +33 I predict that davi_bart will win OII2020 and that you and Keewrem will get into top3 ;)
•  » » » 18 months ago, # ^ |   +25 Why is everybody sleeping on iwannad?
•  » » » » 18 months ago, # ^ |   +33 I think there will be a tie between TheScrasse and davi_bart, they are both very strong!!!
•  » » » » » 18 months ago, # ^ |   -25 I think i will win oii, bc im too strong; armyalpaca suck;
•  » » » 18 months ago, # ^ | ← Rev. 7 →   +50 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! Davide Bartoli (davi_bart, 268/300 points) Filippo Casarin (Virv, 253 points) Taulant Arapi (me, 233 points) Lorenzo Massi (rocks03, 223 points) Tommaso Dossi (Keewrem, 180 points) Tommaso Lunghi (Darkeld, 176 points) Francesco Lugli (franfill, 165 points) Armando Pellegrini (armyalpaca, 160 points) Fabio Giovanazzi (158 points) Lorenzo Ferrari (lorenzoferrari), Massimiliano Foschi (MassimilianoF), and Antonio Ciociola (146 points) 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.
•  » » » » 18 months ago, # ^ |   0 Any tips on how to stop writing code full of bugs? D:
 » 18 months ago, # |   +30 I think taulant has a good chance to win, but for sure it will be a very exiting contest. GL to everyone!
 » 18 months ago, # |   +30 Obviously TheScrasse is gonna win it. Btw good luck to all the others, including me.
 » 18 months ago, # |   0 I missed the practice contest. Is there any place where I can see/try some of the problems from there? Thanks in advance!
•  » » 18 months ago, # ^ |   +35 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.
•  » » » 18 months ago, # ^ |   +37 Here are the problems for upsolving: mascherine (the author is bortoz) account (the author is bortoz) sushi (the author is Virv)
 » 18 months ago, # |   +8 and now where can we submit those problems?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +8 They are now available here.
 » 18 months ago, # | ← Rev. 4 →   +3 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)$)
•  » » 18 months ago, # ^ |   +3 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +71 I'm actually curious about this too. These are the best solutions I know: $O(NB / 64 + B \log^2 B)$: first use bitsets to find the mask of what's possible using at most one of each type. Then, we can binary-search-on-answer and use FFT multiplication to take exponents of this bitmask. $O((N+B)B / 64)$, by ksun48: Note that in $O(B / 64)$, you can add one instance of one item to a knapsack DP, using bitset. Then, we'll cycle through the types and add 1 instance to the bitset one at a time; if it doesn't change the bitset, then we can omit it from future loops. Thus, each addition either increases the number of set bits, or we remove an item, so there are at most $N+B$ runs total. 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?
•  » » » 18 months ago, # ^ |   0 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).
•  » » » 18 months ago, # ^ |   +40 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.
•  » » » 18 months ago, # ^ |   +18 How do we prove that we can safely omit an item? Can't it add bits after few iterations?
•  » » » » 18 months ago, # ^ |   +8 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.
•  » » » » » 18 months ago, # ^ |   +8 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.
 » 18 months ago, # |   +43 Less than 10 minutes to the start! GLHF
 » 18 months ago, # |   +57 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.
 » 18 months ago, # |   +13 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.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 18 months ago, # ^ |   +16 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]$).
•  » » » » 18 months ago, # ^ |   0 Oh ok, I see. Thanks!
•  » » 18 months ago, # ^ |   +11 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 mul only 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}$?
•  » » » 18 months ago, # ^ |   +23 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.
•  » » » » 6 months ago, # ^ |   0 Why are you trying to reduce the log?
•  » » » » » 6 months ago, # ^ |   0 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).
•  » » » » » » 6 months ago, # ^ |   0 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.
 » 18 months ago, # |   +8 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)
•  » » 18 months ago, # ^ |   +16 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).
•  » » » 18 months ago, # ^ |   +16 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
•  » » » » 18 months ago, # ^ |   +16 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.
•  » » » » » 18 months ago, # ^ |   +5 I see
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +29 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: 2 pointers. At all times, the set of lit candles is a contiguous subsegment of the candles (considering their fuses). We can keep this subsegment and the current two waves of moving candles (one going to the left and one going to the right). This solution has complexity $O(n)$ after an initial sorting. Dijkstra. Given two candles $i, j$ we put a directed edge between $i$ and $j$ if $i$ can lit up $j$; and the weight of such edge is $|M_j-M_i|$. The answer to the problem is given by the distances from candle $0$ to all other candles. Sadly the graph I have described may have $O(n^2)$ edges. Notice that the distances do not change if we put the edge $i\to j$ only if there is not another fuse between $M_i$ and $M_j$ that can lit up $j$. With this reduction of the edges, each vertex has in-degree $\le 2$ and therefore the total number of edges is $O(n)$. This solution has complexity $O(n\log(n))$.
•  » » » » » 18 months ago, # ^ |   +5 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
•  » » » » » 18 months ago, # ^ |   +24 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.
•  » » » » » » 18 months ago, # ^ |   +16 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.
 » 18 months ago, # |   +35 We hope you liked the problems.For upsolving (you can switch to english using the menu on the top-right): Candele (the author is cip999) Compleanno (the author is wil93) Ristorante (the author is dario2994)
 » 18 months ago, # | ← Rev. 2 →   +38 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.