gen's blog

By gen, 5 months ago, In English

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!

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Looking forward to great problems :)

»
5 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Thank you MikeMirzayanov!

»
5 months ago, # |
  Vote: I like it +63 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Link to participate ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Even solve counts should be hidden in the dashboard ideally.

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

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

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it +38 Vote: I do not like it

        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. :)

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +60 Vote: I do not like it

          For public.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +139 Vote: I do not like it

          For hidden.

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

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

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

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

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

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

      Can i look at the boi 2020 Ventspils current leaderboard?

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        AFAIK no.

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

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

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I was just asking out of curiosity

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            Rev. 2   Vote: I like it +31 Vote: I do not like it

            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.

»
5 months ago, # |
  Vote: I like it +44 Vote: I do not like it

hope to be more oi contest in codeforces

»
4 months ago, # |
  Vote: I like it +99 Vote: I do not like it

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, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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, # ^ |
        Vote: I like it +45 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -36 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +60 Vote: I do not like it

    GPU is irrelevant here.

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

      why do you say that ?

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

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

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -90 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -78 Vote: I do not like it

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, # ^ |
      Vote: I like it +25 Vote: I do not like it

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

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

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

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

how to solve A ?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -106 Vote: I do not like it

    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:

    1. if the result is "1", you set the upper_bound to P and recur.

    2. 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_bound

    NOT SURE about it

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

      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, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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, # |
  Vote: I like it +24 Vote: I do not like it

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

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

    Also is B just checking that the triangle contains the origin?

    roughly speaking, that's exactly that.

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

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

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

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it -59 Vote: I do not like it

    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:

    1. if the result is "1", you set the upper_bound to P and recur.

    2. 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_bound

    NOT SURE about it

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

      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, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

Will there be upsolving?

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

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

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

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

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It doesn't pass in c++ too.

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

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

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

      Is link cut tree intended? :o

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

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

            Here is the model solution for this subtask 87704876.

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

              I am not allowed to view the requested page.

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

                  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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

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

                  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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also got TLE

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

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
  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +21 Vote: I do not like it

    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 details
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You are querying the same color multiple times, this is not allowed.

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

    I cannot see your submission.

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

Boi!

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

Will this contest be available for virtual participation?

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

When will it be possible to see others submission?

»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

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, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

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

      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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve day 2 problem A?

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

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

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

      probably ternary search would work

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

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

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

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

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

      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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

          the sum of convex functions is also convex

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

      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, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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, # |
  Vote: I like it +17 Vote: I do not like it

B2 is the same as tree and hamiltonian path atcoder

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

    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   Vote: I like it 0 Vote: I do not like it
      Test

      Answer should be 90.

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

        link doesn't work

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

        it gives me 90.

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

        Why does it fail tho?

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

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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, # |
  Vote: I like it +15 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +110 Vote: I do not like it

I had to.

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

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

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

    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   Vote: I like it +8 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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   Vote: I like it +33 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My code for this problem

      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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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, # ^ |
                Vote: I like it -13 Vote: I do not like it

              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, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

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

                  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, # |
  Vote: I like it 0 Vote: I do not like it

When will be the test data open?