ch_egor's blog

By ch_egor, 6 weeks ago, translation, In English

Hi!

This Sunday will take place All-Russian olympiad for students of 5-8 grades, in the name of Keldysh. Good luck to all the participants! Olympiad is conducted under the guidance of the Moscow Olympiad Scientific Committee, in particular GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil and, of course, Helen Andreeva.

We are happy to announce the Codeforces Round #727 based on the problems of this olympiad! It will be a Div. 2 round, which will take place at Jun/20/2021 13:05 (Moscow time). You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707).

The problems of this olympiad were prepared by _tryhard, Siberian, shishin, Artyom123, TeaTime, Tikhon228 under the supervision of grphil.

Thanks to KAN, Aleks5d and isaf27 for their help in organizing the Codeforces version of this contest and MikeMirzayanov for the Codeforces and Polygon.

Also I would like to thank the Tinkoff company and personally Tatyana TKolinkova Kolinkova for great help with organizing the competition.

Good luck!

UPD1: Thanks to _overrated_ and Ormlis for testing.

UPD2: Scoring distribution: 500 — 750 — 1250 — 1500 — 2000 — 2500

UPD3: Editorial

UPD4: Winners!

Div. 2:

  1. MiyoHijiriido
  2. newbiewzs
  3. tou_xue
  4. SoilCrystal
  5. EEIEE

Div. 1 + Div. 2:

  1. Maksim1744
  2. kal013
  3. jiangly
  4. LayCurse
  5. 2qbingxuan
 
 
 
 
  • Vote: I like it
  • +460
  • Vote: I do not like it

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

uh oh, another russian middle school olympiad

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

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

WYSI

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

Dude, what the heck happened here? [I didn't participate in this round]

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

    weak pretests and tight TL/ML. But the problems were good (very hard in fact).

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

      Bruh,remember the destruction #657 did, Even problem A was 1500 :waturr:

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

You might have already participated in rounds based on the school olympiads, prepared by Moscow Olympiad Scientific Committee (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707).

Yes, I have and this line, this line.......... terrifies me.

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

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

    After reading this comment , I fear Weak Pretests .Since only red coders are testers so they most probably had used the right approach to solve the problems and wouldn't had thought like pupil or specialist or expert ( various greedy approaches or so)

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

      There's a simple solution, just think of the correct/intended approach from the get-go.

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

Note the unusual time

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

The scariest rounds on CF.

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

    Why? I got 44th place in the last round of them

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

      That explains it all :)

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

        I understood that Russian mid-grade Olympiad problems are tough for the majority :)

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

    Problem A is quite tricky !!!!!!!

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

Don't complain about #707 any more everyone...Maybe cf is thinking about a no-pretest contest at that time

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

Aireu from osu must see this contest.

»
6 weeks ago, # |
  Vote: I like it +155 Vote: I do not like it
Meme
»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

WYSI

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

I am new here can anyone tell what these rounds are like

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

As a setter I hope you will enjoy our problems!

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

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

    I am hoping for linear increase in difficulty of problem. In past contests like this we have seen drastic increase in difficulty (like proble B — 900 difficulty to C-1800 ).

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

      707 C passed with n2 algo(which wasnt actually n2 after doing hard analysis, but I didnt know that and got lucky), but still, it was a bad question,not a hard one:)

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

        it was a good question that reminded you to check constraints

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

          now that i have seen the question again and that I understand the beauty of its solution, I second your comment.

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

        It was a Good Problem with pigeonhole principle.

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

    Don't get Dijkstracted. :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +31 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it +59 Vote: I do not like it
Relatable af
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

is this gonna be tough??

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

    Nobody knows at this point of time . From previous such contest that I have taken part in I can say there is always a drastic increase in difficulty from one problem to another in contest like this .

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

    But after solving Problem C.

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

Sus

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

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

    LoL how to break this loop bruuhh !!

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

      Solve Problem C, Because you are grey because you can't.

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

      Try to practice more of C and D questions. In total, more than 80% C questions, but 10-20% D questions too, to get more experience in that difficulty rating.

      Even if you can't solve them, try to spend 10-20 minutes trying to observe different details about the problems, that might help in finding its solution.

      Then try to read the editorial 3-4 times, and see if you can solve it. If you can't, try to see the code solution 3-4 times, and see if you understand it. If you don't, go to youtube, and learn how to solve it.

      Try to see the editorial, editorial solution, and multiple youtube solutions, even if you get it right. It's good to learn new tricks and new approaches.

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

    ahh, humour based on my pain :')

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

    All circular array problems be like.

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

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

I remember the last round they organized. It was extremely hard and rating jump from b to c was huge.
But i remember for another reason. I became specialist for first time in that contest. Kinda emotional >.<

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

The last time I saw this much red with numbers was my maths answer sheet in high school.

:Danger:

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

This comment section is surely one of the most funniest ones. Lots of fear, confusion and memes before the contest itself.

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

Round 657 was arguably the hardest round of last year.

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

How many question will be there??

»
6 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

Please HELP!!

https://codeforces.com/contest/1534/submission/120000620 why is it showing out of bonds when it is perfectly working in XCODE

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    1. This isn't really the place to post that

    2. You swapped the indices around when initializing your array. It should be string** arr = new string*[a]; and then arr[aa] = new string[b];

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

Hope history doesn't repeat itself ಠ_ಠ Looking forward for interesting but moderate round.

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

    problems were hard, but interesting.

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

When you see it!!

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

Does anyone else's latoken rating reduced today after rating returned ?
This round https://codeforces.com/contest/1537/standings

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

hard div 2 :V

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

    will this round be harder than normal div 2??

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

      Yep,it's equivalent to div 1.5

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

      In Russia, it's for grades 5 to 8 :V

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

        All-Russian does't mean its for all students 5-8. Its a final, of course problems gonna be tough

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

Notice the unusual timing

»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Give me some positives here, looks like in the contest I'm not getting it!

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

meme

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

Do russian kids know about video games?

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it
I still have nightmares from 657
»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

No scoring distribution for this round!?

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

Score distribution?

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

    There will be six problems with following scoring distribution.
    1500 2000 2500 3000 3500 $$${\displaystyle \infty }$$$

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

RIP to my ratings in Advance , I got green in last round.

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

What about score distribution?

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

Time to get my ratings higher downwards again!

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

A, B -->> Accepted

»
6 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Hope all these positive ratings of this round's announcement should not convert into negatives after the contest.

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

ch_egor there are less then 25minutes to start. score distribution did not update yet.

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

    1500,3500,3500,3500,3500.

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

    Why it's so important? For real, what you use that information for?

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

      Because many people create code files in advance (like me) and for that we need to know the number of problems

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

        Just create more files! It's free, nothing bad gonna if you create more files than problems

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

          There can be subtasks too
          obviously I am not gonna create every letter number combination

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

      To estimate difficulties of problems.

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

        Why would you need that?

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

          For cheating purposes.

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

          To understand — how many problems I can solve and do I need to solve them faster or normal speed is enough?

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

            Just always solve as many as you can as fast as you can

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

      I use it to get a rough estimate of how many problems will I be able to solve..

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

Wish it be easy:(

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

Here we go again.

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

hope for no googleforces

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

10 minutes to go!

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

left 3 minutes, hope this time I can be green!

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

    this time I just solved 3 problems. I am not sure whether I could go up or down.

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

WYSI

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

I want an extra registration for this contest sir. Please I didn't know about this timing. I thought it is at 8PM.

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

Huuuuuge gap between D and E,F

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

Again a contest with great problems and a hell lot of cheaters.

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

tourist giving div 2 round very rare

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

Bruh, They either come up with div1 round or div3 round everytime. Give us a round with div2 difficulty variant. :weary:

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

How to solve A? Please reply once contest ends

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

I hope the pretests are strong coz I'm really happy right now

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

What do I make wrong if in custom invocation all result are correct but if I send my solution "Time limit exceeded on pretest 1" — How to resolve that in future?

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

    Even if it exceed time limit it will still show the output in custom invocation. Check the time shown below, is it within the time range

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

      But how can I control time range — by means of what? I uderstand that there is a time exceed but how to keep it in line?

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

First time solved four questions in any div2 contest :)

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

    Hope you solve four questions next round too

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

    C bro i sorted the array and if any two successive elements had a difference of greater than x then i increased the groups variable by 1 but if the diff was greater than x but less than or equal to 2*x and also if k>0 then i decreased the increased groups variable and also decreased k by 1, can u tell me where i went wrong.

»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Hoping the pretests for D are strong.

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

problem A was very annoying , I solved BCD but not A

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

That was educational contest, which is no suprise given the target audience.

For me A was much harder than B, and even harder than C. Also gap from D to E/F felt huge.

But nice problems anyway, thanks a lot.

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

Thanks for the round. I think the problems were good, except A. The sad thing is that the gap between D and E was large.

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

After participating in this round, I QUIT :(

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

speedforces

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

payed back more than what i got in last round.

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

A is the hardest problem among A,B,C,D :))

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

Goddamn A

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

Why nlog(n) TLEd on problem B? Please help

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

    You should have used vector& indices=p.s otherwise it will make copy

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

MEET AN EXPRIENCED & SHAMELESS CHEATER This is how kedos123 bypasses Plagiarism testing.

kedos123 does cheating from starting and i reported about it to MikeMirzayanov and he got plag in last round , he abused me in private chat becz i reported him https://ibb.co/JmhSwKL .
guys show your support and again upvote my comment so he again got punished by MikeMirzayanov

People like kedos123 are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .

his todays contest submission 120093195 120088691 , saw his submission timing and also see this dummy variables snippet
;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++; cur+=to_take;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++; cur+=arr[j].first;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;baap++;aaya++;knock++;knock++;tera++;

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

    Didn't get how is he cheating?

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

      saw his submission , he cheated from code which leaked on telegram channel and added dummy functions , dummy variable inbetween the each lines of code , thats how he submitted the code very quickly and also plagchecker cant able to found that sol is someones else copied or not

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

Was D easy? I had no idea how to solve D. Can anyone tell what they did

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

    every question is easy when you have answers floating around on youtube and telegram

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

    Sort the pairs by the number of purchsed objects required to get a discount in non decreasing order. Then proceed with two pointers, one at the beginning and one at the end of the sorted sequence. Buy from the end at full price, until there are enough objects to get a discount at the beginning. Then buy from the beginning at discounted price, until the condition for discount is not satisfied anymore. Alternate until the pointers meet in the middle and the object are exhausted.

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

Dear problem setters if solution is short doesn't mean the problem is easy and should be A

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

feels like educational round :<

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

    It was made for 5 to 8 graders, so no suprise it feels educational.

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

Oh dear, I had a stupid mistake in Problem C. For $$$x=1$$$ I treated students with equal levels wrongly (my code increased $$$k$$$ then, since it thought it needs $$$-1$$$ additional students) and I just couldn't find this case. That cost me so many points, it's infuriating! And the points-ranking curve felt quite flat so it hurt even more. :D

But still, I liked the tasks! Looking forward for Editorial E and F.

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

I lost the round because of the unusual time :((((

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

How to solve D? Thanks.

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

    sort the whole pair according to $$$b_i$$$ .
    then from i = 1 to n -> if already taken no of element >= $$$b_i$$$ take $$$a_i$$$ otherwise take $$$b_j$$$ from the last untaken until taken reached $$$b_i$$$. (for this can use two pointer idea.)

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

Can we solve F by finding the maximum values and (n(i)-n(j)) where a[i]>=a[cur] and a[j]<a[cur] in both directions?

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

For problem D :-

AC submission in 1hour 57 min ---> 1800

AC submission in last 3 min ---> 300+

All due to legends like this shivam.utube23
He is one of many others .

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    https://www.youtube.com/watch?v=xpuLhmR5rZc

    Wondering how 1800 got it in 1 hr 57 min. Here is the guy posting solutions for last 2 contests

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

      They are making it hard for contestants who do all the hardwork to get +ve delta and growth, what they deserve .

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

      This idiot deserve IP ban

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

      Wow!! I go through most of my friends' submissions after the contest ends. Something caught my eye in many solutions and I found it 'not so wise' to first sort the array and then reverse it rather than just reverse-sorting it.

      Now I completely understand why. My peer just converted the leaked code given in this link to Python and submitted it. It is very heartbreaking in the first place that the amount of people that cheat has risen up so significantly. :((

      I really wish rodents like him be banished from codeforces, just like snakes were banished from Ireland.

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

        Sometimes I do the same thing, at first sort, then reverse, with my template it is just faster to type.

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

          Well, in the case of vectors of pairs, with a lambda function defined inline, it looks very odd when we can just change < to > rather than sorting then reversing and in Python we just have to add a minus to the lambda.

          My guy just translated the leaked code in c++ to python.

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

Problem ABCD is very simple and problem E&F is a bit hard. Over 2000 persons solved D, but few of them solved E.

I think D should be more difficult and E should be a little easier.

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

Was D really that easy?

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

    I thought I will just sort the pairs but it's not that simple if I had more time it can be solved maybe

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

    I felt it was easier than your usual Div2. D

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

Everything was going fine until I got TLE.

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

Can someone tell why am I getting WA in B 120121669

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

    I just used a prefix sum as there was a single test case and multiple queries

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    intl x[100002][26];
    

    is in a function (main), so it is uninitialized. After initializing x[0], the rest of the values are only added to (+= and ++) so the stored value could differ from the intended one.

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

I got destroyed after seeing this was meant for students of grade 5-8...

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

How to solve E?

I was thinking of doing some sort of dp whether its possible to place $$$i$$$-th card in $$$j$$$-th hand. If its possible for $$$(i, j)$$$, binary search on largest $$$x$$$ such that its possible to place only other hand (not j) from $$$(i + 1, x - 1)$$$ (check with pref sums) and $$$k_i$$$ in hand $$$j$$$ is valid in the same range (check with RMQ). Now just mark all $$$(y, j)$$$ as good for all $$$i + 1 \leq y \leq x$$$ using difference sums. I'm still not sure if this is correct as I ran out of time implementing.

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

A was tougher than B.

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

always got WA in pretest 6 for problem C T_T idk what's wrong with my code, need to see editorial

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

    consider this example for array : 1 13 and x=4. You might be adding 3 extra numbers to make stable group but instead you can do it only using 2 extra numbers.

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

      AHHH, you are right, I think I miscalculated the number of people with (v[i+1]-v[i])/x. Thank you.

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

I think in Russia they don't like int they only like long long.

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Scoring distribution is wrong.It should be 1000-1250....and so,on

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

Can someone explain what is wrong in my approach for problem D? I am using greedy with prefix and suffix sums. Sort the given 2D array according to products required for discount and then traverse from top and see how many products you can get for a discount.

120081648

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

For problem c, What's wrong in this code?

    vi v;input(v,n);
    sort(v.begin(),v.end());
    ll ans = n;
    for(ll i=1;i<n;i++){
        if((v[i]-v[i-1])<=x)  {
            ans--;
            continue;
        }
        if(k>0){
            if((v[i]-v[i-1])<=2*x){
                ans--;
                k--;
            }
        }
    }
    cout<<ans;
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take this example: x=10, k=2; 1 2 3 500 511 522

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

    The gap can be greater than 2*x which you haven't considered. Also, there is the case of priority of which gap to close first, which hasn't been taken into account.

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

    You can add multiple students between elements.


    2 2 2 1 7

    Answer is 1, add 3 and 5 to it.

    Even if you remove $$$\leq 2 \times x$$$ condition from your code another problem will appear

    3 1 4
    1 100 108
    
    

    Here its optimal to add the one person between $$$100$$$ and $$$108$$$, whereas your code (with the fix) would try to insert it between $$$1$$$ and $$$100$$$. You need apply the operations in non decreasing order of diffs ($$$v_i - v_{i - 1}$$$) for it to be optimal.

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

    3 2 2

    1 2 8 -->ans : 1 try this

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

    Even when the difference between the two consecutive number is greater than 2*x, in some cases, you can put 2 or more extra numbers between them so that they are connected. However, you have only accounted for the difference lower or equal to 2*x which is incorrect.

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

Also got 4 TLE seemingly just because codeforces doesn't use the latest pypy

It always hurts getting TLE with correct asymptotic and it is even more painful when you know that the problem is not in the language per se or in the code but just in the version the judge uses

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

Anyone tried Top-Down approach for D?

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

Can anyone please help why I am getting a TLE in [problem:727 (Div. 2)-B Love song] 120120431,even though I am having two loops and time complexity is O(n^2) which justifies the constraints as it comes out be 10^12 and we can perform 10^8 operations in one second??If I am calculating time complexity wrong please tell how to calculate it properly as I am facing this problem in many questions

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

    I have not gone through your code but assuming it is O(n^2), how can 10^12 operations be performed if in one second you can perform 10^8. 10^12 / 10^8 = 10^4 second.

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

    your complexity is n * q, that is 10^10, and that is hundred times 10^8

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

For A think in reverse from second last participant ans = 1 , 2 , 3 .... , (t/x-1) , t/x , t/x , t/x ........

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

Russian Olympiad rounds and Weak Pretests are really Synonyms. Thanks For FST in C , I was accessing Garbage value , I know it's my mistake but then why Pretests passed . :/ .

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

Contest was amazing but Why There is A problem very Annoying :( killed me

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

Why I am getting WA on problem A? Used Approach reverse from second last participant ans = 1 , 2 , 3 .... , (t/x-1) , t/x , t/x , t/x ........

Edit: Got it. t/x can be greater then n.

My Solution
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F? Any hint??

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

    in problem F, we notice one mathematical fact that helps us solve the problem: the distance of the median and the element of any array depends only on $$$nS-nG$$$, where $$$nS$$$ is the number of elements smaller than that element and $$$nG$$$ is the number of elements larger than that. To find the exact expression you should break it into two cases: $$$nS \geq nG$$$ and $$$nS < nG$$$. For $$$nS \geq nG$$$, it comes out to be $$$val = floor((nS-nG)/2)$$$ and for $$$nS < nG$$$ it comes out to be $$$val = floor((nG-nS+1)/2)$$$.

    So you can find subarrays with the maximum value of $$$val$$$ for each of those two cases. For this I implemented two lazy segment trees which output max/min and store prefix sum.

    Then you iterate in descending order and you can maintain in the array that if the value is greater than curr, it is $$$+1$$$ otherwise it is $$$-1$$$. Then prefix sum gives the value of $$$nG-nS$$$ for a prefix.

    120142177

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

Just ban cheaters accounts. It's getting out of control.

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

    Honestly, still surprised 2k+ people were able to solve D

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

      And here I am, getting WA in D cause I mistakenly wrote i>0 instead of i>=0 in a for loop.

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

After sys failing C; Don't believe floating-point arithmetic.

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

So I tried to find the ordering of the products in problem D with exchange argument. However I couldn't is there any proof for the order of products using exchange argument ?

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

    Here's what I can think of:

    Let's say I have to decide the order between two products A and B (where B has a higher required-number-of-prior-purchases-to-unlock-discount value)

    Now I know that no matter what order I go with, I won't be able to purchase B-type products at the discounted price.

    But there CAN exist some order where I can obtain A-type products at a discount. This order will be when I purchase A-type products after purchasing the minimum required B-products to unlock A's discount.

    After that I can buy all A-type products and then buy any remaining B-types.

    To summarize: I will ALWAYS have to spend full price on the objects whose discount-cutoff is high, but there's a chance I can unlock a discount on lower discount-cutoff products. Therefore I should make any full-price purchases on higher discount-cutoff products so I can unlock discounts on lower discount-cutoff products simultaneously.

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

A was really interesting.Mind negetive numbers. And it's my first turn solve many problems in div2 thanks a lot!

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

Why did C not have multiple testcases in each pretest? It has so many FSTs.

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

Most of the code using pypy C is 0.99x seconds, isn't it unreasonable? I still don't know why my code is TLE

code
»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I think TL on problem C is too tight for Pypy3. Or I was wrong?

(Edit: I got TLE while system testing.)

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

I thought tourist will be streaming for today's contest when he registered.

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

can someone give counter case for pretest 7 of problem D, I tried similar to solution mentioned by others above. Submission

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

Just Python Things :)
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Lol FSTs. What just happened there? I see a lot ppl getting FST on C and D. XD

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

      In case of python int64 numbers which are really slow in codeforces version of pypy on windows

      D should be fine if you solve it with two pointers, but gets the same problem if you use binary search like I did

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

        Feels like the pythonistas are in the middle of an appocalypse. I have read that blog mentioning int64's time limit problem by pajenegod earlier, but I've seen it in action for the first time.

        Really sorry for all those who FST'ed because of this problem. I love Python for every reason possible but I just don't use it in CP because people don't care about us and our time limits :(

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

          The thing that sucks the most is that it is not some fundamental performance issue of python, It is just the version/instance installed at codeforces sucks, Which makes it more annoying to get fst on that

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

      TLE on test 18 ╥﹏╥

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

    Does Russian Olympiad allow Python? This might be part of the issue?

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

    Is it possible that the judges will increase the time limits for problem С?

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

    What extension do you use ?

»
6 weeks ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Why this gives WA on test 37 in C I didn't expect that :(

cin>>n>>k>>x;
for(int i=0;i<n;i++)
{
    cin>>a[i];
}
sort(a,a+n);
vector<long long>tmp;
for(int i=1;i<n;i++)
{
    if(a[i]-a[i-1]>x)
    tmp.push_back(a[i]-a[i-1]);
}
sort(tmp.begin(),tmp.end());
int si=tmp.size();
si++;
//cout<<si<<endl;

for(int i=0;i<tmp.size();i++)
{
    long long chk=(tmp[i]+2*x-1)/(2*x);
    if(chk<=k)
    k-=chk,si--;
    else break;

}
cout<<si<<endl;



        return 0;
        }

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Strange formula. Suppose you have tmp = {0, 10}, x = 2. So k = 4 needed to have one group. Your solution thinks it can make one group with k = 3 only.

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

It's sad and funny how pretests and 1 sec limit killed most of python solutions. During contest I was happy my C passed and sad cause D didn't. Now, I'm happy D failed, since I have rewritten D in c++ and sad that C passed pretests, since C failed tests :) :( Mood roller-coaster round :)

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

Please give some relief in tightness of time bounds for python users. My O(n) solution for Q. C gave TLE during system testing.

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

    Hey, a couple of things.

    1. Your solution is actually nlogn, since you are sorting.
    2. My pypy submission also failed on system tests, and it's really sad. Turns out the pypy version that codeforces uses is just really bad with large numbers. So much so, in fact, that the same solution passed comfortably using Python 3.9. I really hope they do something about this.
»
6 weeks ago, # |
  Vote: I like it +85 Vote: I do not like it

I could not understand the statement of problem F during the round. It has many ambiguous points.

I first read maximized value as |i-(center's value)|, |a[i]-(center's value)|, not |(position of a[i] in a subsegment) — (position of center)|.

The statement said "the center" is not the position but the element itself, so the distance compares the position and element's value. I messed up. First sample which has explanation is pretty weak to resolve them.

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

    Exactly my thoughts as well. Surprisingly, each explanation bullet for the first sample also agrees with the other interpretation of the problem xD

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

Why do I have TLE? I don't understand.

120075328

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

    Too many sum operations. Google "prefix array".

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

      I got AC with same code 120078694

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

        You can see your solution runs for 1.8s ,very close to 2s.Actually we can let every question' l=1 and r=n ,then your algorithm turns into O(n^2)

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

    Use fenwick tree or something so the sum only calculated once. For your code it will be calculated every time it receive input, but with fenwick tree we can store the sum first so we can access it later (I think it is called dynamic programming(?))

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

Feel my pain

»
6 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

Short Solutions

Solution A
Solution B
Solution C
Solution D
»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Why did python O(N) TLE in C
;-;

Time to reject python embrace c++

»
6 weeks ago, # |
  Vote: I like it -49 Vote: I do not like it

Extremely Sorry for posting this question here, Regarding yesterday's atcoder beginnner contest abc206 F. (https://atcoder.jp/contests/abc206/tasks/abc206_f). I tried to solve it by DP.

This is what I tried.

My understanding for intersecting is, Two intervals A, B are said to intersect if there is atleast one real number x such that x belongs to both A and B. (i.e. intervals which lie completely within each other do intersect).

With this definition, I tried the following logic. First for each position from 1 to 100 note the end positions of the interval starting from that position. Similarly find the minimum end position of all the intervals starting at or after the current position.

Then do a reverse dp (states 0, 1 : 0 -> considering all the intervals starting from >= current position, whether the 1st player can win. 1 -> considering all the intervals starting from current position (only this current position), whether the 1st player can win).

The transition is for all the intervals starting from current position, dp[i][1] = dp[i][1] | !dp[end_position][0]. Then For j from i until the minimum end position -1, dp[i][0] = dp[i][0] | dp[j][1]

https://atcoder.jp/contests/abc206/submissions/23636854

But it does not work. I could not think of a case where it fails. Could somone please suggest a case where it does not work ?

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

i goofed up!

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

Ideone Link: D solution Link Matching submissions which I have found till now: https://codeforces.com/contest/1539/submission/120121120 by Harsh18064, https://codeforces.com/contest/1539/submission/120121447 by dvjakhar31, https://codeforces.com/contest/1539/submission/120121675 by Abhijeet007

There might be many more such submissions which would have copied from the same source. MikeMirzayanov and ch_egor Please have a look at this. I did not want to pollute the CF blog but this type of behaviour must be penalised.

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

greedy forces

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

What is disappointment?

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

For 1539C - Стабильные группы, 120068517 (PyPy 3) and 120127418 (Python 3) are exactly the same, however, the PyPy one got TLE while the Python one got AC. Why did this happen?

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

Please try to make pretests stronger. T~T. My Global rank fell from 63 to 1807, because C failed on main tests!

Your text to link here...

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

    that's the point of the pretests, they are not supposed to cover ALL testcases. They are giving meaning to hacks.

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Pretests for C are too weak. There are no tests with max K. My code passed pretests but failed main tests because I forgot to use long long for k :(

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

To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

I can't believe what I just did The same code that TLE'd in a contest in pypy 3 passed in python 3

python 3

https://codeforces.com/contest/1539/submission/120128958

pypy 3

https://codeforces.com/contest/1539/submission/120107086

CAN ANYONE PLEASE EXPLAIN THIS

TIA

»
6 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

The pretests of C is soo weak.

Even in the test cases if you just add 1 participant in every place which has diff > x then it will pass upto test case 24.

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

can someone provide insight on why my code for A fails link. I find the first m elements which contribute "t/x" to answer then there is AP for remaining (n-1-m) elements from (t/x-1).....0

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

editorial please

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

In problem D,Can anyone please explain as to why it would not be optimal to take more than required ai's for any i? Can it not be the case that it would profit us later?

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

    It is not optimal to buy any product more than it is actually required. Consider if you buy an extra item at a discounted price and then by doing this step your total number of bought items reaches a level that you get a discount for buying another item. In this scenario, your total incurred cost would be 1+1=2. Instead of buying this extra item, you can buy the second item at its original price i.e. 2.

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

    I spent a lot of time at the contest for figuring this out lol. So far I can't come up with counter-example nor a formal proof.

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

Why I am getting TLE in C what I have done is if diff > x then insert if even that not work increase result by 1 120131849

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

Pretest of problem C seems very weak (╥╯^╰╥)

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Simple and short accepted solution for problem C using sorting and heap C++, (in case someone needs). https://codeforces.com/contest/1539/submission/120114415

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

How to solve E?

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

Where is editorial?