dario2994's blog

Italian Olympiad in Informatics (OII) 2018 — Online Contest
By dario2994, history, 6 years ago, In English

OII logo

For the third 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 24 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 problem statements will be available in both English and Italian.

2. The time window will start on 2018 September 14th, 10:00 CEST and will end on 2018 September 15th, 10:00 CEST.

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

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

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

If you want to participate, you must:

  1. Visit the training website: https://training.olinfo.it
  2. Click "Sign up" (if you haven't already done it last year!)
  3. Fill out the form and then confirm
  4. Visit the contest list: https://training.olinfo.it/contests
  5. Click on the OII 2018 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 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)
  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!

Ranking

The final ranking of the online contest is available here.

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

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i hope it will be a great contest! did you save the past contest problem statement in english?

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

Is there going to be an editorial afterwards?

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

    We will publish a slideshow with a brief presentation of the solutions, if that is what you mean. For now we have it in Italian, but if there is sufficient interest for having it in English we can translate it!

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Thanks for the interesting contest. Where can we upsolve the problems, dario2994?

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

I'm pretty sure I kept getting WA on the last test from the last subtask of problem 1 and I quitted after not being able to understand problem 2's statement. Now the ranking shows I got 100 on problem 1. WTF?

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

    Same happened to me. They announced they discarded the test in the end.

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

      Exactly. We are sorry for that, last testcase was wrong (it did not satisfy the assumptions described in the statement and the output was wrong).

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

Thank you for the contest, I really enjoyed solving the problems. If anyone is interested, here you can find my solutions, feel free to ask about them.

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

Will some participants get virtual or imaginary medals?

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

Any ideas for incendio?

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

    First for an O(N2logN) solution:

    Binary search the answer and run BFS from all fires at once to get a binary matrix, where 1 represents a cell where fire spread and 0 representing a safe cell. The answer is whether there exists a path from (0, 0) to (N - 1, N - 1) consisting only of 0 cells.

    Now, the trick is to check whether there is an answer in a slightly different way:

    Define a 1-path to be a path that starts somewhere on the left/down sides of the matrix and ends on one of the right/up sides of the matrix such that all its cells are ones and we allow movement in all 8 directions (i.e. the 4 initial directions and the 4 diagonal directions, this is crucial for the solution to work). I claim there exists a normal path from (0, 0) to (N - 1, N - 1) if and only if no 1-path exists (formal proof left as an exercise, but a hint is to think of the maxflow-mincut duality).

    With these in mind, it's actually not that hard to check for the existence of a 1-path without explicitly building the whole matrix. We build a graph with M + 2 nodes, one for each of the fires and 2 for the left/down and right/up sides of the matrix. We connect 2 fires with an edge if there is a 1-path starting at the first fire and ending at the second fire (this can be checked with some casework in constant time). We connect one side and one fire with an edge if the fire can reach that side of the matrix. The answer is whether there is some undirected path in this graph from one side to the other side.

    This runs in time O(M2logN) and may only be enough for 92 points. The trick is noticing that there is a certain "time" in the binary search when a given edge becomes active. Thus, all we need to do is process the edges in increasing order of "time" and stop as soon as the 2 sides become connected, maybe with some disjoint sets. This would be fast enough if we wouldn't need to sort the edges in increasing order of "time".

    The final trick to get rid of the sorting is to realize this whole procedure is akin to Kruskal's algorithm for finding MSTs and we can run Prim's algorithm instead, which doesn't need the edges to come in sorted order and can be implemented in time O(M2) if the priority queue is a simple array instead of a binary heap (basically, just brute force for the minimum value each time extract_min is called and do all updates in constant time). This is fast enough for 100 points, although some constant optimization might be needed to make it fit in time.

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

      I claim there exists a normal path from (0, 0) to (N - 1, N - 1) if and only if no 1-path exists (formal proof left as an exercise, but a hint is to think of the maxflow-mincut duality).

      After this I understood all the solution thank you.

      → Reply