When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

harniver's blog

By harniver, 5 years ago, In English

OII logo

For the fourth 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 will start on 2019 September 18th, 10:00 CEST and will end on 2019 September 19th, 22:00 CEST.

The contest 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 22:00 CEST regardless of your time window.

If you want to participate, you must:

  1. Visit the contest website: https://open.oii2019.ga/
  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 here 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
  • +102
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The link for the training website https://mirror.oii2019.ga/ doesn't seem to work.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

hi harniver may i ask if problems will be available after the contest? So people can upsolve or something? Thanks :)

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

    Yes they will, thanks for asking. I will immediately update the announcement with info on that!

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I can't open the contest website.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

seems like the server is down. Please check

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Yes, the whole network of the Pisa university (where the contest is hosted) went down. Unfortunately, we have no way to intervene on this issue and we can just hope it will be fixed as soon as possible :(

    When the network will be up again, we will reopen the time window of anybody which had already started the contest, so that you will be able to restart working on it with your remaining time. Sorry for the inconvenience :((

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

      We are trying to figure out the seriousness of the problem... if things are not going to get better soon we will re-import the contest on some cloud servers

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      The contest is now back online, if you had your time window reduced by the shutdown, consider registering another fresh account. I am truly sorry :-(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the server down? My solution has been compiling for 10 minutes without any sign of getting evaluated.

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

    Welp the contest has finished for me and my solution is still not compiled :D

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I have been waiting for one hour, but my solution is still not compiled.. What is a problem? ;(

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

    Workers went down again... thanks for signaling the problem, we are going to fix it in few minutes

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

      Workers went down again...

      Yup, workers doing nothing is an Italian tradition.

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

    I reached the "tech guys", but they are in a bus right now :-( They should be able to fix it in about 30 minutes

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've just started the contest and it says that only ~3:50hrs is remaining :|. I am allowed to start my window any time in the above time frame ( maybe even at 1 hr remaining) and still get whole 5 hrs window, right? I mean, as far as I have seen all of the window featured contests support this. Is this supposed to be like this or have you guys missed to handle that? Can you look into this issue? harniver

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    but the contest will end at 22:00 CEST regardless of your time window.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, shouldn't it be void Budget(long long B); instead of void Budget(int B);?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    (I just replied in the system) for the inputs provided, the answer always fits in an int

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Was problem C last subtask necessary for school olympiad? IOI syllabus is against modular inverses.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    store $$$(x, p)$$$ as an interval $$$(x-p, x+p)$$$, merge intervals if they overlap or are at most $$$2*d$$$ apart. Interval $$$(l, r)$$$ should call $$$posiziona((l + r) / 2, (r - l) / 2)$$$

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you install a sprinkler at position $$$P$$$ and let it run for $$$T$$$ seconds, you can associate it with segment $$$[P - T, P + T]$$$. The cost for that segment is of course $$$C + T$$$. Now, notice that a seed at position $$$X$$$ and depth $$$Y$$$ will be watered by a sprinkler if and only if the interval $$$[X - Y, X + Y]$$$ is entirely covered by the interval associated with that sprinkler.

    That being said, you can turn all of your seeds into the corresponding intervals, and you now have to cover each of them with a sprinkler interval while paying minimum cost. Now, notice that if you have two segments that intersect, it is always more optimal to cover both with the same sprinkler.

    This means you can find some "components" of segments that you want to cover with the same sprinkler. Each of this components can be turned into a bigger segment, and obviously all of those new segments are disjoint. This step is $$$O(N)$$$ if the segments are sorted by increasing left point.

    Now, take two "components". If $$$2C$$$ is greater than the distance between them, you want to fuse them and cover them with the same sprinkler. You only really need to do those decisions for pairs of consecutive components, so you have $$$O(N)$$$ checks to do.

    Overall complexity is $$$O(N \log N)$$$, because you have to sort the segments.