lumibons's blog

By lumibons, 4 years ago, In English

The year is 2021. Like every year, contestants from all of the baltic countries meet for the Baltic Olympiad in Informatics. Well, not entirely... One small virus still holds the entire world under its spell. And life is not easy for BOI contestants who have to participate remotely from their own homes...

This weekend, the Baltic Olympiad in Informatics 2021 (BOI 2021) is going to take place! BOI is a programming contest for secondary school students from countries around or close to the Baltic sea. This year, around 60 contestants from Denmark, Estonia, Finland, Germany, Latvia, Lithuania, Norway, Poland, Sweden and our guest countries Israel and Ukraine will compete against each other, solving difficult problems of algorithmic nature. Each participating country sends 6 contestants from their national olympiads which take place in the months beforehand.

The contest consists of two days, Saturday and Sunday, on each of which the contestants have 5 hours to solve 3 problems of varying difficulty. Each problem is worth 100 points that are distributed into multiple subtasks with different constraints that allow the participants to earn partial scores. During the contest, each participant receives the verdict of the execution of his/her solutions on all tests.

BOI 2021 was planned to be hosted in the beautiful city of Lübeck, a historical German town on the Baltic Sea, member of the „Hanse“ trade union of cities. Now, due to the Corona pandemic, BOI is run for the second year in a row as a virtual event only with contestants participating from their own countries in a proctored online setting. Next year, BOI 2022 is hopefully really going to take place in Lübeck. For more information about the contest, visit the official website at boi2021.de.

Furthermore, if you want to experience the struggle of a BOI contestant for a medal firsthand, we are happy to invite you to participate in an online mirror of BOI 2021! The online mirror will be held on Saturday, April 24, 2020 at 14:00 UTC and Sunday, April 25, 2020 at 14:00 UTC, the same days as the official contest, but with 6 hours delay. The mirror will be held on CMS which is also used for the official contest. To register for the online mirror, visit opencontest.boi2021.uni-luebeck.de. You need to register there, before participating.

We wish everyone and in particular all BOI contestants an enjoyable contest despite these challenging circumstances!

-- BOI 2021 committee

Update: The first contest is over! You can find the results of the intense competition on the scoreboard here.

Update: We hope that all participants in the online mirror enjoyed the problems! Standings can be found here. And don't miss the mirror of the second day tomorrow if you want to know how the story about the BOI participant who turned art thief continues...

Update: And that's it! The official contest of the second day is over, too. Congratulations to all participants on their performances! We hope that everyone enjoyed the problems. The combined ranking of both days can be found on the same scoreboard as before. (And of course, the mirror of day 2 will start in less than an hour...)

Final Update: After the committee took a small break to catch up on the sleep missed over the last weekend, we finally got around to update the official website with all the information that was still missing. Firstly, we have added the official results of this year's BOI. Congratulations again to all the medalists and in particular to the overall winner of BOI 2021, almogwald! Also, you can now find all the tasks on the website, including spoilers and test data.

Finally, we were really impressed to see the strong competition in this year's contest. While not being able to meet anyone in person, we hope that we will see some of participants again next year in Lübeck. Until then: Auf Wiedersehen!

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible for students from other countries, which are not listed among the 60 countries, to participate just for practice and fun?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    Yes, everyone is invited to participate in the mirror contest

»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

As a member of the Israeli team this year, I'd like to thank the organizers for having us as guests this year for the first time!

I hope we all have a great contest :D

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there a live scoreboard for the official contest?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    I will prefer if its posted only after the mirror contest gets over

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +78 Vote: I do not like it

    The scoreboard is not live due to the online nature of the contest, but publicly available after the end of each contest on both competition days (see the update)

»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like it

How does one solve Servers and Watchmen?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I solved servers using centroid decomposition. We need to add weights to the edges of tree. If $$$"S a b"$$$ was $$$i$$$-th query the weight of $$$(a,b)$$$ will be $$$i$$$. Then by the time of $$$i$$$-th query we know that $$$b$$$ contains chunk $$$a$$$ if and only if the path from $$$a$$$ to $$$b$$$ has increasing weights and the last edge on the path has weight less than $$$i$$$. So now we can solve this problem offline using centroid decomposition and some data structure like fenwick tree, which will make the total complexity $$$O(nlog^2n)$$$

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

      Could you elaborate on how you use this to handle type C queries please? I'm a bit of a noob at centroid decomposition

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    We will publish solution outlines at some point on the official website. However, that might only be in a few days — we will announce it here once that happened. Until then, you have the opportunity to continue trying to solve the problems on your own ;-)

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

    In problem Servers, I come up with the following idea:

    If server a stores data chunk d, then there should be an increasing path form node d to node a if we add weighted edges to the graph (tree), where weights are just the query indexes.

    Now Q type of queries can be solved using binary lifting if we build the tree offline and we can check whether these two nodes are in the same component using DSU.

    This increasing path idea maybe can be applied to C type off queries. I don't know exactly how, but the idea is the number of servers that contains chunk d is the number of nodes that has an increasing path from d

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

      Yep, centroid decomposition as... well... MrDecomposition mentioned above does utlilise this fact of monotonous edges. Ended up being a bit late in implementing that :( Also, you can implement the same idea for "Q A B" without UFDS by simply comparing if the parent edge of A is added at a time less than the query time (after, obviously, checking if the paths are monotonous).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it
    hint
    solution
  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it +27 Vote: I do not like it

    I only got 70 on watchmen but here is my method.

    We denote the length of the path on the henchmen on vertex $$$a$$$ as $$$ped[a]$$$. For each vertex $$$v$$$ with a watchmen on it, we will duplicate it $$$ped[v]$$$ times, the $$$i$$$-th duplication stores the minimum time such that residue modulo $$$ped[v]$$$ is $$$i$$$. We denote this $$$w[v][i]$$$.

    Now we will just have to figure out how to draw edges such that we reduce the number of edges.

    Firstly, for vertices that are duplicated, we draw edge with weight $$$1$$$ from $$$w[v][i]$$$ to $$$w[v][(i+1)\%L]$$$. This just means staying at that edge. We also draw edges to the adjacent vertices in the henchmen's path (with conditions about not getting noticed). The number of additional edges here is $$$O(l^2)$$$.

    For edges that connect a vertex without henchmen to a vertex with henchmen (there are $$$O(M)$$$ of these), we have to split this into $$$2$$$ parts. Say $$$a$$$ is the vertex with the henchmen and $$$b$$$ is the vertex without. For edges go $$$a \to b$$$, we make a new node, $$$a'$$$ that is the minimum time over all $$$w[a][i]$$$. Then connect $$$a'$$$ to $$$b$$$. We only have to create $$$a'$$$ once, so the number of additional edges here is $$$O(l^2)$$$. For edges that go $$$b \to a$$$, we want to connect $$$b$$$ to all $$$w[a][i]$$$ but this will create $$$O(Ml)$$$ edges, so we reduce this number by connecting only $$$2$$$ edges. One of them has weight $$$1$$$, which is going into $$$a$$$ immediately, and the other is we wait for the henchmen to pass and go into the node. This is equivalent because we have edges from $$$w[a][i]$$$ to $$$w[a][(i+1)\%L]$$$.

    Now for the interesting part, the edges that connect the vertices where there are $$$2$$$ different henchmen, note that there are $$$O(l^2)$$$ such pairs. We make this edge directed first. So the edge is $$$a \to b$$$. Suppose $$$w[a][i]=t$$$, then we can reach $$$w[a][i]$$$ at time $$$t+ped[a]$$$ by going around a cycle. When we want to update $$$w[b]$$$ from $$$w[a][i]=t$$$ we want to update $$$t+1,t+1+ped[a],t+1+2ped[a],\ldots$$$ but this will take add a $$$O(l^4)$$$ to our complexity. So we add a "hidden layer" $$$w[h]$$$ of size $$$ped[b]$$$ between $$$a \to b$$$. $$$w[a]$$$ connects directly to the hidden layer. The hidden then has edges from $$$w[h][i]$$$ to $$$w[h][(i+ped[a])\%ped[b]]$$$ which allow us to only add $$$O(l^3)$$$ to our complexity. This has to be sped up for 100 points but I am not sure how.

    Using Dial's algorithm (I assumed the answer is always less than $$$10^7$$$), we have a $$$O(N+M+l^3)$$$ algorithm.

    My implementation is here

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I came late to the online contest, is there any way to submit to day 1 now?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Unfortunately not right now. We currently prepare the servers for the live contest tomorrow. We may enable analysis mode tomorrow after the day-2 contest for both contests.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Analysis mode is now enabled for both contests.

»
4 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Is it possible to optimize a O(n * sqrt(n) * log(n) + n * log^2(n)) solution with persistent segment tree to pass servers? My implementation was running at about 3s.

Edit: It actually runs much slower than I thought, so it definitively shouldn't work.

»
4 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

Also I don't know if this is intentional, but the day 1 standings for the open contest are behind a login thing and my login details don't work

Edit: Not anymore :)

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hello ! I could not attempt the online mirror because of some prior commitments. Is there any way in which I can attempt day 1 problems?

»
4 years ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

still day 1?
image
where is day 2?

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

    What's the link for day 2?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Please wait a few more minutes, we are currently setting up the contest.

    Edit: It should work now :)

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +39 Vote: I do not like it

      do I have to re-register?

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

        No, you should be able to use the same credentials as yesterday.

        Edit: There was a configuration error on our side. It is fixed now.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +57 Vote: I do not like it

      Its showing "Failed to log in" for me, after using the same username and password.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        You are right, it was a configuration error on our side. Please do not register a new account as the contest results cannot be merged in that case. It should work now with your previous account.

»
4 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Thank you all for the amazing problem set. Really enjoyed both days of contest!

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

Did someone get 100 points with aliens trick in Prisoner?(I got 80 with it)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I also got 80 and I don't think it is possible to get 100 due to the bounds on n,d = 2*10^6, unless you are able to optimize the inner dp to run on O(n) instead of O(n*log(n)). Actually I think they made the bounds that high to stop lagrange from getting 100 pts, because there is another more efficient solution described in the analysis that does not involve lagrange.

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

    I did.

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

    At first I was working with the alien trick approach too. But then I was trying to solve the d-parameter-less version with good complexity, and the greedy approach clicked. In fact, it's not the only problem. I vividly remember getting alien-trick-rolled in few other problems- (a) get a vibe and verify the function is convex (b) think about the parameter-less version, get a greedy approach to solve that (c) but wait, I can use this greedy approach in the actual problem :v

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

    Can somebody describe the process in detail, since I noticed that you can't do the standard trick. At least for me, I get a problem when C(l) is > d where C(l) is the minimum number of mattresses for an optimal solution where a cost of a mattress is l. I saw some codes use the formula:

    if(C(l) > d) r1 = dp(l) — l*C(l) r2 = dp(l+1) — (l+1)*C(l) answer is r2 + (r1-r2)*(d-C(l+1))/(C(l)-C(l+1))

    where l is the biggest cost for a mattress such that C(l) >= d

    Can someone give an explanation. Thank you in advance

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Prisoner 100 points
»
4 years ago, # |
  Vote: I like it +96 Vote: I do not like it

How can I do upsolving?

»
4 years ago, # |
  Vote: I like it +78 Vote: I do not like it

Is test data published anywhere?(since ojuz usually uploads the problems to oj.uz).Upsolving window on cms was only of 3 hours

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    Sorry for the delay, but most of the committee members were a bit to exhausted to get to that right away :-) The test data is now on the website, ready to be uploaded to another online judge. Note, however, that the managers used for the interactive tasks rely on the German fork of CMS, so they might need some tweaking to get them running on another judge system.

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks lumibons it was a really nice competition. I really enjoyed it.

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

You can solve all the problems here: https://oj.uz/problems/source/552

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the statment for problem books is wrong. For subtasks 3, 4 and 5, $$$S$$$ is $$$ \geq 200$$$ instead of $$$\geq 170$$$. It is true according to the editorial and the statement I received during the mirror.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Day0's testdata is broken. Can you fix it?

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Will you hold online contest of BOI2022?