wil93's blog

Italian Olympiad in Informatics (OII) 2017 — Online Contest

By wil93, history, 7 years ago, In English

OII logo

For the second 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 2017 September 15th, 10:00 CEST and will end on 2017 September 16th, 10:00 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++.

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 (note that the URL was updated since last year)
  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 2017 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 ranking for the national contest will be available here when the contest ends (now it just shows a 404).

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

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

Will the ranking list contain unofficial participants?

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

The ranking isn't working.

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

    Please read the last paragraph carefully.

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

      Out of curiosity why say that rather than "They mention that the ranking will only be available after the contest at the end of the post"?

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

        Maybe because one shouldn't ask such questions.

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

          He didn't ask a question he just pointed out a link doesn't seem to be working.

          It is true the post mentioned this but misreads are inevitable and I don't see how trying to make someone feel bad about what would otherwise be a useful comment (if the organisers intended the link to be working but it in fact wasn't) achieves anything good?

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

I signed up, and when I try to log in it says "Welcome back Rudy69" and then "Login Error" and doesn't log me in.

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

How to solve 3rd problem (specchi)

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

    Contest is not over yet.

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

    I think that the contest is over so I'll explain my solution (I had a stupid bug so I wasn't able to pass it during the contest).

    The main idea is that when we add a mirror we know that there will be two paths which will be split in two and then their parts merged (one of the paths is vertical and the other one is horizontal).

    Also the other observation (which is actually pretty obvious) is that if we shoot the laser from point X and it goes to point Y, then if we shoot from Y it will go to point X.

    This can be done with link/cut tree. For each component (tree or actually path) we store the two ends of the path. Then for every query we can simply pick the other end which is stored for the query point's component.

    Every time we add a mirror we will create a two new nodes which will be the link between the different parts. Also we will add these verices to some sets to easily find which is the closest mirror to the left, right, down and up for the next queries.

    This solution is which runs fast enough.

    In the contest I forgot that we can create a cycle with the mirrors. I fixed it in the last minutes but couldn't submit, because the contest was over.

    There is another solution which can pass for 100 if implemented well using sqrt decomposition. In short for every mirror we store where we will be after operations. This way we need to update nodes. Then for the query we will make at most jumps. The complexity will be .

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

      How did you solve Corteo?

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

        Do a bfs from each node to get dist[i][j], the distance between vertices i, j for all pairs (i, j).

        Binary search the answer d.

        To determine if d is achievable, we do a bfs on the pairs (x, y), where x is the position of the first group and y is the position of the second group. Initially, (s1, s2) can be reached (if dist[s1][s2] ≥ d). From each such pair, we go to all the pairs (x', y) where there is an edge between x and x' (and dist[x'][y] ≥ d) and also all the pairs (x, y') where there is an edge between y and y' (and dist[x][y'] ≥ d). d is valid if and only if (d1, d2) is reachable.

        What is the complexity of this bfs? For each edge (u, v), it contributes to the edges between pairs (x, u) and (x, v) and (u, x) and (v, x) for any x. Thus, there are O(MN) edges and O(N2) vertices, so the bfs takes O(MN) time.

        The total complexity is because of the binary search.

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

          And how did you solve caduta?

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

            My solution for 91 points is outlined below if you're interested

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

Would we be able to upsolve the problems anywhere after the contest?

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

Where can i see and submit last year OII tasks?

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

So how does one solve the problems?

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

How to solve first problem (the one with the dominoes)?

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

    Here's the pseudocode of my solution for 91 points

    get a list of all dominos that aren't knocked down
if there are none:
	return ok
let L = index of the first domino not knocked down
let R = index of the last
for all i from 0 to n-1:
	for all j from R-height[i]+1 to L-1:
		swap i and j
		if all knocked down:
 			return i and j
		swap back i and j
if none found:
	return impossible
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So why does this work fast enough? (It's not clear to me how many times the three inner loops execute.)

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

        I'm honestly not sure and was surprised when it passed the subtask with N <= 10^5. Clearly the outer loop is O(N) and the most inner loop is also O(N) (if it gets run), the second loop however is a bit of a mystery. I've tried to come up a worst case test for it but it seems like nearly everytime the second loop is run at all it tends to find a solution. Here's my code if you want to try and test it: https://pastebin.com/Bqp00Cfs.

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

Can someone please give me a direct link to the problem caduta (pazza gioia) ? Because when I try the links from above to the training website it showes me the tasks from 2016.

→ Reply