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!
Is it possible for students from other countries, which are not listed among the 60 countries, to participate just for practice and fun?
Yes, everyone is invited to participate in the mirror contest
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
We hope you will all enjoy the contests. Good luck!
Good luck! hf
Is there a live scoreboard for the official contest?
I will prefer if its posted only after the mirror contest gets over
If you don't want it, just don't look at it. I care more about Scarlet's preferences.
there was a poll conducted in last years boi blog and the result was that the scoreboard(both mirror and official) would be hidden. https://mirror.codeforces.com/blog/entry/80321?#comment-665681
Last year was 2020, today is 2021. I agree with scarlet Johansson, sorry.
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)
How does one solve Servers and Watchmen?
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)$$$
Could you elaborate on how you use this to handle type
C
queries please? I'm a bit of a noob at centroid decompositionWe 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 ;-)
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
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).
Centroid decomposition (see subtask 2)
Server $$$i$$$ reaches server $$$j$$$ at time $$$t$$$ if the edges on the path $$$i$$$ -- $$$j$$$ have increasing add times, and the last add time is at most $$$t$$$.
Fix the centroid vertex $$$c$$$. For a vertex $$$i$$$, we call
To answer type Q queries (on vertex pair $$$i$$$, $$$j$$$, at time $$$t$$$) such that $$$c$$$ is on the $$$i$$$--$$$j$$$ path, we check that the join time of $$$i$$$ is at most the leave time of $$$j$$$, and the reach time of $$$j$$$ is at most $$$t$$$.
For type C queries (on vertex $$$i$$$ at time $$$t$$$), to count the number of vertices $$$j$$$ reachable from $$$i$$$ at time $$$t$$$, such that $$$c$$$ is on the $$$i$$$ -- $$$j$$$ path, we do sweepline on time, and maintain a indexed set of leave times of vertices with reach time at most the current time. When a type C query comes, we add the number of currently reachable vertices with leave time less than the current time to the answer to the query.
After these calculations, delete the centroid and repeat for the remaining subtrees.
Total complexity is $$$\mathcal{O}(n \log^2 n)$$$.
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
I came late to the online contest, is there any way to submit to day 1 now?
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.
Analysis mode is now enabled for both contests.
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.
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 :)
Sorry, it should work now!
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?
still day 1?
![image](/predownloaded/c9/23/c92386dc31665ff42778628e6338ab0fc0b2c44b.png)
where is day 2?
What's the link for day 2?
I was using the same link
Please wait a few more minutes, we are currently setting up the contest.
Edit: It should work now :)
do I have to re-register?
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.
previous credentials not working :(
edit: working now :)
It's working for me now
Its showing "Failed to log in" for me, after using the same username and password.
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.
Thank you all for the amazing problem set. Really enjoyed both days of contest!
+1 The problems are really nice
Did someone get 100 points with aliens trick in Prisoner?(I got 80 with 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.
I did.
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
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
If a prisoner starts rebelling at a time $$$<= T$$$, then it will rebel no matter how you block the cells. For all other prisoners compute a value $$$low_i$$$ denoting the lowest index of a prisoner you can block so that the i-th prisoner doesn't start rebelling, this can be easily calculated with a stack. So if you block a cell in the segment $$$[low_i; i - 1]$$$ then the i-th prisoner doesn't start rebelling. Now you can repeat the following D times — pick a cell that can block the most prisoners, and put a mattress on it and remove the prisoners whose segments contained that cell, and this can be easily implemented by a segment tree in $$$O(N log N)$$$, however it might get TLE because the limits are very strict(I struggled quite a bit during the contest to get 100 points).
How can I do upsolving?
Is test data published anywhere?(since ojuz usually uploads the problems to oj.uz).Upsolving window on cms was only of 3 hours
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.
Thanks lumibons it was a really nice competition. I really enjoyed it.
You can solve all the problems here: https://oj.uz/problems/source/552
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.
Day0's testdata is broken. Can you fix it?
Will you hold online contest of BOI2022?