Блог пользователя gen

Автор gen, 4 месяца назад, перевод, По-русски

Привет всем!

Я рад пригласить всех к участию в онлайн зеркале Балтийской олимпиады по информатике в 22.07.2020 14:05 (Московское время) и 23.07.2020 14:05 (Московское время) на Codeforces!

Балтийская олимпиада по информатике 2020 (BOI 2020) – индивидуальное соревнование для учеников средней школы из одиннадцати стран (в алфавитном порядке): Германия, Дания, Исландия, Латвия, Литва, Норвегия, Польша, Украина, Финляндия, Швеция и Эстония. Более 60 участников борются между собой, решая сложные алгоритмические задачи. Каждая страна представлена 6 лучшими участниками по итогам национальных олимпиад. Официальную страницу олимпиады можно посмотреть на boi2020.lv.

Контест состоит из двух дней, каждый день участникам дано 5 часов на решение 3 задач различной сложности. За каждую задачу можно получить до 100 баллов, которые распределены по нескольким подзадачам с различными ограничениями, что позволяет участникам получить частичные баллы. Оценивание происходит по формату IOI, где участник получает полный отчёт по тестированию по всем тестам во время соревнования.

В этом году олимпиада должна была состояться в Латвии в Вентспилсе, однако не проводится на месте из-за пандемии, поэтому ученики будут участвовать онлайн, под присмотром участников жюри из каждой страны. Благодаря помощи MikeMirzayanov, мы рады провести онлайн зеркало на Codeforces для всех желающих.

Обратите внимание, что соревнование не рейтинговое. Зеркало начинается на 1 день, 1 час и 5 минут позже официального контеста.

Желаем интересного контеста! :)

-- BOI 2020 committee

Мартиньш Опманис, Рихардc Опманис, Сергей Мельник, andreyv, pakalns, gen, eduardische, Alex_2oo8, nvilcins, KarlisS.

UPD1: Таблица результатов не будет публичной, каждый участник сможет видеть только результаты своих посылок.

UPD2: Разбор задач 1-ого дня опубликован.

UPD3: Разбор задач 2-ого дня опубликован.

UPD4: Поздравляем победителей с полным результатом 600 баллов WZYYN, isaf27, Arpa!

 
 
 
 
  • Проголосовать: нравится
  • +514
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Looking forward to great problems :)

»
4 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Thank you MikeMirzayanov!

»
4 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Link to participate ?

»
4 месяца назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    Even solve counts should be hidden in the dashboard ideally.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        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 месяца назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I was just asking out of curiosity

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится +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 месяца назад, # ^ |
            Проголосовать: нравится 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 месяца назад, # ^ |
            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 месяца назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

hope to be more oi contest in codeforces

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

а условия будут доступны на русском языке?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, условия в зеркале будут на английском и русском!

»
4 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
        Проголосовать: нравится +45 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится -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 месяца назад, # ^ |
    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 месяца назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    GPU is irrelevant here.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится -90 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится -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 месяца назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

how to solve A ?

  • »
    »
    4 месяца назад, # ^ |
    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:

    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 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
        Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    roughly speaking, that's exactly that.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    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 = 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 месяца назад, # ^ |
        Проголосовать: нравится -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 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be upsolving?

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 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 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится +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
  • »
    »
    4 месяца назад, # ^ |
    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 месяца назад, # ^ |
        Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится 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 месяца назад, # ^ |
    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 details
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Boi!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will this contest be available for virtual participation?

»
4 месяца назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

When will it be possible to see others submission?

»
4 месяца назад, # |
  Проголосовать: нравится -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 месяца назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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 месяца назад, # ^ |
        Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve day 2 problem A?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      probably ternary search would work

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
          Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
      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 месяца назад, # ^ |
        Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

B2 is the same as tree and hamiltonian path atcoder

  • »
    »
    4 месяца назад, # ^ |
    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 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Test

      Answer should be 90.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        link doesn't work

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        it gives me 90.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Why does it fail tho?

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +110 Проголосовать: не нравится

I had to.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +40 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +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 месяца назад, # ^ |
      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 месяца назад, # ^ |
      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 месяца назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    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 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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 месяца назад, # |
  Проголосовать: нравится 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 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +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 месяца назад, # ^ |
      Проголосовать: нравится 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 месяца назад, # ^ |
        Проголосовать: нравится 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 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The problem was not well-known among the BOI contestants. Only five contestants could solve it (http://www.boi2020.lv/results.html).

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 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 месяца назад, # ^ |
              Проголосовать: нравится +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 месяца назад, # ^ |
                Проголосовать: нравится -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 месяца назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 месяца назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 месяца назад, # ^ |
                    Проголосовать: нравится 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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will be the test data open?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

gen Евгений ,а вы можете открыть тесты и решения других пользователей ? В Day 2 ,все открывается .