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

Автор MofK, 4 года назад, По-английски

Hello Codeforces!

I am glad to invite you to Codeforces Round #601, which will take place on 19.11.2019 17:35 (Московское время). The round will be rated for both divisions.

All problems in this round were created and prepared by a team of all-Vietnamese setters: MofK, I_love_tigersugar, UncleGrandpa, ngkan. This is the first Vietnamese Div1 round. We tried to make both the problems and the statements interesting and hope that you will enjoy them!

There is an interactive problem in the round. You can read the guide for interactive problem here.

We would like to give a lot of thanks to:

We wish you an exciting round!

UPD: The message from MikeMirzayanov. If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295 Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest. Mike.

UPD: There will be five problems for Division 1 and six problems for Division 2. The score distribution is as follows:

Division 1: 750 — (500 + 750) — 1500 — 1750 — 2500

Division 2: 500 — 1000 — 1500 — 1750 — (1000 + 1250) — 2750

UPD2: : Thanks for participating! Congratulations to the winners!!!

Div. 1: Top 5 are also the only 5 contestant managed to solve all problems!

  1. Radewoosh

  2. maroonrk

  3. SkyDec

  4. webmaster

  5. ecnerwala

Honorable mention: taeyeon_ss for solving problem E in just 31mins!

Div. 2:

  1. MbahSA1937 (solved all problems!)

  2. mintwhale (solved all problems!)

  3. Nightmare05

  4. Don_Quijote

  5. mangojunior

UPD3:Editorial is out!

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

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

from VNOI with love =))

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

From VN with orz!

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

Is it supposed to last 2:15 opposed to the standard two-hour competition?

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

Interactive problems are always fun and challenging.

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

Wish everyone the best of luck and get a good rating after the contest!!

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

    .

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

      Don't worry. Sometimes when we feel that we are not good, then we need to try a lot harder. For example, you should try to do harder problems such at Div 2 D E F, and aim that in a contest you need to finish A B C D E in 2 hours ( maybe F if you're able to ). Just don't giveup halfway through.

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

    Wish so :)

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

Why will contest be held on Tuesday ? There is a Vietnam football match on this day.

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

From VN with love

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

Vietnam national team will play football at 20:00 :(( oh no

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

    Trust me, by that time Vietnam would have the game in their bag anyway, so please join our contest! :)

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

      Not yet calculated the case of rejected goals?

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

        So many downvotes lol.
        Just how butthurt people were seeing your comment, or those ignorant dudes not getting the context and still trying to be superior.

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

    I feel you, I can't stop supporting my national team. So I will write the contest later. =)))

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

Good luck everyone, from Vietnam with love <3

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

There will be Hanoi Tower problems?

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

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

But I always wondered, what if someone pass the 9999 rating in the future?

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

Good luck everyone, from Peru with love <3

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

I should be aware of I_love_tigersugar's tricks

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

highly expecting Prof.PVH throwing some maniac traps into the statements like how he's done those National/Regional problems

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

Hope to see both tourist and Benq participate in this round.

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

Have a nice round!

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

Hoping to see tourist become the highest rated coder on cf again

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

The only question about the contest

Will the No. 1 spot in the rating change ?

tourist or Benq or Anyone else

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

For some reason I am not able to register for the contest :/ There is no register link displayed anywhere.

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

Why close the Registration when the competition begins? I forget to register before the competition.

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

I have no electricity right now and i have made submissions. Can you please make the round unrated for me because i am writing now from my phone with 4G. It is completly dark in my house and the only thing i can do is participate from my phone in a div1 contests which is absurd. Please understand my problem and help me.

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

    I just submited from my phone and got accepted xdddd. Still can you please make it unrated for me. I dont know how to prove to you that i dont have any electricity now.

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

help in B DIV2

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

This round should be unrated. Sample and constraints should not be modified in-between contests. This creates an overall negative experience.

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

    Sorry, we are all not perfect. This time I suggested such a change for the problem and it leads to a much more harder problem. This problem is really minor, all participants solved (thinking that they are solved) harder version actually solved the simplified version. I'll give a chance to exclude yourself from the rating if it really affects you. But 99% (or more) of users weren't really affected.

    Actually, I saw what diligence and efforts were put by both the writers and the coordinator. They really tried to do their best. All the other problems are great.

    Sorry again for the issue. I feel it mostly my mistake (I didn't ask writers to stress it with naive solution).

    I hope you liked the problems!

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

      No, I hate the problems

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

      Thanks, Mike for proactively addressing the issue.

      I was impacted as I was trying to solve a different problem all this time (as you can look from my submission history). I would want to be excluded from the rating.

      Codeforces is the best platform out there and a minor glitch here and there does not change the fact regarding how much effort goes into every round all thanks to admins, setters, testers and co-ordinators in maintaining the continuous high quality of every contest. Thank you for herding all the cats to keep things in order.

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

      If the issue heavily affected you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295

      Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest.

      Thank you.

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

        "Hardly" means "not much", heavily/strongly seems to be what you mean.

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

          I think, a more appropriate word here would be "significantly".

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

            There are a lot of near-synonymous options.

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

              "Near" is the key. :)

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

                Um, no? Any near-synonymous words work well enough if you're not dealing with formal writing and even more will convey the point, although awkwardly. The thing here is that "hardly" has the opposite meaning.

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

                programmers have their own English. It is as simple as possible

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

        Sorry , but how can i get unrated if my electricity was cut out a minute 47 of the contest and then i submitted for fun from my phone problem A an it passed. I had no way of participating for more than half a contests , i know that i can't prove it but may be somehow you can check where from my last submission was made, please help.

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

        I am really disappointed of that. I solved the problem 2 min after the change. I lost a lot of time , 3 wrong submissions and maybe I could solve E1 Div2 I just needed more time to do that. I don't know what you gonna do but I really think I was affected to much by this. Thanks anyway the problems were amazing and I learnt new things.

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

        The only issue for each and everyone who actually solved B initially was that we spent close to 45 mins more or less which reduces to less than 5 mins of time spent after the constraints changed, time that one could have utilized to solve C which was not a mighty hard problem.

        It's okay if you want to keep this rated but it makes user experience pretty weird.

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

        Basically, if:

        1. you participated in the contest &&
        2. you spotted the tricky case &&
        3. you spent too much contest time thinking of how to solve/work around it (and/or tried to hack others based on it)

        then appeal, otherwise, move along :)

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

      What was the problem with $$$m>n$$$?

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

      Tell before the contest that you are not perfect and no one will ever participate

      iMAGE ;

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

      MikeMirzayanov Sir can you please tell us what was the problem with the problem that it required modification of constraint .
      Was it to make the problem easy or the tester code was designed for m <= n ?

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

      MikeMirzayanov

      May you explain what do you mean "by all participants solved (thinking that they are solved) harder version actually solved the simplified version"? Was the problem with the checker? The solution is the same but only with adding edge between the 2 lightest fridges m-n times (which is a very easy addition that I doubt being the reason for the change in constraints).

      EDIT: Have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now.

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

      make it unrated for Benq, he was strongly affected

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

      Why my submissions are skipped? :/ It was hard to me to get that position :c

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

кто-нибудь может объяснить условие B? надеюсь просто я невнимателен. И что всё-таки значит "сообща"??

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

Anyone else thought in Div2D/Div1A that the rice cells assigned to every chicken form a connected area? I was going nuts trying to solve that, would be a really nice problem though.

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

Div2 D and E1 should not have been together because they don't require much concepts and their implementation took a lot of time.

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

How to solve div. 1 C Point ordering ?

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

    Find the next point to first using second type of queries (n-2 queries used).

    Now we have 2 adjacent points. Now find areas of all the others with these 2.(n-2 queries).

    Now the take highest area point (lets say h). Now using 1,h,i we can decide side of i to h. And with information of area we can sort points in each side.

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

Div. 2 Was just a coding contest, sorry but not the best contest :)

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

How to solve Div1 C?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    1. we save the relevant number (1 to n)
      ex) (1,2,3) -> 1 save 2,3 and 2 save 1,3 and 3 save 1,2
      i used set supervising the array
    1. for (1 to n) we find the number that has two sizes of set
      then, that number is what we start to solve the problem
    1. then, keep track of that number
      also erase the already using number from the other set
      the size of set of that number is three , then that is not proper number to keep going

    sorry, i am not good at english.. so i can't write any more

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

    First of all, lock the first and second point. We'll consider other points to be on either side based on those two points.

    We can see that the query $$$(2, 1, i, j)$$$ can tell that in a permutation starting from $$$1$$$, which point will come first: if the response is $$$1$$$, $$$i$$$ comes before $$$j$$$, and the other way around if the response being $$$-1$$$.

    Loop through point from $$$3$$$ to $$$n$$$ to find out if each of them comes before or after $$$2$$$ in the permutation, using the query $$$(2, 1, 2, k)$$$. Here we can see that the points have been separated into two halves.

    For each half, we can see that, following the permutation's order (i.e. the points' counter-clockwise order), the area of the triangle with point $$$1$$$, point $$$2$$$ and point $$$k$$$ forms a bitonic sequence: the area increases until the maxima value, then it decreases. From this knowledge, we may do the following:

    • Use the query $$$(1, 1, 2, k)$$$ for each half to get all the required areas. Pick the point with the maximum area as maxima (if there are many points having the same maximum, pick an arbitrary one).
    • Traverse through the not-chosen-as-maxima points in the area-increasing order, check if it comes before or after the maxima using the 2nd type of query (similar to the aforementioned part). If it comes before the maxima, add it to the left side of the current half, otherwise add it to the right side.

    Total number of queries used will not surpass $$$3n-6$$$.

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

Amazing contest, thanks for it! All tasks were very interesting!

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

bullshit contest.

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

Вопрос к авторам задачи B2: зачем TL в одну секунду? У меня решение за O(n * 12), если вы пытались отсечь такое — то у вас, очевидно, не вышло. А если вы не пытались отсечь, то почему приходится пихать?

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

Div2 C & D are just implementation problems.. got stuck with some sily bug in both..

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

what is pretest 5 in C it's so weird to me it's WA ...

isn't it we just see the first 3 numbers and then we can detect the next number

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +13 Проголосовать: не нравится

well i thought if div2b if m<n the ans=-1 otherwise just 12/23/34..n1 ans = 2*sum

what's the counter-case?

got it, stupid i am! and thank you

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

How to solve div2B ?

I was thinking of connecting each of them to the 2 with the smallest values

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

    case where you have 3 fridges and 2 chains, your code will fail. answer should be -1.

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

    Solution:

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

      That's incorrect, consider N = 5 nodes with weights 0 1 2 3 4, and M = 6

      After building the cycle with 5 edges, you can remove the edge between 2 and 3 to create two edges between (0 and 2) and (0 and 3), which costs the same and uses all edges instead of creating a new one that costs 1 more.

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

        So to replace a chain between any 2 fridges with 2 chains coming from the smallest-weighted will cost 2*(smallest-weighted). And add a chain between 2 fridges with least values will cost (smallest-weighted + second-smallest-weighted).

        If the first one is smaller then you can just replace any pair of fridges k time. If not, you can add k number of chain between 2 fidges with least values.

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

          You certainly can't "just replace any pair of fridges k times" since in the example above you can't replace the edges 0 and 1, 1 and 2, 3 and 4 or 4 and 0

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

problem B is bad..

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

    Felt like C in difficulty to me, both implementation and solution

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

      I felt c was horrible in implementation, what did you do for c?

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

        Not too horrible if you store everything in sets, cause you just need to know if it contains stuff or not, something like 3 loops it makes

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

wa9 on E1 and pretests passed on E2. cmooon. Does it means that solution differ or threre are just different tests?

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

I was getting wrong in e1 easy. My strategy was to accumualate lowest prime factors of total 1 at one place(middle of that prime factors) . can any tell me what i m doing wrong?

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

    first i did the same, wa at 8. check all factors(no need prime) and pp

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

      thanks

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

      why should we check all factors? I had solution on contest that passed E2 pretests and failed on E1. It is probably a bug, but i can't find it. Idea is to find all prime factors and enumerate over it. For each prime factor find an answer, grouping by this number to it's meridian. I checked test i failed on, but it is too big. (submission 65381763)

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

    In array 1 1 1 0 0 1 1 1 The best solution would be 4 (divisible by 3)

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

Why were constraints for B changed??

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

When you realize that its not the boxes to be shuffled but the units in them in E1.......

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

After one hour of round I see message with words "sorry, we gave you wrong task". What is it?

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

What was the required time complexity for DIV2 c ?

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

    If a number X appears just 1 time in all triplets, it must be the first/last one in the original permutation. Save number->triplet mapping and start finding with X. It's an O(n) solution.

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

Those pretesting times on div1 D...

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

I guess that the std of D is O(n^1.5) . (because of so large time limit)

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

    I'm pretty sure O(n^1.5) wouldn't need a large time limit, especially not for such low constraints. I've got $$$O(Q \sqrt{N \log N})$$$ where the log factor comes only from binary search. It still got TLE, but on pretests 29 and then 34, so it must be pretty close to passing.

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

      It can be done in $$$O(Q \sqrt{N})$$$ online

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

        Could you please tell how to solve it in $$$O(Q\sqrt N)$$$?

        I've seen your submission which perform (# different subtree size of $$$v$$$) for each update on $$$v$$$.

        The tightest bound I know is $$$O(Q\sqrt N log N)$$$ for (# different subtree size of $$$v$$$) can't be too much.

        I believe it has tighter bound but can't come up of a proof. (Ignore this line, found myself stupid :( )

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

      I think D's O(nlogn) solution is very interesting, but unfortunately std is O(n^1.5)

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

        "std" is the namespace, do you mean the intended solution and that there's a log solution?

        Okay, so the time limit is just intentionally loose and a lot of slow solutions had a chance thanks to that. I'll try squeezing through with my own.

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

        what is the $$$n \log n$$$ solution?

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

          Root the tree at node 1. Suppose we iterate through all the neighbors of node $$$v$$$ for some type 1 query; we can update a child's subtree or the parent's subtree in $$$O(log(n))$$$ with a segment tree. Since the number of neighbors can be $$$O(n)$$$, this solution is $$$O(qnlogn)$$$. So we can't really traverse every child of an update node. Instead, for an update, we will update the biggest child's subtree and the parent's subtree "normally". We won't update the other children but we will keep a running sum of type 1 updates for each node $$$u$$$, which can be used later. The answer for a node will be the value of that node in the segment tree + some of it's ancestor's updates which we didn't apply. We can traverse through each such ancestor and sum up the answer. The number of such ancestors will be $$$O(log(n))$$$. So, our total complexity is $$$O(QlogN)$$$.

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

            The number of such ancestors will be $$$O(log(n))$$$

            Can you explain this?

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

              If the biggest subtree of node u is that of child v, then we call edge (u, v) heavy. Others are light edges. Starting from a node, if we go up to the root, there will be at most $$$O(log(n))$$$ light edges. Proof

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

            That's cool. Thank you!

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

    I am the author of this problem. My solution runs in $$$O(QT\log{N} + QN/T)$$$ with some predefined constant $$$T$$$. I divide all queries into blocks of $$$T$$$. Choosing every $$$T$$$ between $$$175$$$ and $$$350$$$ should give you AC, unless your implementation has huge constant factor.

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

      Might give you AC if you haven't put effort into keeping your constant factor explicitly low. That's how it always is with these problems, you need to check.

      UPD: I just didn't have high enough $$$T$$$ to pass (I had 350), but more optimisations speed it up massively.

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

      I had $$$T=\sqrt{N/\log N}\approx93$$$. Where did you get 175 and 350?

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

        It turns out (a bit counterintuitively) that with such sqrt solutions, the branch "update values after processing a block" has a much worse constant than "answer query", probably because it's basically DFS and that's cache-inefficient and just more to calculate. You need less blocks than the theoretical value implies.

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

      Maybe you should learn from the god of sqrt decomposition ODT

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

bad div2 B, the first time to get ranked 3k+...

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

    Can you explain the problem statement

    I can't even understand it

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

      u need to take care of the case with n = 2(ans = -1), n=3, n=4, when n > 4 && m > n, the smallest ans will not be the circle cause the head and tail can connect to the smallest node, the left edge just link the smallest and second smallest node, just it...

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

        if n = 2 or m < n, ans =-1, otherwise answer is circle and (m — n) edges between two smallest nodes. To lock fridge, you must connect it with two different fridges, so each node must have min 2 edges. So in cost weight of each fridge will be counted minimum 2 times, it just turns out when you connects all fridges in circle and in this case all fridges are private. It takes n edges and other (m-n) edges must have minumum weight, just connect two smallest fridges (m-n) times. Its not clear explanation, but i hope it helps to understand solution.

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

    It was my problem in the round. I didn't know (also the coordinator and writers) about the previous problem. Yes, it is very similar. Sorry about it. My problem was invented completely independently by myself. You see, it is not the first, not the last case when problems coincide. Sometimes it happens, sorry. Moreover, it can happen even on more important official contests. It's a life. The only way to prevent prepare a similar problem, just do not invent any problems. But I don't think it is the right way.

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

    Maybe I have a solution that differs from yours, but I can't get how one can solve this problem using the solution to the problem you mentioned.

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

      Yeah it's subtly different. In the old problem, the permutation is treated as circular.

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

    That is interesting

    I'm not saying it's the same code, but it's interesting submit during the contest somewhere else

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

What is testcase 2 for div2 C ?

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

Took a long time to implement B & C. Problem D, a zig-zag scan will do but i don't have time to finish it correctly. sad.

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

deleted

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

I thought of a solution for Div2. B as it was originally.Any review would be appreciated : I thought of first making 1 cycle of size N(in case when m>=n) and from set of total edges sorted by weight, to remove edges till my graph contains M edges.Is it a correct solution?Please confirm.

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

    but it allow multiedge between two nodes

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

    if all fridges have same value except 2 that have a larger value than the others, you might break the cycle of n. (if m=n+1, the last edge you remove is the one between the 2 larger valued fridges).

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

    In fact, I solved D2/B and still do not get was was wrong with it, why the change?

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

      If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy (assuming that your strategy is the one everyone used — build a cycle of size N and add the edge between the 2 minimums how many times it is needed), while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.

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

    You can add same edge several times so just add the one with minimum weight instead of removing things which might result in incorrect solution

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

Didn't like the problems of this contest, got stuck in Div2/C with some more or less stupid implementation problems. Now, afterwards, having read D and E it would have been better to not work on C.

Afterwards we allways know better.

I was not able to register within like first 10 minutes of contest. That sucks.

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

Not Satisfied with Today's Contest

1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

Here is the test case that made me thinking for over an hour in B and finally your announcement came.

Contest should be unrated for everyone

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

    how did you solve for m > n, same was troubling me for more that hour, when new constraint was announced, I got the idea in 2 minutes but due to some silly mistake and debugging, took some time to get B accepted.

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

      Mathematically if m = 2 * n — 3 Then we can perfectly select two smallest cost fridges and connect all with them.

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

        MikeMirzayanov I guess if you go for previous constraints where m<=2000 80% of people who solved it till that would get WA so I am still wondering why this contest can't be unrated.

        Still wondering why people who couldn't able to figure out for 1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 and go for making a cycle just for n==m should get benefit over people who wasted time.

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

        I was thinking of selecting two smallest cost fridges and adding all else to them but what if m > n && m < 2 * n — 3 ?

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

          Here you can think of select any smaller x<n where this condition could be satisfied and you have remaining m i.e. m-=(2*x)-3 which are enough to join remaining n-=x fridges with at most 2 other fridges. That's where I wasted so much time

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

          Make a cycle of length n, you're left with m — n edges, use them all to connect two smallest fridges. Works for all m and n

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

      you could make multi-edges though

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

        I do but with the new constraints for this test case

        1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

        total cost is 36k approx

        but in old constraints, it should be 16k approx.. that's what I'm saying..

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

          it doesn't affect jury's solution right?

          and your test case not satisfying 1 <= m <= 2000 in the old constraint and 1 <= m <= n in the new constraint

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

            How about 1 10 1000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

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

              it's 17984

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

                And what if we connect 1 and 2 node to all and then just 1 and 2 m — n + 1 times?

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

                  This is invalid. All nodes $$$i$$$ ($$$i>2$$$) will not be private (node $$$1$$$ or $$$2$$$ can unlock them working alone).

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

                  They can't for opening any i both 1 and 2 would be required.

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

                  $$$1$$$ and $$$2$$$ will be required if only every $$$i$$$ ($$$i>2$$$) was connected to both $$$1$$$ and $$$2$$$. And it will give no lower cost (than in the cycle construction method) as weight of every $$$i$$$ ($$$i>2$$$) is still added $$$2$$$ times to the total cost.

                  EDIT: I have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now. Got the issue.

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

                  aight from mohamedeltair's link I can see the problem now, thanks for discussing :)

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

Am I the only one who solved div2 D within 50min but could not solve C:(

BTW, how to solve div2 C?

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

      How are we going to sort the triplet's array?

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

        Don't sort it, just know for each number the three triplets that contains it. Map, vector, anything

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

I wasted 20 minutes because I missed the $$$p_1 = 1$$$ condition in C (interactive problem). Not reading statements carefully hurts :(

I would highlight it or write something like "all these conditions mean that the output is unique", that would help.

Also, I didn't like the round. Problems A-D didn't require much thinking. Just my opinion.

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

    Daaaaaamn I didn't even see that, luckily my solution does that by default

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

    I also missed it, got WA on pretest 1, read the sample error message, fixed it and resubmitted.

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

      wtf, that thing is always displayed?

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

        For samples, yes — it sure is better than dealing with eternal "I got WA on the first sample but my solution works on it!". I didn't even rely on that, just automatically clicked on my submission and scrolled down.

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

          It is helpful, obviously. I just didn't know it exists and it should be this way. Can I see that msg for all problems with a checker?

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

            Yes you can. This is actually a very useful feature of Codeforces that not many people know. I only discovered this during an ICPC training with 10 WA on test 1.

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

              This should definitely be considered as bug not a feature and be fixed asap.

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

                +1, don't rules say that you only see WA/TLE/etc. verdict for the first failed test?

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

                As I mentioned, it helps avoid questions about samples, so I'm not opposed to changing it and creating a Polish Brigade for answering questions during contests (for free, ofc). It would be like Microsoft Tech Support except with Poles instead of Indians!

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

                  What kind of a twisted reasoning is that? Maybe we should write some machine learning algorithm that tells you which line of your code contains bug in order to omit questions?

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

                  That would be interesting, you can even try to pitch it as a startup idea.

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

                  The same argument can be used for introducing rule "show what first failed test looks like". No other platform displays some detailed verdict for test 1, right?

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

                  The first failed test is always in the statements?

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

                  Only if you fail a sample test...

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

                  Topcoder displays checker verdict for test 1 as well :)

                  What exactly is wrong with that? The only problem I see is lack of awareness, and yes, it can be improved.

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

                  Well, that's why you can see it for sample tests. When you have undefined behaviour, you see a different output and a comment for that output. Otherwise, it doesn't give you extra info beyond which rule from the Output section you're failing.

                  It sounds like you're glad you spent so much time on it.

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

                  You are right that Topcoder does that too.

                  The lack of awareness is a big deal (knowing that you should click something and then you will get a hint). Two small issues are being different than other platforms and the fact that a participant can check this way if there is indeed a checker in the problem.

                  It sounds like you're glad you spent so much time on it.

                  It's more convenient to see this thing, but I need to know about this feature in the first place. It's something easy to forget, I don't like it.

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

          What the actual fuck?

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

So, what will happen to me because I had 3 WA submits for prob B and after rejudging, I got 3 AC submits in total, tbh I dont like this contest because of rejudging and in prob D, number of rows is r and c for columns and I followed it, then it took me a lot of time to debug because I used variable with same name (in other contest, they use m and n instead of r and c) and I cant like this kind of trick at all. If it had been m and n, I would have been able to solve this prob on time (with some luck). Anyway, I will try my best till I get to my goal. Have a nice day everybody!!

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

    Tbh, you can make your life easier, instead of

    int r,c; cin >> r >> c;

    just do

    int m,n; cin >> m >> n;

    It isn't really a "trick", it's just your implementation skill.

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

    Use meaningful variable names in your code, you will never be confused.

    int numRow, numCol; cin >> numRow >> numCol;
    
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

    Can anybody tell me why I get a lots downvotes here? I dont think I had any very big mistakes in my comment. Quite annoying when seeing it without any acceptable reasons, hmm...

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

      Your comment is quite boring. Yes, people make bugs. Complaining about the contest because $$$r$$$ and $$$c$$$ are bad variables seems stupid. And you could use some more sentences (dots at the end and then an uppercase).

      But don't care too much about downvotes in CF, they are quite random.

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

What's the correct solution for Div2B in case n < m < 2n — 4? Does greedy work?

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

Wasn't the solution of both the cases (m>n and m<=n) of DIV2 B was to create a cycle and thus the answer will be 2*(sum of weights of all fridges) and if m<n or n=2 answer will be -1 ?

Edit : I think in case of m>n we have (sum of least two weights ) * (m-n) + 2*(sum of weights of all fridges )

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

    Create the cycle, so every fridge has two locks, then add chains between the two cheapest fridges until m is reached.

    Edit: Turns out that this is wrong.

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

    take $$$n = 4, m = 4, a = [0, 0, 1000, 1000]$$$. For "cycle" solution, the answer is $$$4000$$$, but you can get $$$2000$$$ if you connect $$$2-0$$$, $$$2-1$$$, $$$3-0$$$, $$$3-1$$$

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

      2 — 0 costs 0 + 1000

      2 — 1 costs 0 + 1000

      3 — 0 costs 0 + 1000

      3 — 1 costs 0 + 1000

      total: 4000

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

        I think answer will by cycle only since to avoid other person to open the fridge , each fridge should be connected to two other fridges and thus it's weight will be added twice in final answer.Hence answer will be 2*(sum of weights of all fridges) + (sum of least two weights) * (m-n) .

        Is this correct ?

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

          I believe so, because every fridge MUST contribute 2x their weight. So with leftover edges it must be optimal to connect the lightest fridges.

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

    If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy, while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.

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

      Is this a corner case (i.e when of the fridge has weight 0) or there is any other counterexample ? Oh Mike has written a blog on it ! https://codeforces.com/blog/entry/71562

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

        Not a corner case. Just what happens when m > n. The problem basically asks for a graph of minimum cost having each node contained in at least one cycle. Doing a big cycle and adding edges on it is just a greedy solution which is not correct if m > n. However, it is correct for n == m because all nodes should have at least 2 edges so the minimum cost has a lower bound of sum(2 * w[node]). And this is also the answer of the greedy approach.

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

"If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link"

Looks like only positive deltas this round!

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

    If people who did poorly withdraw, then this depends on whether the ratings for the rest of us will be calculated based on their absence or presence. If they are ignored when computing our ratings, then we can expect all our deltas to drop, due to our ranking relative to the size of the group diminishing. I hope this does not create a runaway effect, where contestants fear that their rating would drop due to people who did poorly withdrawing, thus withdrawing themselves and exaggerating this effect.

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

If my rating is still increasing after getting affected, will it be unrated for me?

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

Was the modification in Div2 problem B made to simplify it?

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

Even though I might not gain much rating from this contest, It was indeed educational for me, to work on my weak points.Thank you to all the organizers.

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

Implementation problems occur now and then. It's a nice contest overall. Kudos to setters.

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

Too much implementation for a slow coder like me :( Really regret not being able to finish the div2D in time.

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

Thanks for the contest!

»
4 года назад, # |
Rev. 5   Проголосовать: нравится -18 Проголосовать: не нравится

Deleted .... i am sorry

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

I didn't see the clarification of div2-B ,because I used "m2.codeforces.com" : (

Does anyone have the same situation as me? : (

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

    Then I guess you have all the right to fill that form. If you want it to be unrated for you. :)

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

I think Div1-B2's Time Limit is a little severe and I got TLE on the system test...
How to avoid TLE?
My code is following:
https://codeforces.com/contest/1254/submission/65368643
(I've only used prime numbers as $$$k$$$)

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

    I got TLE on pretest because of high constant also. Many of friends did the same

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

It affected me lots but I want this Round to be Rated for me ^^ From Vietnam with love <3

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

I could not really understand what is the issue with div2 B. what is wrong with the case if(m>n).

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

    I don't think there is any problem. They just wanted the problem to get simpler I guess.

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

When will editorials be released?

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

Why my 1st AC submission skipped and counted as a wrong submission?? and minimized my score from 748 to 690?? Please check out this issue.(skipped : 65373327 AC : 65391169) Thanks

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

    in normal codeforces rounds(except div3) last pretest passed sollution is judged in maintest. You will also get resubmission penalty. But today's div2 B has a special case. Contraint changed during contest. That may be considered if it is applicable for you.

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

Can someone please tell why this code of div2B is giving TLE? 65391058

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

    You do a nested loop here

    for i in range(n):
                for j in range(i+1,n):
    

    Since n is up to 1e5 this is to long.

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

Back to codeforces after my cultivation days, I became stronger, go to blue!

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

is round rated today?

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

I think that the testcases in D might be weak. My time is 420ms while I'm able to create test on which my program runs 3790ms.

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

    A lot of solutions got TLE on either high-numbered pretests or systests, so they can't be that weak. It's more like your solution happens to not have a strong countertest among these tests. (You can uphack other solutions to find out if it's the case for them too.)

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

      Probably not so many people did it like me and this is strange in my opinion as the solution is very simple.

      If vertex $$$v$$$ has some subtree of size $$$x$$$, then ofc. we want to add $$$(n-x)\cdot d$$$ to all the vertices in the subtree. As there can be at most $$$\sqrt{n}$$$ different sizes of subtrees, we can do the query with $$$\sqrt{n}$$$ operations on BIT.

      Is there anybody who also solved it this way?

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

        Yeah, I solved it that way and used Segment Tree instead. Just hacked myself. 65387642

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

        I too solved it this way and am getting TLE because of unnecessary %mod operations.

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

          Each query can contribute atmax (1.5e5)*(1e7) to a vertex. (1.5e5)*(1.5e5)*(1e7) is less than 1e18 hence you can just get away with mod and before printing final result take mod and multiply it with inv(n).

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

        I solved it like that but I used a cool trick to eliminate the log factor — sqrt decomposition! When there are many more writes than reads to a data structure like BIT, updates work in $$$O(1)$$$ and queries work in $$$O(\sqrt{n})$$$.

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

        Interestingly enough, it is possible to make this solution faster by applying sqrt-decomposition ideas.

        Fix some $$$k$$$ and do the segment tree operations only for vertices with at most $$$k$$$ different subtree sizes. For vertices with more than $$$k$$$ different subtree sizes (let's call them special), simply precalculate how an update in them with $$$d = 1$$$ "influences" the answers for other vertices.

        I claim that for $$$k = n^{1/3}$$$ the number of special vertices is $$$O(n^{1/3})$$$. The proof is kind of long and technical, so I hid it under a spoiler:

        Proof

        Now, we can handle the queries of the first type in $$$O(k \log n)$$$ for non-special vertices and $$$O(1)$$$ for special vertices: simply increase their value in some separate array. Similarly, the queries of the second type can be handled in $$$O(\log n + \texttt{#special vertices}$$$): the influences of all non-special vertices are taken from the segment tree and the for special vertices we add up their influences separately.

        The total complexity is $$$O(q \cdot n^{1/3} \log n + n^{4/3})$$$. From theoretical standpoint, it is possible make the complexity slightly better by choosing $$$k = (n / \log n)^{1/3}$$$.

        The code is here: 65440117. It runs unnaturaly quickly, probably for the same reason your code did on the contest: there are no tests in the current testset where it achieves its worst perfomance.

        UPD The previous implementation I linked (65398024) had a bug that made it produce incorrect answers on some tests (to be exact, I forgot that vertex influences itself, not only its subtrees). Thanks to alex9801 for the hack.

        UPD 2 I rewrote the proof of the fact that there are $$$O(n/k^2)$$$ special vertices, because the argument I used before did not actually make much sense (you still can see the old argument on the lower edit levels of this comment, if you wish).

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

    Well I personally think for D, there are a bunch of different approaches, solutions and techniques that can be used to solve it. Even just sqrt decomposition, I have currently seen at least 6 or 7 different ways people did it. So I can tell that preparing test cases for this problem was indeed a pain, and the setters did a pretty good job on it (proved by the number of TLEs on System Tests).

    I'm not saying that having an unique way (maybe got TLE on some unprepared test for large const) can give you a free AC on it. But passing all the test cases with a solution that none of the setters and testers were aware of really deserved an AC.

    On the other hand, I really like your approach for it. Learning the fact that all the subtrees having the same size can be treated similarly really made my day.

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

      How does number of TLEs prove anything? Most people had correct asymptotics and struggled with constant optimizations, so to me it seems that TL was pretty bad.

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

    I solved it this way too and was wondering why would it run so fast :/

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

      ..and got immediately uphacked. I guess it's nearly impossible to make hard test against this solution unless authors were aware of it.

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

WEAK TESTCASE

I was looking at the solution of Div2 problem B of one of my friends. Although it gives the correct minimum total cost, it prints a wrong network of connection. Here is the code This code got AC but it fails to print out a correct output for the following input:

1

4 6

100 1 100 1

I think the test cases for this problem are very weak

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

Div.1D is very usual I think, at least what about $$$N \cdot \sqrt{N}$$$ solution. Unfortunately, I did not manage to write it fast enough for having time to solve E, so don`t like the contest very much. Although, problem C was interesting for me.

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

By the way,I think Div1-C is one of the best problem in geometry! It's my favorite!

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

Why my submissions are skipped? :/

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

How to solve Div1 — D. Tree Queries?

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

    Have a buffer of $$$\sqrt{q}$$$ queries of type 1. When the buffer is full, flush the answer to permanent storage. For each query of type 2, the answer is the permanent storage for that node + the expected value each of the buffered query gives it. Implement an $$$O(1)$$$ LCA query and you have yourself an $$$O((q+n)\sqrt{q})$$$ solution.

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

    I used HLD and BIT to solve the task. For a modification, add $$$d$$$ to $$$v$$$, add $$$d\cdot\frac{\mathrm{size}_v}n$$$ to all nodes outside the subtree of $$$v$$$, and for each child $$$u$$$ of $$$v$$$, add $$$d\cdot\frac{n-\mathrm{size}_u}{n}$$$ to all nodes inside the subtree of $$$u$$$. But in the last type of modification, we only add to its heavy child, and add a tag to $$$v$$$ which means the subtree of every light child $$$u$$$ of $$$v$$$ is increased by $$$d\cdot\frac{n-\mathrm{size}_u}{n}$$$. When handling a query, find its value on BIT and the sum of all tags on its path to the root.

    Complexity : $$$O(n+q\log n)$$$.

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

My electricity was cut out after the 46 th minute of the contest and i have made some submissions for A. Then i tried to participate from my phone but it is absurd. Can you please make the round unrated for me or at least half rated because i was able to participate less that half a contest, please.Can somebody from the codeforces team try and help me or at least respond . arsijo MikeMirzayanov I appreciate the time.

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

    Probably just if you can prove you're not lying.

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

      I have some conversations with friends from that time telling them that my electricity is out, i mean i wouldn't have a reason to lie to them. That's the only thing i have to prove. Also i submitted A from my phone may be they can check the ip or something.Come on why would i go this far just to get an unrated round, i had more than 1 hour in front of me. Even if i was participating badly i had a chance to go up.

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

      But yeah you are right, everybody could say the same thing as me. It doesn't really matter anyway, just sucks if i am going to participate in a round in div2 when there will be a div1 in parallel.

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

    No worries, you will recover your rating in the next contest.

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

Is Div 2 going to be rated?

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

Thank you for the problems!

Especially Div1C, which went for me, like, "how on earth would this be possible in O(n) while finding convex hull clearly isn't?". Loved it.

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

Will codeforces round #601 div.2 be rated??

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

Is div 2 going to be UNRATED? Because div 1 participants RATING is CHANGED already

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

Is this round unrated? I really wish it isn't:(

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

MikeMirzayanov is it rated?

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

MofK can you add somewhere 'hard' version of div 2 B?

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

I couldn't notice the constraint was changed, and I gave up to solve B. I will lost rating.. but fine. Im looking forward to next contest, and I will recover rating :)

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

Div1 starts at 1900 or 2100. Also when will the rating be updated for last 601 div2.

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

Not able to see rating graph for tourist. Profile P.S :The rating graph is showing now.

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

Hello everyone,

I have tried to make video solution for first three problems hoping to help people understand the problem and what was my approach for the same. Codeforces Round 601 Div2 Video playlist

Please do like the video and do subscribe for more such content.

Happy Coding

Divyanshu Kumar

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

Почему-то рейтинг для див2 не обновился

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

How to solve Div.2 C.?

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

    Observe that there are only 2 different possible solutions and either end point will appear only once in total, so you know where to begin from and the second point will appear in a triplet with your assumed first point and have a total frequency of 2, rest you can follow up from there checking points, in triplets where 2 of the points have been placed in order already.

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

Hey, guys! I have a small questions. My idea for problem E sounds like this. Compute the sum of all values in the array. Now we know that if we have k which should divides all numbers in the array, then k should divide the sum. Therefore, I need to check all divisors of sum and see the minimum cost. For a divisor d of the sum, I do the following:

  1. Change v[i] with v[i] % d. Because I am interested only in what sweets (or whatever they are) should be moved.

  2. Go from left to right, find d sweets and move all of them at the index of the (d + 1) / 2 sweet. Do this with two pointers to have O(n).

Now, we also notice that we do not need to check all divisors because if we have d % d1 == 0, then the answer for d is greater or equal than the answer for d1. Therefore, we have to check only the prime factors of the sum.

With this solution, I got WA on test 50 and I have no idea why. This is the submission: 65391533

If someone can explain what I do wrong here or maybe you see a case where my solution is not correct, I would appreciate it. Thank you! Have a good day everyone!

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

    Try to take index of the d/2 sweet (the one right below sweet (d + 1)/2-th) into account also.

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

      My answer is better than the committee one. So even if I take that into account, it will not make my answer worse I assume.

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

When will ratings get updated. It still says afternoon. What is the time zone exactly.

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

Does November/20/afternoon mean next year?

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

Terrible contest

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

Game Theory Problems seldom appear. They should occur more frequently!!!!

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

when will the rating be updated of this contest

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

When the rate of DIV2 will appear ?

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

sometimes you have to wait for afternoon too...not evening :)

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

Any updates regarding ratings ?

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

orz

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

.

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

why rating changes are not appearing for this contest?

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

afternoon 2020 :)

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

Why it happened again?

10enf1.jpg

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

MikeMirzayanov your message is being displayed in "Russian" when I have opened codeforces in "English" and vice versa.

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

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

i am new to codeforces platform.i took part in codeforces round 2 divison ,i solved few questions but i am still unrated . how and when is the rating awarded ?pls help

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

    Hey welcome to codeforces!!
    Actually there has been a small issue in the div2 of previous contest. That's why it's taking a while to update our ratings. It will be done soon. :)

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

    .

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

May i please know why most of the B solutions are remained as pretests passed and why B problem is not considered in the total score ?

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

    Maybe Checker is checking 1st version of problem's solution who has solved it and the 2nd version and making the penalty score perfect by Compairing those, rating will be some called perfect if it does.

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

I want this round unrated for me but i couldn't find the form.

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

Finally rating changes into effect :3

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

Finally rating changed.

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

I solved one Problem and got 174 score but i became Newbie from Pupil. Why!!!!??? [Note : My previous rating was 1242!!]

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

ez problems

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

what is the "wrong output format Unexpected end of file — int32 expected" mean ? why my code can't pass the pretest 5 ? div2 601 problem C

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fp(i,a,b) for(register int i=a;i<=b;i++)
#define mp(a,b) make_pair(a,b)
const int MAXN=4e6+5;
struct Node{
	ll a[4];
}node[MAXN];
int n,root,head,en,a[4],b[4],fa[MAXN],son[MAXN];
map<pair<int,int>,int > book;map<pair<pair<int,int>,int>,int> p;
vector<pair<int,int> > v;vector<int> vv;
inline void ycl(){
    fp(i,1,n) fa[i]=son[i]=i;
    fp(i,1,n-2){
    	fp(j,1,2){
    		fp(k,j+1,3){
    			book[mp(node[i].a[j],node[i].a[k])]++;
    			if(book[mp(node[i].a[j],node[i].a[k])]==2) 
				v.push_back(mp(node[i].a[j],node[i].a[k]));
			}
		}
	}
}
inline int judge(int x){
	if(fa[x]==x&&son[x]==x) return 0;
	if(fa[x]!=x&&son[x]==x) return -1;
	if(fa[x]==x&&son[x]!=x) return 1;
}
inline void rt(){
	fp(i,1,n){
		if(fa[i]!=i&&son[i]==i) root=i;
		if(fa[i]==i&&son[i]!=i) head=i;
		if(fa[i]==i&&son[i]==i) vv.push_back(i);
	}
}
int main(){
	scanf("%d",&n);
	fp(i,1,n-2){
		scanf("%d%d%d",&a[1],&a[2],&a[3]);
		sort(a+1,a+4);
		fp(j,1,3) node[i].a[j]=a[j];
		p[mp(mp(a[1],a[2]),a[3])]=1;
	}
	ycl();
    fp(i,0,v.size()-1){
    	int x=v[i].first,y=v[i].second;
    	if(!judge(x)){
    		int num=judge(y);
    		if(!num) son[x]=y,fa[y]=x;
    		else if(num==1) son[x]=y,fa[y]=x;
    		else son[y]=x,fa[x]=y;
		}
		else if(judge(x)==1) fa[x]=y,son[y]=x;
		else son[x]=y,fa[y]=x;
	}
	rt();int cnt=0;
	b[++cnt]=vv[0],b[++cnt]=root,b[++cnt]=fa[root];
	sort(b+1,b+cnt+1);
	if(p[mp(mp(b[1],b[2]),b[3])]) fa[vv[0]]=root,fa[head]=vv[1],son[vv[1]]=head,son[root]=vv[0],en=vv[0];
	else fa[vv[1]]=root,son[root]=vv[1],fa[head]=vv[0],son[vv[0]]=head,en=vv[1];
	/*
	while(en!=fa[en]){printf("%d ",en);en=fa[en];}
	printf("%d\n",fa[en]);
	*/
    while(en!=fa[en]){
    	printf("%d ",en);
    	en=fa[en];
	}
	printf("%d\n",en);
	return 0;
}
/*
5
4 3 2
2 3 5
4 1 2
*/
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For some testcase your code outputs to few numbers. That should be visible from the test results.

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

Round was really interesting!) Also it was very successfull for me=)

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

For the Point Ordering problem, the problem states the following about cross product:

Recall that the cross product of vector (xa, ya) and vector (xb, yb) is the integer xa * yb — xb * ya. The sign of a number is 1 it it is positive, and −1 otherwise. It can be proven that the cross product obtained in the above queries can not be 0.

But the example given says: Contestant asks a query with t = 2, i = 1, j = 5, k = 6. Jury answers −1. The cross product of A1A5 (2, 2) and A1A6 (4, 1) is −2. The sign of −2 is −1.

2 * 1 — 4 * 2 = -6, not -2, right? Can someone explain about the cross product definition here?