MofK's blog

By MofK, 3 weeks ago, In English,

Hello Codeforces!

I am glad to invite you to Codeforces Round #601, which will take place on Nov/19/2019 17:35 (Moscow time). 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, Prof.PVH, UncleGrandpa925, ngk. 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. stO

  5. ecnerwala

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

Div. 2:

  1. MbahSA (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

»
3 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

from VNOI with love =))

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

From VN with orz!

»
3 weeks 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?

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

Interactive problems are always fun and challenging.

»
3 weeks 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!!

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

    .

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wish so :)

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

From VN with love

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    3 weeks 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! :)

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

      Not yet calculated the case of rejected goals?

      • »
        »
        »
        »
        2 weeks 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.

  • »
    »
    3 weeks 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. =)))

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

Good luck everyone, from Vietnam with love <3

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

There will be Hanoi Tower problems?

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

then-french now-vietnamese next-?

»
3 weeks 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?

  • »
    »
    3 weeks 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

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

    I think it is impossible to be rating 9,999.

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

      forget 9,999.

      It's not even possible to be rating.

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
Rev. 3   Vote: I like it -71 Vote: I do not like it

.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone, from Peru with love <3

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I should be aware of PROF.PVH's tricks

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a nice round!

»
3 weeks 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

»
3 weeks 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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm unable to register Please help!!!

»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

help in B DIV2

»
3 weeks 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.

  • »
    »
    3 weeks 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!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -128 Vote: I do not like it

      No, I hate the problems

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There are a lot of near-synonymous options.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              "Near" is the key. :)

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Neither variant being considered is simpler than any other.

      • »
        »
        »
        »
        3 weeks 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.

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

          Submit a notarized affidavit from the utility company.

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

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

      • »
        »
        »
        »
        3 weeks 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.

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

          I solved E1 .... I think this is a real affect now..

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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 :)

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

          A tricky case — I am sure it's not unique.

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

        I filled the appeal and It was rejected. why it was rejected ? you not just miss up a promising contest for me. but I also get -50. You probably didn't even read any appeals MikeMirzayanov

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

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

    • »
      »
      »
      3 weeks 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 ;

      • »
        »
        »
        »
        3 weeks 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?

    • »
      »
      »
      3 weeks 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 ?

    • »
      »
      »
      3 weeks 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.

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

      make it unrated for Benq, he was strongly affected

    • »
      »
      »
      3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve div. 1 C Point ordering ?

  • »
    »
    3 weeks 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.

»
3 weeks 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 :)

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Div1 C?

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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$$$.

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

bullshit contest.

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

    Why?

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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..

  • »
    »
    3 weeks 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.

»
3 weeks 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

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

how solve div 2 b

»
3 weeks 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

»
3 weeks 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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution:

    Spoiler
    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Solution B
»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

problem B is bad..

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

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

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i guess linked list can help here

»
3 weeks 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?

»
3 weeks 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?

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

    • »
      »
      »
      3 weeks 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)

  • »
    »
    3 weeks 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)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for reply and test case.

    • »
      »
      »
      3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Why were constraints for B changed??

»
3 weeks 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.......

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

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

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the required time complexity for DIV2 c ?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Those pretesting times on div1 D...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks you for this contest

»
3 weeks 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)

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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 :( )

    • »
      »
      »
      3 weeks 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)

      • »
        »
        »
        »
        3 weeks 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.

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

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

        • »
          »
          »
          »
          »
          3 weeks 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)$$$.

          • »
            »
            »
            »
            »
            »
            3 weeks 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?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I was not familiar with this technique. Thank you!

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's cool. Thank you!

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

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

      Maybe you should learn from the god of sqrt decomposition ODT

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the problem statement

    I can't even understand it

    • »
      »
      »
      3 weeks 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...

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +70 Vote: I do not like it
  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there an english editorial for it ?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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

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

What is testcase 2 for div2 C ?

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

benq orz

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but it allow multiedge between two nodes

  • »
    »
    3 weeks 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).

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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 ?

        • »
          »
          »
          »
          »
          3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you could make multi-edges though

      • »
        »
        »
        »
        3 weeks 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..

        • »
          »
          »
          »
          »
          3 weeks 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

          • »
            »
            »
            »
            »
            »
            3 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              it's 17984

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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 :)

»
3 weeks 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?

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

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

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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.

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

      wtf, that thing is always displayed?

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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?

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The first failed test is always in the statements?

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

                  Only if you fail a sample test...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it -45 Vote: I do not like it

          What the actual fuck?

»
3 weeks 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!!

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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;
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    3 weeks 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...

    • »
      »
      »
      3 weeks 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.

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

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

»
3 weeks 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?

»
3 weeks 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 )

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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$$$

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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 ?

        • »
          »
          »
          »
          »
          3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its still 4000! LOL

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks 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!

  • »
    »
    3 weeks 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.

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the contest!

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

Deleted .... i am sorry

»
3 weeks 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? : (

  • »
    »
    3 weeks 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. :)

»
3 weeks 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$$$)

  • »
    »
    3 weeks 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

»
3 weeks 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

»
3 weeks 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).

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will editorials be released?

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. When rejudged, my 1st submission was pretest passed (with constraint m<=n), but CF skipped it in main test. My 2nd submission accepted with a wrong submission penalties. .

      Details
»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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!

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

is round rated today?

»
3 weeks 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.

  • »
    »
    3 weeks 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.)

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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).

      • »
        »