wil93's blog

Italian Olympiad in Informatics (OII) 2016 — Online Contest

By wil93, 8 years ago, In English

OII logo

For the first 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!

The contest timing will be USACO-like: it will be open for 14 hours but you will be able to compete for up to 5 hours (you can decide when to "start" your time window, after the login). Participation will be available upon registration to the Italian trainings website (localized also in english).

1. The problems will be available in both English and Italian.

2. The time window will start at 2016 September 16th, 10:00 CEST and will end at 23:59:59 CEST.

3. Tasks will be IOI-like (with graders) and you will have 5 hours to solve them.

4. The languages allowed are: C, C++, Pascal.

Note: you can decide when to start your 5 hour time window, but remember that the contest will end at 23:59:59 CEST regardless of your time window.

If you want to participate, you must:

  1. Visit the training website: https://cms.di.unipi.it
  2. Click "Sign up"
  3. Fill out the form and then confirm
  4. Visit the contest list: https://cms.di.unipi.it/contests
  5. Click on the OII 2016 National contest list entry
  6. Log in with the same username and password you used to sign up
  7. If the login is successful you are now ready to participate, just wait for the contest time window to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  8. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  9. Good luck and have fun!

Can't wait??

This is your lucky day! You can participate right now to the OII 2016 Practice round (which sports very nice problems, authored by Delfad0r, mark03, cip999 and filippoqua) available until September 14th, 23:59 CEST (click here to see the countdown!). You just need to choose "OII 2016 Practice round" from the aforementioned contest list.

For this contest:

  • You will have a 5 hour time window as well.
  • The languages allowed are: C, C++, Haskell (sadly no Pascal!).

Ranking

  • The real-time ranking for the practice round can be found here.
  • The ranking for the national contest will be available here when the contest ends (now it just shows a 404).
  • Vote: I like it
  • +56
  • Vote: I do not like it

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

I'm really interested in how national competitions happen in different countries.

Why is Italian national contest being held so early? The study year has just started, how were students supposed to qualify or to prepare for it? And how is Italian IOI team formed?

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

    The national contest is the first step towards the qualification for the IOI. The ~30 best ranked students are allowed in the next selection (which is a residential course session with a final contest). Then, after 2-3 more similar selections along the year, the IOI team is chosen in April-May.

    To qualify for the national contest, easier competions are held in the previous scholastic year (in most schools of the country).

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

Nice problems!

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

the contest ended and results is still not available :(

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

    Whoops, I forgot. Now the ranking is online :)

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

My solution for problem lungomare:

Let x(i) be D(i — 1), h(i) be P(i — 1) (I prefer 1-indexed :D).

Let f(i) be the minimum value to go from 0 to the i-th point and go refresh at the beach there. Then:

f(i) = min(x(i) + h(i), max(f(j), x(i) — x(j) + h(i) + h(j))) for all j from 1 to (i-1).

Observation 1: if there is some i such that x(i) + h(i) >= x(i + 1) + h(i + 1), then i-th point is useless, we can just go to (i+1)-th and get a better result.

Observation 2: if x(i) + h(i) < x(i+1) + h(i+1) for all i, then f(i) <= f(i + 1).

  • If we go from i to (i+1), then of course f(i) <= f(i+1).

  • If we go from k < i: assume f(i) > f(i + 1), then we can use the path of f(i+1), change the path (i-th point — beach at (i+1)-th point) to the path (i-th point — beach at i-th point) and get f(i) with smaller value (as h(i) < x(i+1) — x(i) + h(i+1)).

Observation 3: if -x(i) + h(i) <= -x(i+1) + h(i+1) then max(f(i), x(k) — x(i) + h(k) + h(i)) <= max(f(i+1), x(k) — x(i+1) + h(k) + h(i)) for all k > i, that means (i+1) is useless.

So, we modify x() and h() so that x(i) + h(i) < x(i + 1) + h(i + 1) and -x(i) + h(i) > -x(i+1) + h(i+1) (using a stack).

Now to compute f(i), we can use two-pointer, find the largest k such that f(k) <= x(i) — x(k) + h(i) + h(k), and we only consider k-th point and (k+1)-th point, as f() is increasing and -x() + h() is decreasing.

Just wonder if this solution is correct or not, since the test data seems quite weak.

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

I just can't believe how weak the tests for Lungomare were — 53 points, 100 points.

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

Is there a way to retry the problems now?

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

Can someone post the problem statements?

They are not visible on the judge now.

→ Reply