When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

MofK's blog

By MofK, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +69 Vote: I do not like it

from VNOI with love =))

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

From VN with orz!

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

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

»
4 years ago, # |
Rev. 2   Vote: I like it +63 Vote: I do not like it

Interactive problems are always fun and challenging.

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

    If it is not a binary-search problem :)

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

      It indeed is not :) how do you feel about today's interactive problem?

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

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

    .

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

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

    Wish so :)

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

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

From VN with love

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

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

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

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

      Not yet calculated the case of rejected goals?

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

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

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

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

Good luck everyone, from Vietnam with love <3

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

There will be Hanoi Tower problems?

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

    A character smarter than the cat in your profile picture doesn't exist.

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

    Actually the 9999 upper-bound is modifiable from the contest panel. Can change it to 1e9+7

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

    .

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

      forget 9,999.

      It's not even possible to be rating.

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

    That means one day tourist will be affraid of being banned from div1

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

Good luck everyone, from Peru with love <3

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

I should be aware of I_love_tigersugar's tricks

»
4 years ago, # |
  Vote: I like it -27 Vote: I do not like it

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

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

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

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

Have a nice round!

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

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

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The only question about the contest

Will the No. 1 spot in the rating change ?

tourist or Benq or Anyone else

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

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

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

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

help in B DIV2

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

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

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

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

      No, I hate the problems

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

      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 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

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

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

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

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

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

            There are a lot of near-synonymous options.

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

              "Near" is the key. :)

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

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

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

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

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

          Submit a notarized affidavit from the utility company.

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

            Sorry but i didn't understand what you just said.

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

        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 years ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

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

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

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

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

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

      iMAGE ;

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

        lol you haven't even participated in a single contest, why are you whining?

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

      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 years ago, # ^ |
      Rev. 3   Vote: I like it -9 Vote: I do not like it

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

      make it unrated for Benq, he was strongly affected

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

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

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it +36 Vote: I do not like it

    Div1A reminds me of this CF995A — Tesla when people go derp mode real hard.

    Contestants tried heuristic solutions, dijkstra, weird heaps, while you only need loops to solve it.

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

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

How to solve div. 1 C Point ordering ?

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

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

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

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div1 C?

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

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

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

»
4 years ago, # |
  Vote: I like it -42 Vote: I do not like it

bullshit contest.

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

    Why?

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

      Sorry, in B I was missing n=2 case, it took me 1 hour to find it, so contest went bad for me..Contest was good.

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

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

    the same for me , and problem B changed during the contest was very confusing to me, !Rated.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # |
Rev. 5   Vote: I like it +13 Vote: I do not like it

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

How to solve div2B ?

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

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

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

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

    Solution:

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

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

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

          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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Solution B
»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

problem B is bad..

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

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

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

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

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

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

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

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

      thanks

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

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

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

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

      thanks for reply and test case.

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

      you can collect 3 on 2-nd and 7-th place. What is wrong with idea of accumulating prime factors?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Why were constraints for B changed??

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

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

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

    When you realize you passed pretests with a blatantly incorrect solution ...

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

What was the required time complexity for DIV2 c ?

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

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

Those pretesting times on div1 D...

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

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

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

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

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

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

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

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

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

        "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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

            Can you explain this?

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

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

                I was not familiar with this technique. Thank you!

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

            That's cool. Thank you!

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

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

      Maybe you should learn from the god of sqrt decomposition ODT

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

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

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

    Can you explain the problem statement

    I can't even understand it

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

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

        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 years ago, # |
  Vote: I like it +70 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

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

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

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

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

    That is interesting

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is testcase 2 for div2 C ?

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

deleted

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

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

    but it allow multiedge between two nodes

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

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

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

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

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

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

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

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

      you could make multi-edges though

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

        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 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

              it's 17984

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

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

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

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

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

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

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

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

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

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

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

BTW, how to solve div2 C?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Solution C
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

»
4 years ago, # |
Rev. 2   Vote: I like it +55 Vote: I do not like it

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

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

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

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

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

      wtf, that thing is always displayed?

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

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

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

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

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

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

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

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

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

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

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

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

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

                  The first failed test is always in the statements?

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

                  Only if you fail a sample test...

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

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

                  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 years ago, # ^ |
                  Rev. 2   Vote: I like it -12 Vote: I do not like it

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

          What the actual fuck?

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

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

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

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

    int numRow, numCol; cin >> numRow >> numCol;
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Or just H and W, as in height and width.

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

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

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

        Your comment helps me feel a little better. Thank you!

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      2 — 0 costs 0 + 1000

      2 — 1 costs 0 + 1000

      3 — 0 costs 0 + 1000

      3 — 1 costs 0 + 1000

      total: 4000

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

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

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

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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

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

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the contest!

»
4 years ago, # |
Rev. 5   Vote: I like it -18 Vote: I do not like it

Deleted .... i am sorry

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

Does anyone have the same situation as me? : (

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

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

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

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

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

When will editorials be released?

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

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

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

»
4 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

is round rated today?

»
4 years ago, # |
  Vote: I like it +77 Vote: I do not like it

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

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

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

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

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

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

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

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

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

        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 years ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

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

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

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

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

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

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

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 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it +42 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why my submissions are skipped? :/

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve Div1 — D. Tree Queries?

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

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

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

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

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

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

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

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

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

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

Is Div 2 going to be rated?

»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

MikeMirzayanov is it rated?

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

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

    Because of div2 B. We need to wait people fill that form. Be patient :D

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

      I mean it says afternoon, but based on what time zone exactly?

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

        I guess that "afternoon" is according to your time zone. It will be "morning" for some and "night" for some other people.

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

          it's saying afternoon for me too

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

How to solve Div.2 C.?

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

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

»
4 years ago, # |
Rev. 2   Vote: I like it +80 Vote: I do not like it

Does November/20/afternoon mean next year?

»
4 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Terrible contest

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

when will the rating be updated of this contest

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

When the rate of DIV2 will appear ?

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

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

»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any updates regarding ratings ?

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

orz

»
4 years ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

.

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

why rating changes are not appearing for this contest?

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

afternoon 2020 :)

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

Why it happened again?

10enf1.jpg

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

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

    i have used google translator to read this.

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

    Translation: Task 1255B may temporarily be reverted to the old version, some solutions may be temporarily tested. I am working on a rating update. MikeMirzayanov

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

    A person's first language comes out when he is so annoyed fixing lot of issues. We can't blame him.

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

    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 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    .

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

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

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

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

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Finally rating changes into effect :3

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Finally rating changed.

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

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

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

    Rating change based on your place on standing, not the points you get in the contest

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

ez problems

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

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

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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?