Блог пользователя dario2994

Автор dario2994, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +156
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

I can't enter the webpage.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot for your concern :D

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        The registration webpage is up and running.

        Whoever registered before the downtime shall register again.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +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. :c

            We had to move the mirror to another server, for this reason the previously registered accounts went lost.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

The practice contest just started! GL & HF

»
4 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Very nice problems!!

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

and now where can we submit those problems?

»
4 года назад, # |
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)$$$)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +71 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Less than 10 minutes to the start! GLHF

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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]$$$).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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}$$$?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Why are you trying to reduce the log?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 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).

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится +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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        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:

        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))$$$.
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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)
»
4 года назад, # |
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.