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

Автор wil93, история, 7 лет назад, По-английски

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

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

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

Will the ranking list contain unofficial participants?

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

The ranking isn't working.

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

    Please read the last paragraph carefully.

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

      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"?

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

        Maybe because one shouldn't ask such questions.

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

          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?

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

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.

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

How to solve 3rd problem (specchi)

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

    Contest is not over yet.

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

    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 .

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

      How did you solve Corteo?

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

        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.

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

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

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

Where can i see and submit last year OII tasks?

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

So how does one solve the problems?

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

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

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

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

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

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

        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.

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

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.