dario2994's blog

Italian Olympiad in Informatics (OII) 2020 — Online Contest
By dario2994, 3 years ago, In English

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:

  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"
  3. You can now log in with the same username and password you used to sign up
  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).

  • Vote: I like it
  • +156
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

I can't enter the webpage.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for your concern :D

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        The registration webpage is up and running.

        Whoever registered before the downtime shall register again.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I can't enter italian training website

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the expected difficulty of problems? Like in terms of codeforces div2. A/B/C etc?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Ok, thank you!

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -46 Vote: I do not like it

      The hardest is only div.1C? Seems much easier than CNOI....

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        Probably most OI's are much easier than CNOI....

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

          At least I think JOISC do not.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            Most is not all.

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +29 Vote: I do not like it

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

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunate that Java is not available though, I guess you can't get to IOI in Italy if you just use Java.

→ Reply
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

The practice contest just started! GL & HF

→ Reply
»
3 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Less than 3 days before the contest, good luck to everyone participating!

→ Reply
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Only two days to go! Get ready and sharpen your keyboards!

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Very nice problems!!

→ Reply
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

armyalpaca is very strong, he will win OII for sure!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I predict that davi_bart will win OII2020 and that you and Kaey will get into top3 ;)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      Why is everybody sleeping on iwannad?

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 7   Vote: I like it +50 Vote: I do not like it

      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!

      1. Davide Bartoli (davi_bart, 268/300 points)
      2. Filippo Casarin (Virv, 253 points)
      3. Taulant Arapi (me, 233 points)
      4. Lorenzo Massi (rocks03, 223 points)
      5. Tommaso Dossi (Kaey, 180 points)
      6. Tommaso Lunghi (Darkeld, 176 points)
      7. Francesco Lugli (franfill, 165 points)
      8. Armando Pellegrini (armyalpaca, 160 points)
      9. Fabio Giovanazzi (158 points)
      10. 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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any tips on how to stop writing code full of bugs? D:

        → Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I think taulant has a good chance to win, but for sure it will be a very exiting contest. GL to everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Obviously TheScrasse is gonna win it. Btw good luck to all the others, including me.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I missed the practice contest. Is there any place where I can see/try some of the problems from there? Thanks in advance!

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

and now where can we submit those problems?

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +71 Vote: I do not like it

    I'm actually curious about this too. These are the best solutions I know:

    1. $$$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.
    2. $$$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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      How do we prove that we can safely omit an item? Can't it add bits after few iterations?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Less than 10 minutes to the start! GLHF

→ Reply
»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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}$$$?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why are you trying to reduce the log?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +29 Vote: I do not like it

        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:

        1. 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.
        2. 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))$$$.
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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

          → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

We hope you liked the problems.

For upsolving (you can switch to english using the menu on the top-right):

  1. Candele (the author is cip999)
  2. Compleanno (the author is wil93)
  3. Ristorante (the author is dario2994)
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

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.

→ Reply