Hi everyone!

I am happy to invite you to take participation in the online mirror of the Baltic Olympiad in Informatics 2020 to be held on Jul/22/2020 14:05 (Moscow time) and Jul/23/2020 14:05 (Moscow time) on Codeforces!

The Baltic Olympiad in Informatics 2020 (BOI 2020) is an individual contest for secondary school students from eleven countries (in alphabetic order): Denmark, Estonia, Finland, Germany, Iceland, Latvia, Lithuania, Norway, Poland, Sweden and Ukraine. Over 60 secondary school students compete against each other, solving difficult problems of algorithmic nature. Each country sends their top 6 contestants from their national olympiads which take place in the months beforehand. You can check out the official web page at boi2020.lv.

The contest consists of two days; each day the students are given 5 hours to solve 3 problems of various difficulty. Each problem is worth 100 points that are distributed into multiple subtasks with different constraints that allow the participant to earn partial score. For the testing, the IOI grading format is used, where the participant receives full feedback of the execution of the solution on all tests during the contest.

This year the contest was supposed to be held in Latvia, Ventspils, but is not held onsite due to the pandemic, and the students will compete in a proctored setting online. With generous help from MikeMirzayanov, we are glad to also provide the mirror contest at Codeforces for anyone interested.

Note that the contest **is not rated**. The mirror starts with a delay of 1 day, 1 hour and 5 minutes.

We wish you to enjoy the contest! :)

-- BOI 2020 committee

Martins Opmanis, Rihards Opmanis, Sergey Melnik, andreyv, Pakalns, gen, eduardische, Alex_2oo8, nvilcins, KarlisS.

**UPD1:** The scoreboard will not be public, each participant will be able to see only the results of their own submissions.

**UPD2:** Tutorial for Day 1 has been published.

**UPD3:** Tutorial for Day 2 has been published.

**UPD4:** Congratulations to full score 600 point winners WZYYN, isaf27, Arpa!

Wow!!! I was looking for a way to participate from country that's not mentioned above and thanks to MikeMirzayanov

Looking forward to great problems :)

It's pitty that is not rated. I remember similar rated mirrors on CSacademy for Balkan OI.

Thanks for contest, I hope to see more initiatives like this in future (maybe some national olympiads).

I know we are getting many such rounds from past as Opencup, but still there is a lot of unused materials.

Whats the expected difficulty ? More inclined towards Div1 I guess ?

Yes, solving the full tasks is likely in the Div1 difficulty range but that does not mean that you can't enjoy the problems. The problems are split into subtasks and the easier subtasks can be closer to Div2 problems in difficulty. You can also check out problems from previous BOIs if you are trying to decide whether to participate or not.

Link to participate ?

It is in the 'contests' menu, here. It starts in three days, so you don't need to worry now.

The standing should be hidden in the contest time following rules of IOI standard contest.

Even solve counts should be hidden in the dashboard ideally.

We are considering keeping the scoreboard hidden during the contest. I will post an update later.

Hey everyone, it is possible to proceed both ways, however, we're not sure which one is the better one. Since it is not the official contest, it is more fun to make the standings open both to participants and the spectators. Then again, it would be more realistic if the standings are hidden.

Hence, we are interested in your opinion. Vote + / –; for my reply to this comment "For public.", if you prefer public / hidden scoreboard, and + / –; for my reply to this comment "For hidden.", if you prefer hidden / public scoreboard. Please vote for an even number of replies so that my contribution stays the same. :)

For public.

For hidden.

Update: based on the public opinion, we are making the scoreboard hidden.

Update: based on the hidden opinion, we are making the scoreboard public.

I've never seen that done for a mirror contest though.

Can i look at the boi 2020 Ventspils current leaderboard?

AFAIK no.

Indeed, we will not publish the scoreboard publicly until the corresponding mirror contest has finished.

'the students will compete in a proctored setting online' Can you share more details of this?

Hi, it is requirement only for the official participants, if you participate in the mirror, you don't have to worry about it.

I was just asking out of curiosity

There are people monitoring the participation of the students in each of the countries. I think the team from each country gets together at some place and there are persons watching over them.

Are these "persons who watching over them" from the same country or representatives from an International Committee? I understand that the latter is more unlikely with the current pandemic situation but i'm curious. By the way is this how the IOI going to happen?

BOI will not be a good representative for how IOI will be proctored I’m afraid.

Regarding IOI, Singapore has started to distribute drafts of proposed proctoring requirements to the delegations. I believe these weren’t released to public because it’s still work in progress and large parts of it would only affect delegations themselves rather than students.

Having said that, let me ask the hosts if they are willing to provide some sort of short summary for how IOI is planned to run to the students & general public.

UPD: I have checked and more information is expected to be released to public in early August.

Thank you for your time

hope to be more oi contest in codeforces

If we code different subtasks in different submissions will we get points for both?

This is followed in IOI but not sure if this works on cf since this didn't work when I did vc of ceoi 19 on cf

The submission with highest score counts. You can try to combine "subtask-specific" code for multiple subtasks in one solution, but if you don't you gain points equal to your best submission anyways. These are the rules of the official contest, I'm not sure if cf will mirror them entirely.

On CF, the submission with the highest score counts, an we use the same for BOI.

Hey guys , I wanted to ask something. I do have nvedia graphics card on my computer but when I perform a simple compiling and running test on sublime, it takes from anywhere between 10 to 15 seconds to execute. So is my laptop slow or is it that it is not using card for computation? Any suggestions?

GPU is irrelevant here.

why do you say that ?

You're not doing anything with graphics or massive matrix multiplications.

One of my friend had the same problem. Make sure there's no antivirus blocking the program's execution.

Why is this contest unrated? Let people have some fun, no need to make it unrated

In problem C, the 3rd subtask should be passable with a (n + m) * logm algorithm right? Well, at least for java, the constraints seem to be too tight. I think the problem lies in the fact, that in Codeforces Java programs use quite a bit of time not related to the running time complexity (like printing just one line takes few 100ms more on java than on C++).

Please don't discuss the problem until the end of the contest.

I'm sorry, I didn't think it was important since it's unrated and there are no standings.

how to solve A ?

My approach to A goes like this, first initialize ans = n, now answer would be the smallest number between 1 and n-1, which returns 1. Now let's set a cursor named cur. Which starts in some position (let's name it x). Now we will do a binary search on [1,n-1]. If in the ith step, we do cur = cur+mid, then in the next step we will do cur = cur-mid and vice-versa. This will surely lead us to the answer. Now the fact comes, what if cur cross the bound! So we need to choose the position x cleverly. It's not hard to understand the fact that the bigger the value of C is, the bigger the moves are. So the worst case is C=N. Now we can simulate this case with a binary search to choose the position x for cur. The interesting fact about this approach is mid becomes too large or too small to intersect with previous queries! I hope this clears the doubt!

Yes I have also the same idea, but can u explain more how p is always between 1 and n (1<=p<=n). my code passes the restriction if the respond of the queries is 0s.

For n= 32, here is a picture

How to solve A,C? Also is B just checking that the triangle contains the origin?

roughly speaking, that's exactly that.

I did what you say in B but it fails first subtask. Did you pass it with that idea?

I couldn't even debug my brute force solution. My geometry is really weak :'( I got the triangle idea after writing all sorts of equations and found it is the same as point in a triangle inequality.

Swap coordinates to make A != 0, that fixed my fail on the first subtask.

Problem A : I tried it

binary search, I guess the idea is correct, but theimplementationwas hard.We are sure that

Cis between1 and N,inclusive so let thelower_bound = 0andupper_bound = NYou need to ask the middle value of

lower_bound (0)andupper_bound (N)P = (0 + N)//2there are 2 possibility:

if the result is

"1", you set theupper_boundtoPand recur.if result is

"0",you set thelower_boundtoPand recur.so finally the upper_bound and lower_bound will be the same, which is the

base case,theC = lower_bound = upper_boundNOT SURE about itWhy are u guys downvoting, it is better to say "You aren't correct" than a downvote?

I am not expecting another down votes for this.

You're oversimplifying the problem by a LOT, what you wrote isn't a solution. That's the main reason.

In B my solution passes 2,3,4,5 subtasks but it fails on first subtask. Anyone has the same problem? Or anyone has any idea how this happened?

This happened to me on A. I guess test cases are weak.

I had the same problem for my first submission.

It seems that only the first two subtasks contain corner cases like $$$S_f = P_f = 0$$$ (two zeroes and one non-zero number). I had a small bug with it.

Will there be upsolving?

Excellent contest. I enjoyed it a lot, although I couldn't AC any problem. When editorial will be published?

It would be helpful if anyone shares there approaches for the problems.

did anyone solve subtask 3 of the third problem with binary search?

it could be used, but it's not needed. you can use DSU to do that. Also, myapproach for 4th subtask had time complexity $$$O(m\cdot L\cdot \alpha(n))$$$ where $$$\alpha(n)$$$ is the inverse of Ackerman and $$$L$$$ is the amounf of different $$$l_i$$$, and it gave TLE.

DSU? Can you tell the basic logic of the solution? I had an (n + m)logm algorithm in Java (binary search + 2-color) and it didn't pass.

Look here

I used DSU by storing the distance from the root for each vertex and checking while combining if they have to the same parent and their sum is even but doesn't seem to pass. Is this the right approach or I am making an implementation mistake?

I tried to, but it was too slow (was using java tho).

My (n + m)log(m) solution for the third subtask of the third problem didn't pass, I think the constraints were too tight or maybe it's just a codeforces problem (taking more starting time for Java).

It doesn't pass in c++ too.

The time limits were quite tight to distinguish between Mo's algorithm and the faster solution.

Is link cut tree intended? :o

Was not. :D

for 4th subatsk, was an $$$O( (n+m)\cdot 200 \cdot \alpha(n) )$$$ intended, or something better? My approach had that complexity and it gave me TLE. This is my submission

It was intended... Probably your solution can be optimized.

Can you share one solution with that complexity that passes 4th subtask?

Here is the model solution for this subtask 87704876.

I am not allowed to view the requested page.

Sorry, https://pastebin.com/H7YzqBtX

Isn’t this $$$O(\max l \cdot (N + M \log N))$$$? I see path compression, but I don’t see anything like union by rank.

(But it’s some 20 times faster than my own solution of the same complexity using binary search and graph traversals, sigh.)

Yes, you are right. Well, probably this is a more light-weight implementation.

I haven’t read the solution, but path compression in union find is enough to achieve amortized $$$\log n$$$ complexity per query.

I also got TLE

I am totally stuck and clueless on how should I go next on

Joker. Can anyone please give me a hint? Here is what I found so far :SpoilerBipartite ColoringDisjoint Set Unionof $$$2N$$$ nodes (first $$$N$$$ nodes are one color, last $$$N$$$ are another color of those same nodes) to detect if Odd-cycle appear immediatelywhile adding edges ONE BY ONE.add the entire edges-array to its back.The size of array will become $$$2M$$$.the smallest $$$r$$$ ($$$l \leq r \leq 2M$$$) such that edges in interval $$$[l,r]$$$ form at least one Odd-Cycleismonotonicas $$$l$$$ is increasing.Divide and Conquer Optimizationtrick, but I am struggling to not loop outside of candidate intervals.Bipartite Coloring, but I couldn't find anything useful.I know a solution with $$$O(N*\sqrt{Q}*\alpha(N))$$$ which uses dynamic dsu + mo's algorithm. I don't think it will pass the TL though.

Nitpick. I don't think the $$$α(N)$$$ part is valid. You get it if you add "path compression" to DSU, but (afaik) you can't do that for dynamic DSU. Should be $$$log(N)$$$ instead in this case.

Right, my bad.

If you have link cut tree template, then it can be solved quite easily: Go forward keep only important edges. Then go backward, remove those edges one by one, also maintain a pointer at the end. Try to add edges from the end that won't produce an odd cycle, possible remove some edges that can be removed when going backward.

You were on the right track. This problem can be solved in $$$\mathcal{O}(M \log(M) \log (N))$$$ with Divide and Conquer + DSU with rollbacks. Keeping the intervals as $$$[1, l_i) \cup (r_i, M)$$$ is more convenient, as it avoid the issue where edges that were added on the right and are removed on the left.

solution detailsThe solution uses a global DSU with rollbacks and a recursive function

`rec(a, b, A, B)`

that computes $$$r$$$ for all $$$l \in [a, b)$$$ given that those $$$r$$$ lie in $$$[A, B)$$$. When the function is called, the DSU contains all edges in $$$[1, a) \cup (B, M]$$$. Then you put $$$m = (a+b)/2$$$, add edges on the left to get $$$[1, m) \cup (B, M]$$$ and then add edges on the right to determine $$$r(m)$$$. Roll back to $$$[1, a) \cup (B, M]$$$, add only the left edges to get $$$[1, m+1) \cup (B, M]$$$ to call`rec(m+1, b, r, B)`

. Roll back and add only the right edges to get $$$[1, a) \cup (r, M]$$$ to call`rec(a, m, A, r)`

. Roll back and return. (There's a special case where the edges in $$$[1, l)$$$ form an odd cycle on their own in which you should set $$$r = \infty$$$.)Thank you so much! I am glad that I was on the right track. I will try to complete the hole by my own first(I won't open the solution detail yet), but really thanks a lot!! :D

I solved it! Thank you so much! (I wish I can upvote your comment more than once :D)

What is the problem with the my

python submission87694579, I am sure I solved the test cases 1(the example given), but it gives me 0 point. I think the problem is with theinput and output?I tried to see other

python(both python 3 and pypy 3.6) submission, but there is no one who has got totally accepted.You are querying the same color multiple times, this is not allowed.

I cannot see your submission.

Boi!

Will this contest be available for virtual participation?

Yes, it is now.

When will it be possible to see others submission?

Please make standings or submissions visible today , it helps to get to know which problem to solve first , and standing keeps motivated to not give up.

It was voted by participants to keep the scoreboard hidden during the contest: https://codeforces.com/blog/entry/80321?#comment-665679

Note, though, that a relative comparison of problem difficulties doesn't really apply here (and competitions of similar format) since each problem contains multiple subtasks of varying degrees of difficulty. So in essence, you already know before-hand that focusing on subtasks is going to be easier than tackling the full problems.

This is correct. Please do not forget to make the submissions visible immediately after the contest. Currently they are not visible for day 1 so comments above like "Here is the model solution for this subtask 87704876." are useless.

How to solve day 2 problem A?

Especially, for the case that multiple sulutions exist, how to find the minimal one?

probably ternary search would work

So there should be only one local minimum in the function. Any hints why this is?

$$$|A\cdot x + B|$$$ is convex, and the sum of convex functions is also convex.

In case of multiple answers, we can express the final result as : |0 — x| + |a1 — x| + |a2 — x| + |a3 — x| + ... , where is x is the value assigned to any on node in a connected component. a1, a2 can be obtained by solving equation which result after assigning x to a specific node, then the answer is the median of (0, a1, a2, a3,...)

If you assign value $$$x$$$ to some vertex, then vertices connected to it with a black edge must have value $$$1 - x$$$, and vertices connected to it with a red edge must have value $$$2 - x$$$. This way you get that the value of every vertex in that component must be $$$c_i + s_i x$$$ for some $$$c \in \mathbb{Z}$$$ and $$$s_i \in {-1, 1}$$$.

If there is a cycle, it gives you an equation on $$$x$$$, from which you either get no constraints on $$$x$$$, that no value $$$x$$$ works, or the exact value $$$x$$$ must be.

After calculating the value $$$c_i + s_i x$$$ for every vertex, you set $$$x' = arg\,min_x\ \sum_i abs(c_i + s_i x)$$$ and assign value $$$c_i + s_i x'$$$ to vertex $$$i$$$ in the component. The function we are minimising is a sum of absolute values, so we can compute its minimum with a sweep line. There always exists a solution of form $$$x' = \frac{k}{2}$$$ for some $$$k \in \mathbb{Z}$$$.

Repeat for every connected component.

Code: 87774627

Code is not visible, you should submit it for a random problem and share that link

87795405

I solved problem A today, by this method. First I choose a node to begin, and called it value A. Then in a DFS I updated every node to have an equation like k*A+c. k was always either 1 or -1. When a node had multiple equations, you could solve for A. When there were no restrictions on A, you had to find the best A. I did this by finding the median of the all the k*c.

For every component, choose an arbitrary vertex and let its weight be $$$x$$$. Then all vertices in that component has weight of the form $$$ax+b$$$ for some coefficients $$$a$$$ and $$$b$$$.

Our goal is to minimize

which is well-known that the best $$$x$$$ we should choose is the medium among $$$x_i = -b_i/a_i$$$.

well, my approach was similiar, but I found the optimal $$$x$$$ with ternary search

How do you come up with that $$$\sum_{i} |a_ix+b|$$$ has only one local minimum?

the sum of convex functions is also convex

There are at max 2c+1 possible values of x where c is size of component. You can just loop over them

Problem B: https://codeforces.com/contest/1280/problem/C

Well, not exactly. In the problem you linked we are forced to use pairs (I at least found it non-trivial to prove we'll always want to swap pairs only, except for the last vertex).

Also here you need to reconstruct the solution which is also not exactly trivial (but not very hard either).

B2 is the same as tree and hamiltonian path atcoder

for problem B2 (second subtask) I made this greedy algorithm that seems work but it gave WA: pick the two farthest nodes, move from one to the other and the reverse, erase them from the tree and continue doing that. Stop when there are $$$0$$$ or $$$3$$$ nodes. In case when there are $$$3$$$ nodes, these nodes will form a chain, so move the first to the second, the second to the third and the third to the first.

Any case that breaks it??

It fails in test case 21.

TestAnswer should be 90.

link doesn't work

it gives me 90.

Why does it fail tho?

My first idea was also the same(matching 2 farthest nodes) but later figured this solution is incorrect and found this anti-test(mine was giving 86 instead of 90). Here is an image of my solution's matching the 2 farthest nodes each time. We can match 2-8 and 21-10 to get the answer 90.

Thanks.

https://www.spoj.com/problems/HOLI/

naviiiiiiid

Anyone ideas about C from day 2? I had zero ideas except some very, very ugly DP which would have solved a few subtasks...

We have now published the analysis for Day 2.

Thank you gen. What wonderful contests they were! I really enjoyed it.

I had to.

Let's pretend everyone was protesting in unity against geometry ;)

Well, now that you've started it, I'll share a video I made yesterday as a joke. Hopefully, I won't offend anyone.

On a more serious note, I think that perhaps it wasn't an ideal task for subtask-structure. What I mean by that is I think it was way harder than usual to score points even on the first subtask (it's reasonable if you notice simplification to 2D, but if you keep working in 3D, good luck). Additionally, long testing queue during the first onsite day, made it a bit more difficult as well. Finally, pre-written code may have helped a lot in this task as well, so comparing onsite results to online mirror isn't exactly fair in my opinion either. So, while this is definitely an amusing situation, it was the hardest task in the set in my opinion, and I'm not overly surprised, especially since I feel that a lot of people kept working on other tasks as well instead. Which maybe, given the difficulty to score even some points here, was in most cases absolutely the right decision.

Yeah, after the contest I thought that better subtasks could have saved this problem. Like having just two substances instead of three, as a subtask.

The problem is still solvable in 3D without the use of floating numbers (also without fractions). I believe that the most difficult part was that contestants likely didn't know the trivial operations with 3d vectors (triple product sign and cross product).

I've wished for geometry in BOI/IOI for a while. Maybe I should be more careful of what I wish for.

This diff would've yielded me 43p. Not even geometry, just a stupid bookkeeping error :P And since it uses floats, I got 100p in analysis after a little tweaking.

Not necessarily blaming the queue though, I got this done at the very end.

My code for this problemThe main idea of my solution was to pick an arbitrary vector and split everything else into two parts (by sign of triple product). After that, I maintained two sets with vectors by polar angle. (Again, used triple product sign for custom comparator)

I dont know why I am getting WA on test 38 and beyond(Task A, Day 2)..My solution has the correct complexity. 87801797

The "BO" in "BOI" stands for "Big Oof"

What's B doing in a serious competition? I've seen/solved both parts multiple times, hell I even set a problem that uses the same ideas as B2.

Why did

you"set a problem" that you had already "seen/solved both parts multiple times" of before? Was that for a non-"serious competition"?Jokes aside, all problems at BOI go through a review process involving multiple people, both from the official jury and the representatives of all delegations, taking into account aspects like difficulty, originality, amount/quality of meaningful subtasks, as well as all that in the context of the other problems. The problem in question may not be the most original one (heck, truly original problems are so rare tbh) but it was decided to (and ultimately turned out to) serve its purpose well.

It was for Topcoder SRM, yes.

That's pretty bad if there were no better problems than repost of a repost of a repost. I mean we used tree diameter with dynamic edge lengths last year in CEOI, but that was because I couldn't find it solved

anywheredespite a lot of effort even though it's a standard HLD.The problem was not well-known among the BOI contestants. Only five contestants could solve it (http://www.boi2020.lv/results.html).

You realise that for schoolkids, not even something completely standard like finding SCC would be well-known? You're in effect making an argument for total copypasting.

SCC would be well-known to many BOI participants. Many of the participants know basic competitive programming topics, but they don't know all "standard" problems in the world.

By the way, I don't think B is a standard problem, I haven't seen it anywhere before. (Yes I know you can surely show some contest where it has appeared.)

A good way to select problems for a contest is to choose problems that are interesting to the real participants of the contest, instead of an imaginary audience that knows all the problems.

SCC isn't that basic. How many people would be able to write it correctly? It's quite tricky to get right unless you have enough experience. Well-known as in "I know what it is", sure. Well-known as in "I just write the solution automatically and it works"? I'm pressing X for doubt.

Like I said, an argument for copypasting.

I have no real data but I would assume at least 25% of BOI participants could implement SCC correctly during the contest.

And I'd assume at least 25% would implement mixture correctly at least for a non-zero score, but lookatit.

Really? I think for any geometry task 0% is the best estimate :)

By the way, in BOI 2014 one of the tasks was to find Eulerian paths and 16/58 (about 28%) contestants solved it (http://www.boi2014.lmio.lt/results.html, task Postmen). I think this is about as difficult as SCC (maybe a bit more difficult).

When will be the test data open?

+1

Thanks! https://oj.uz/problems/source/506

It's available now.

Keep in mind that there may be some differences between onsite and Codeforces tasks (e.g. colors became multi-test-case-per-input problem).

yeah