### gen's blog

By gen, 4 months ago,

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!

• +514

 » 4 months ago, # |   0 Wow!!! I was looking for a way to participate from country that's not mentioned above and thanks to MikeMirzayanov
 » 4 months ago, # |   +2 Looking forward to great problems :)
 » 4 months ago, # |   -20 Thank you MikeMirzayanov!
 » 4 months ago, # |   +63 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.
 » 4 months ago, # |   0 Whats the expected difficulty ? More inclined towards Div1 I guess ?
•  » » 4 months ago, # ^ |   +64 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.
 » 4 months ago, # |   -22 Link to participate ?
•  » » 4 months ago, # ^ |   -10 It is in the 'contests' menu, here. It starts in three days, so you don't need to worry now.
 » 4 months ago, # |   +26 The standing should be hidden in the contest time following rules of IOI standard contest.
•  » » 4 months ago, # ^ |   +21 Even solve counts should be hidden in the dashboard ideally.
•  » » » 4 months ago, # ^ |   +11 We are considering keeping the scoreboard hidden during the contest. I will post an update later.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +38 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. :)
•  » » » » » 4 months ago, # ^ |   +60 For public.
•  » » » » » 4 months ago, # ^ |   +139 For hidden.
•  » » » » » 4 months ago, # ^ |   +32 Update: based on the public opinion, we are making the scoreboard hidden.
•  » » » » » » 4 months ago, # ^ |   +102 Update: based on the hidden opinion, we are making the scoreboard public.
•  » » 4 months ago, # ^ |   +37 I've never seen that done for a mirror contest though.
•  » » » 4 months ago, # ^ |   -8 Can i look at the boi 2020 Ventspils current leaderboard?
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 AFAIK no.
•  » » » » » 4 months ago, # ^ |   +8 Indeed, we will not publish the scoreboard publicly until the corresponding mirror contest has finished.
 » 4 months ago, # |   +3 'the students will compete in a proctored setting online' Can you share more details of this?
•  » » 4 months ago, # ^ |   +5 Hi, it is requirement only for the official participants, if you participate in the mirror, you don't have to worry about it.
•  » » » 4 months ago, # ^ |   +5 I was just asking out of curiosity
•  » » » » 4 months ago, # ^ |   +10 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.
•  » » » » » 4 months ago, # ^ |   0 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?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +31 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.
•  » » » » » » » 4 months ago, # ^ |   +1 Thank you for your time
 » 4 months ago, # |   +44 hope to be more oi contest in codeforces
•  » » 4 months ago, # ^ | ← Rev. 2 →   -43 We hope so.
 » 4 months ago, # |   +99 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
•  » » 4 months ago, # ^ |   +13 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.
•  » » » 4 months ago, # ^ |   +45 On CF, the submission with the highest score counts, an we use the same for BOI.
 » 4 months ago, # |   -36 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?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Copied this from somewhere: Now we can speed up compilation time by precompiling all the header files as mentioned here, i.e. by precompiling the bits/stdc++.h header file. This can speed up compilation time by up to a factor of 12. For this, first, navigate to the stdc++.h file. This will be located at a directory similar to C:\MinGW\lib\gcc\mingw32\6.3.0\include\c++\mingw32\bits. Right click while pressing Shift to open a Powershell/cmd window there. Run the command g++ -std=c++17 stdc++.h, to compile the header. Take care to use the same flags you used in your build system. Check to make sure that the stdc++.h.gch file was created in the directory. Link: sauce
•  » » 4 months ago, # ^ |   +60 GPU is irrelevant here.
•  » » » 4 months ago, # ^ |   -10 why do you say that ?
•  » » » » 4 months ago, # ^ |   +3 You're not doing anything with graphics or massive matrix multiplications.
•  » » 4 months ago, # ^ | ← Rev. 2 →   -9 One of my friend had the same problem. Make sure there's no antivirus blocking the program's execution.
 » 4 months ago, # |   -90 Why is this contest unrated? Let people have some fun, no need to make it unrated
 » 4 months ago, # |   -78 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++).
•  » » 4 months ago, # ^ |   +25 Please don't discuss the problem until the end of the contest.
•  » » » 4 months ago, # ^ |   0 I'm sorry, I didn't think it was important since it's unrated and there are no standings.
 » 4 months ago, # |   +18 how to solve A ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   -106 Problem A : I tried it binary search, I guess the idea is correct, but the implementation was hard.We are sure that C is between 1 and N, inclusive so let the lower_bound = 0 and upper_bound = N **** You need to ask the middle value of lower_bound (0) and upper_bound (N) P = (0 + N)//2 there are 2 possibility: if the result is "1", you set the upper_bound to P and recur. if result is "0" ,you set the lower_bound to P and recur. so finally the upper_bound and lower_bound will be the same, which is the base case, the C = lower_bound = upper_boundNOT SURE about it
•  » » » 4 months ago, # ^ |   0 I tried that using binary search concept and after extensive testing , i found that my program was asking queries where p>n . Hence , got WA . If there was no constraint where 1<=p<=n . Then i must had got full marks in it (O(logn) sol) . Although managed to get 9 pts using brute .
•  » » » » 4 months ago, # ^ |   0 Yes, I also doesn't notice the restriction 1<=p<=n
•  » » 4 months ago, # ^ |   +9 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!
•  » » » 4 months ago, # ^ |   +3 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.
•  » » » » 4 months ago, # ^ |   +8 For n= 32, here is a picture
 » 4 months ago, # |   +24 How to solve A,C? Also is B just checking that the triangle contains the origin?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Also is B just checking that the triangle contains the origin? roughly speaking, that's exactly that.
•  » » 4 months ago, # ^ |   0 I did what you say in B but it fails first subtask. Did you pass it with that idea?
•  » » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 Swap coordinates to make A != 0, that fixed my fail on the first subtask.
•  » » 4 months ago, # ^ | ← Rev. 4 →   -59 Problem A : I tried it binary search, I guess the idea is correct, but the implementation was hard.We are sure that C is between 1 and N, inclusive so let the lower_bound = 0 and upper_bound = NYou need to ask the middle value of lower_bound (0) and upper_bound (N) P = (0 + N)//2 there are 2 possibility: if the result is "1", you set the upper_bound to P and recur. if result is "0" ,you set the lower_bound to P and recur. so finally the upper_bound and lower_bound will be the same, which is the base case, the C = lower_bound = upper_boundNOT SURE about it
•  » » » 4 months ago, # ^ |   -22 Why 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.
•  » » » » 4 months ago, # ^ |   +10 You're oversimplifying the problem by a LOT, what you wrote isn't a solution. That's the main reason.
•  » » » » » 4 months ago, # ^ |   -29 Ok sorry, I thought I was correct
 » 4 months ago, # |   +18 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?
•  » » 4 months ago, # ^ |   +8 This happened to me on A. I guess test cases are weak.
•  » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   0 Will there be upsolving?
 » 4 months ago, # |   +8 Excellent contest. I enjoyed it a lot, although I couldn't AC any problem. When editorial will be published?
 » 4 months ago, # |   +16 It would be helpful if anyone shares there approaches for the problems.
 » 4 months ago, # |   0 did anyone solve subtask 3 of the third problem with binary search?
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 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.
•  » » » » 4 months ago, # ^ |   +8 Look here
•  » » » 4 months ago, # ^ |   0 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?
•  » » 4 months ago, # ^ |   0 I tried to, but it was too slow (was using java tho).
 » 4 months ago, # |   +8 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).
•  » » 4 months ago, # ^ |   0 It doesn't pass in c++ too.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 The time limits were quite tight to distinguish between Mo's algorithm and the faster solution.
•  » » » 4 months ago, # ^ |   +8 Is link cut tree intended? :o
•  » » » » 4 months ago, # ^ |   0 Was not. :D
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 4 months ago, # ^ |   0 It was intended... Probably your solution can be optimized.
•  » » » » » 4 months ago, # ^ |   0 Can you share one solution with that complexity that passes 4th subtask?
•  » » » » » » 4 months ago, # ^ |   0 Here is the model solution for this subtask 87704876.
•  » » » » » » » 4 months ago, # ^ |   +6 I am not allowed to view the requested page.
•  » » » » » » » » 4 months ago, # ^ |   0
•  » » » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 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.)
•  » » » » » » » » » 4 months ago, # ^ |   0 Yes, you are right. Well, probably this is a more light-weight implementation.
•  » » » » » » » » » 4 months ago, # ^ |   0 I haven’t read the solution, but path compression in union find is enough to achieve amortized $\log n$ complexity per query.
•  » » » » 4 months ago, # ^ |   0 I also got TLE
 » 4 months ago, # |   +8 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 : Spoiler "Detecting odd-cycle", these words trigger one idea : Bipartite Coloring I can use Disjoint Set Union of $2N$ nodes (first $N$ nodes are one color, last $N$ are another color of those same nodes) to detect if Odd-cycle appear immediately while adding edges ONE BY ONE. We can actually modify the query from "check if edges with number in $[1,l_i)\cup(r_i,M]$ form at least one odd-cycle" to "check if edges with number in $(r_i,l_i+M)$ form at least one odd-cycle" by add the entire edges-array to its back. The size of array will become $2M$. For each $l$ ($1 \leq l \leq M$), the smallest $r$ ($l \leq r \leq 2M$) such that edges in interval $[l,r]$ form at least one Odd-Cycle is monotonic as $l$ is increasing. I think of Divide and Conquer Optimization trick, but I am struggling to not loop outside of candidate intervals. I also try to think anything outside Bipartite Coloring, but I couldn't find anything useful.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » 4 months ago, # ^ |   +24 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.
•  » » » » 4 months ago, # ^ |   +8 Right, my bad.
•  » » 4 months ago, # ^ |   0 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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +21 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$.)
•  » » » 4 months ago, # ^ |   0 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
•  » » » 4 months ago, # ^ |   0 I solved it! Thank you so much! (I wish I can upvote your comment more than once :D)
 » 4 months ago, # | ← Rev. 2 →   -11 What is the problem with the my python submission 87694579, I am sure I solved the test cases 1(the example given), but it gives me 0 point. I think the problem is with the input 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.
•  » » 4 months ago, # ^ |   +10 You are querying the same color multiple times, this is not allowed.
•  » » 4 months ago, # ^ |   0 I cannot see your submission.
 » 4 months ago, # |   0 Boi!
 » 4 months ago, # |   0 Will this contest be available for virtual participation?
•  » » 4 months ago, # ^ |   +5 Yes, it is now.
 » 4 months ago, # |   +32 When will it be possible to see others submission?
 » 4 months ago, # |   -29 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.
•  » » 4 months ago, # ^ |   +25 It was voted by participants to keep the scoreboard hidden during the contest: https://codeforces.com/blog/entry/80321?#comment-665679Note, 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.
•  » » » 4 months ago, # ^ |   +8 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.
 » 4 months ago, # |   0 How to solve day 2 problem A?
•  » » 4 months ago, # ^ |   0 Especially, for the case that multiple sulutions exist, how to find the minimal one?
•  » » » 4 months ago, # ^ |   0 probably ternary search would work
•  » » » » 4 months ago, # ^ |   0 So there should be only one local minimum in the function. Any hints why this is?
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   +11 $|A\cdot x + B|$ is convex, and the sum of convex functions is also convex.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +8 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,...)
•  » » » 4 months ago, # ^ |   +5 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
•  » » » » 4 months ago, # ^ |   0 Code is not visible, you should submit it for a random problem and share that link
•  » » » » » 4 months ago, # ^ |   0
•  » » 4 months ago, # ^ |   +11 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.
•  » » 4 months ago, # ^ |   +17 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 $\sum_{i} |a_ix+b|,$which is well-known that the best $x$ we should choose is the medium among $x_i = -b_i/a_i$.
•  » » » 4 months ago, # ^ |   0 well, my approach was similiar, but I found the optimal $x$ with ternary search
•  » » » » 4 months ago, # ^ |   0 How do you come up with that $\sum_{i} |a_ix+b|$ has only one local minimum?
•  » » » » » 4 months ago, # ^ |   +8 the sum of convex functions is also convex
•  » » » 4 months ago, # ^ |   -10 There are at max 2c+1 possible values of x where c is size of component. You can just loop over them
 » 4 months ago, # |   +5
•  » » 4 months ago, # ^ |   +6 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).
 » 4 months ago, # |   +17 B2 is the same as tree and hamiltonian path atcoder
•  » » 4 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Test22 1 2 1 3 3 4 4 5 4 6 3 7 4 8 5 9 9 10 8 11 11 12 5 13 8 14 8 15 5 16 8 17 11 18 15 19 11 20 8 21 15 22 Answer should be 90.
•  » » » » 4 months ago, # ^ |   0 link doesn't work
•  » » » » 4 months ago, # ^ |   0 it gives me 90.
•  » » » » 4 months ago, # ^ |   0 Why does it fail tho?
•  » » » » » 4 months ago, # ^ |   0 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.
•  » » » » » » 4 months ago, # ^ |   0 Thanks.
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   +3 naviiiiiiid
 » 4 months ago, # |   +6 Anyone ideas about C from day 2? I had zero ideas except some very, very ugly DP which would have solved a few subtasks...
•  » » 4 months ago, # ^ |   +22 We have now published the analysis for Day 2.
 » 4 months ago, # |   +15 Thank you gen. What wonderful contests they were! I really enjoyed it.
 » 4 months ago, # |   +110 I had to.
•  » » 4 months ago, # ^ |   +40 Let's pretend everyone was protesting in unity against geometry ;)
•  » » 4 months ago, # ^ |   +59 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 4 months ago, # ^ |   +21 I've wished for geometry in BOI/IOI for a while. Maybe I should be more careful of what I wish for.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +33 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.
•  » » » 4 months ago, # ^ |   0 My code for this problem/*input 1 2 3 6 A 0 0 1 A 1 0 0 A 0 1 0 A 1 1 1 R 1 R 2 */ #pragma GCC optimize ("O3") #include #include using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_map = tree, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); struct viktor { ll x, y, z; viktor() { x = 0; y = 0; z = 0; } viktor(ll x, ll y, ll z): x(x), y(y), z(z) { } int sgn() { if (x == 0 && y == 0 && z == 0) return 0; if (x < 0 || (x == 0 && (y < 0 || (y == 0 && z < 0)))) return -1; return 1; } void normalize() { ll g = 0; if (x != 0) g = __gcd(g, abs(x)); if (y != 0) g = __gcd(g, abs(y)); if (z != 0) g = __gcd(g, abs(z)); assert(g != 0); x /= g; y /= g; z /= g; if (x < 0 || (x == 0 && (y < 0 || (y == 0 && z < 0)))) { x *= -1; y *= -1; z *= -1; } } bool operator==(const viktor &o) { return (x == o.x && y == o.y && z == o.z); } bool operator<(const viktor &o)const { if (x != o.x) return x < o.x; if (y != o.y) return y < o.y; return z < o.z; } }; viktor cross(viktor a, viktor b) { viktor c; c.x = a.y * b.z - a.z * b.y; c.y = a.z * b.x - a.x * b.z; c.z = a.x * b.y - a.y * b.x; c.normalize(); return c; } ll V(viktor a, viktor b, viktor c) { ll s = c.x * (a.y * b.z - a.z * b.y) + c.y * (a.z * b.x - a.x * b.z) + c.z * (a.x * b.y - a.y * b.x); if (s < 0) return -1; if (s == 0) return 0; return 1; } int S(viktor a, viktor b) { viktor c; c.x = a.y * b.z - a.z * b.y; c.y = a.z * b.x - a.x * b.z; c.z = a.x * b.y - a.y * b.x; return c.sgn(); } viktor v; struct oper { bool operator()(const viktor &x, const viktor &y)const { int s = V(x, y, v); if (s == 0) return x < y; else return s > 0; } }; viktor a; int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> v.x >> v.y >> v.z; v.normalize(); ll n; cin >> n; viktor A[n + 1]; int id = 0; int kiekv = 0; int kiek2 = 0; map>M2; bool turiu = false; multisetPL, MI, NU; while (n--) { { char c; cin >> c; if (c == 'A') { id++; viktor w; cin >> w.x >> w.y >> w.z; w.normalize(); A[id] = w; if (v == w) kiekv++; else { if (!turiu) { a = w; turiu = true; } viktor vw = cross(v, w); if (M2.count(vw) == 0) M2[vw] = {0, 0}; if (M2[vw].first > 0 && M2[vw].second > 0) kiek2--; if (S(v, w) > 0) M2[vw].first++; else M2[vw].second++; if (M2[vw].first > 0 && M2[vw].second > 0) kiek2++; int s = V(a, v, w); if (s == 0) NU.insert(w); else if (s == 1) PL.insert(w); else MI.insert(w); } } else { int r; cin >> r; if (A[r] == v) kiekv--; else { viktor vw = cross(v, A[r]); if (M2[vw].first > 0 && M2[vw].second > 0) kiek2--; if (S(v, A[r]) > 0) M2[vw].first--; else M2[vw].second--; if (M2[vw].first > 0 && M2[vw].second > 0) kiek2++; int s = V(a, v, A[r]); if (s == 0) NU.erase(NU.find(A[r])); else if (s == 1) PL.erase(PL.find(A[r])); else MI.erase(MI.find(A[r])); } } } if (kiekv > 0) { cout << "1\n"; } else if (kiek2 > 0) { cout << "2\n"; } else { vectorX; if (!MI.empty()) { X.push_back(*MI.begin()); X.push_back(*(--MI.end())); } if (!NU.empty()) { X.push_back(*NU.begin()); X.push_back(*(--NU.end())); } if (!PL.empty()) { X.push_back(*PL.begin()); X.push_back(*(--PL.end())); } bool ok = false; for (int i = 0; i < X.size(); i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++) { ll s1 = V(X[j], X[k], v); ll s2 = V(X[k], X[i], v); ll s3 = V(X[i], X[j], v); if (s1 == s2 && s2 == s3 && s1 != 0) { ok = true; break; } } if (ok) break; } if (ok) break; } if (ok) cout << "3\n"; else cout << "0\n"; } } return 0; } The 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)
 » 4 months ago, # |   0 I dont know why I am getting WA on test 38 and beyond(Task A, Day 2)..My solution has the correct complexity. 87801797
 » 4 months ago, # |   +3 The "BO" in "BOI" stands for "Big Oof"
 » 4 months ago, # |   +41 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.
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 Was that for a non-"serious competition"? It was for Topcoder SRM, yes. it was decided to (and ultimately turned out to) serve its purpose well. 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 anywhere despite a lot of effort even though it's a standard HLD.
•  » » » » 4 months ago, # ^ |   0 The problem was not well-known among the BOI contestants. Only five contestants could solve it (http://www.boi2020.lv/results.html).
•  » » » » » 4 months ago, # ^ |   0 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.
•  » » » » » » 4 months ago, # ^ |   +3 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.
•  » » » » » » » 4 months ago, # ^ |   -13 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. 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. Like I said, an argument for copypasting.
•  » » » » » » » » 4 months ago, # ^ |   +3 I have no real data but I would assume at least 25% of BOI participants could implement SCC correctly during the contest.
•  » » » » » » » » » 4 months ago, # ^ |   0 And I'd assume at least 25% would implement mixture correctly at least for a non-zero score, but lookatit.
•  » » » » » » » » » 4 months ago, # ^ |   0 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).
 » 4 months ago, # |   0 When will be the test data open?
•  » » 4 months ago, # ^ |   +29 +1
•  » » » 4 months ago, # ^ |   0
•  » » 4 months ago, # ^ |   +10 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).