BERNARD's blog

By BERNARD, 6 weeks ago, In English

The international finals of the International Informatics Olympiad in Teams (IIOT) 2024 will be happening in the next couple of days.

It will be hosted by Syria as a hybrid event. There will be 20 participating teams from 10 different countries.

Contest format:

  • 7-10 problems (including subtasks)
  • 4 hours
  • 4 contestants and 2 computers per team

Authors of the problems used in this contest: Péter peti1234 Gyimesi, Áron mraron Noszály, Bernard BERNARD Brahimsha, Alessandro bortoz Bortolin, Zsolt birka0 Németh, Mihnea-Vicențiu MVB Bucă, Péter Csorba, and Gabriella Blénessy.

People who helped preparing the problems: davi_bart, Kaey, Virv, ApraCadabra, and stefdasca.

The practice round will be tomorrow on Friday, 10 May 2024, 17:30.

The main contest will happen on Saturday, 11 May 2024, 09:30.

For more info about the contest you can visit iio.team and iiot2024.sy.

You can find the problems of the previous editions here.

Wish the participating teams a good luck!

UPD: An unofficial list of participating teams could be found here: codeforces.com/blog/entry/129019

UPD2: The contest is happening right now, you can follow the live ranking at: https://gara.squadre.olinfo.it/ranking/ and it will become frozen during the last hour of the contest.

UPD3: The closing ceremony is now over. You can find the final results here.

UPD4: The editorial is out. You can find it here.

UPD5: An online mirror will be available here (live ranking is available here). It will start on Monday, 19 May 2024, 17:30 and will last for 30 hours.

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

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck to all participants! Hai Andrei!!

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Luck For You And For Syrian National Teams :)

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Great news! Wonderful job guys. Wish you the best of luck.

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Looking forward to a great competition!

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Goodluck everyone!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me how to register

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Live ranking?

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Final scoreboard?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    The ranking will be unfrozen at the closing ceremony.

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there a different way to solving triangles instead of $$$O(N \sqrt{N})$$$ with brutal casework?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +16 Vote: I do not like it

    The way I solved it was pretty easy.

    Let's see how a bad triple looks like.

    a ---> b

    b ---> c

    a ---> c

    For one of the vertex, its in_degree will be 2.

    Let's consider that special vertex to count the number of bad triangles.

    d(i) =def= the in degree of vertex i

    total triangles = C(n, 3)

    bad triangles = sum{C(d(i), 2) | i = 1...n }

    Now we just need to update the number of bad triangles in order to find the number of good triangles.

    Here's how we update :

    let's assume the edge was (i ---> j)

    bad_triangles -= C(d(i), 2) + C(d(j), 2)

    d(i)++;

    d(j)--;

    bad_triangles += C(d(i), 2) + C(d(j), 2).

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yeah, pretty easy solution, nice

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Have you solved the problem Esoteirc Bovines?

        I had a solution of time complexity of O(N * lg A * lg A). Where I use a binary search on my answer and Trie to count the number of pairs that gave me xor value of less than equal to my mid.

        But unfortunately this solution was not working to give 100 points.

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

          Yeah, I managed to solve it, the best way to summarize it is to call it "Parallel binary search on a trie". Imagine you are doing binary for a certain $$$answer$$$. Then, while traversing the trie for the current number, the only thing that matters is whether the current bit in $$$answer$$$ is set or not. Having this in mind, we can do the following procedure (which is implicitly binary search) — greedily set the bits of $$$answer$$$ from the topmost to the bottommost. Imagine we are doing the query for every number in $$$A$$$ separately and keep a pointer, which is pointing to the node in the trie we are located currently. Let the node for the $$$i_{th}$$$ number be $$$u_i$$$. At first $$$u_i=root$$$ for every $$$i$$$. Then, by adding a bit, we will move the pointer for every $$$i$$$ to the child with the same bit as $$$a_i$$$, if we decide to put a bit $$$0$$$, or the opposite bit as $$$a_i$$$, if we decide to put a bit $$$1$$$. It's easy to see what bit you should put in $$$answer$$$, as you can easily tell whether the count of pairs with $$$xor \leq answer\ |\ 2^{bit}$$$ is less or more than $$$K$$$. Repeat this procedure $$$log_{\,2}\ a_i$$$ times and you will find the answer in $$$O(N\ log_{\,2}\ a_i)$$$.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Here is a harder version of this problem 283E - Cow Tennis Tournament.

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

      It's funny that JOI Spring Camp 2024 had a problem which required the same observation — table tennis and I could not see it when I participated, could not see it now

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the ranking is not opening now?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

congrats for all teams who get medals

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Will problems be available for upsolving any time soon ?

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

The mirror is currently running.