ch_egor's blog

By ch_egor, 19 months ago, translation,

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, shishyando, 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:

Div. 1 + Div. 2:

• +460

| Write comment?
 » 19 months ago, # |   +118 uh oh, another russian middle school olympiad
•  » » 19 months ago, # ^ |   +126 Yet another $Div$ $1.5$ round
•  » » » 19 months ago, # ^ |   +74 just gave a div 2.5, its time for payback xd
•  » » » 19 months ago, # ^ |   +8 Your account name said it all ROFL.
•  » » » 19 months ago, # ^ |   0 Finally, it was Div 2 only, lol
•  » » » 19 months ago, # ^ |   +3 It turned out to be div-2.75 if not div-3
•  » » » » 19 months ago, # ^ |   +4 Div.3 combined with Div.1, more precisely.
 » 19 months ago, # |   +93
•  » » 19 months ago, # ^ |   +5 WYSI
•  » » 19 months ago, # ^ |   +5 WYSI
 » 19 months ago, # |   +35 WYSI
 » 19 months ago, # | ← Rev. 2 →   +20 Dude, what the heck happened here? [I didn't participate in this round]
•  » » 19 months ago, # ^ |   +26 weak pretests and tight TL/ML. But the problems were good (very hard in fact).
•  » » » 19 months ago, # ^ |   +25 Bruh,remember the destruction #657 did, Even problem A was 1500 :waturr:
 » 19 months ago, # |   +79 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.
 » 19 months ago, # |   +100
 » 19 months ago, # |   +5
•  » » 19 months ago, # ^ |   +10 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)
•  » » » 19 months ago, # ^ |   0 There's a simple solution, just think of the correct/intended approach from the get-go.
 » 19 months ago, # |   +76 The scariest rounds on CF.
•  » » 19 months ago, # ^ |   -57 Why? I got 44th place in the last round of them
•  » » » 19 months ago, # ^ |   +52 That explains it all :)
•  » » » » 19 months ago, # ^ |   0 I understood that Russian mid-grade Olympiad problems are tough for the majority :)
 » 19 months ago, # | ← Rev. 2 →   +35 Don't complain about #707 any more everyone...Maybe cf is thinking about a no-pretest contest at that time
 » 19 months ago, # |   +5 Aireu from osu must see this contest.
 » 19 months ago, # |   +155 Meme
 » 19 months ago, # |   +14 WYSI
 » 19 months ago, # |   +4 I am new here can anyone tell what these rounds are like
•  » » 19 months ago, # ^ |   +43
 » 19 months ago, # |   +142 As a setter I hope you will enjoy our problems!
•  » » 19 months ago, # ^ |   -26
•  » » 19 months ago, # ^ |   +2 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 ).
•  » » » 19 months ago, # ^ |   +2 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:)
•  » » » » 19 months ago, # ^ |   +4 it was a good question that reminded you to check constraints
•  » » » » » 19 months ago, # ^ |   0 now that i have seen the question again and that I understand the beauty of its solution, I second your comment.
•  » » » » 19 months ago, # ^ |   +1 It was a Good Problem with pigeonhole principle.
•  » » 19 months ago, # ^ |   +7 Don't get Dijkstracted. :)
•  » » 19 months ago, # ^ |   +31 TeaTime orz
 » 19 months ago, # |   +59 Relatable af
 » 19 months ago, # |   +3 is this gonna be tough??
•  » » 19 months ago, # ^ |   +20 But after solving Problem C.
 » 19 months ago, # |   +154 meme"Huee Huee Hueee"
•  » » 19 months ago, # ^ |   +14 LoL how to break this loop bruuhh !!
•  » » » 19 months ago, # ^ |   +4 Solve Problem C, Because you are grey because you can't.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +2 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.
 » 19 months ago, # |   +17
•  » » 19 months ago, # ^ |   +10 Back Story?
 » 19 months ago, # | ← Rev. 2 →   +9 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 >.<
 » 19 months ago, # | ← Rev. 2 →   +31 The last time I saw this much red with numbers was my maths answer sheet in high school.:Danger:
•  » » 19 months ago, # ^ | ← Rev. 2 →   +7 I hope I am wrong though and everyone except pupils and newbies get +ive delta.An irrelevant meme.
•  » » » 19 months ago, # ^ |   +4 2+(2*5)!=12????? do they different in Japan????
•  » » » » 19 months ago, # ^ |   0 First, answer this. 2!=2True or False?
 » 19 months ago, # |   +13 This comment section is surely one of the most funniest ones. Lots of fear, confusion and memes before the contest itself.
 » 19 months ago, # |   +12 Round 657 was arguably the hardest round of last year.
 » 19 months ago, # |   +4 How many question will be there??
 » 19 months ago, # |   -48 Please HELP!!https://codeforces.com/contest/1534/submission/120000620 why is it showing out of bonds when it is perfectly working in XCODE
•  » » 19 months ago, # ^ |   +11 This isn't really the place to post that You swapped the indices around when initializing your array. It should be string** arr = new string*[a]; and then arr[aa] = new string[b];
 » 19 months ago, # | ← Rev. 3 →   0 Hope history doesn't repeat itself ಠ_ಠ Looking forward for interesting but moderate round.
•  » » 19 months ago, # ^ |   +6 problems were hard, but interesting.
 » 19 months ago, # |   0 When you see it!!
 » 19 months ago, # | ← Rev. 3 →   0 Does anyone else's latoken rating reduced today after rating returned ? This round https://codeforces.com/contest/1537/standings
 » 19 months ago, # |   0 hard div 2 :V
•  » » 19 months ago, # ^ |   0 will this round be harder than normal div 2??
•  » » » 19 months ago, # ^ | ← Rev. 4 →   0 In Russia, it's for grades 5 to 8 :V
•  » » » » 19 months ago, # ^ |   +3 All-Russian does't mean its for all students 5-8. Its a final, of course problems gonna be tough
 » 19 months ago, # |   +1 Notice the unusual timing
 » 19 months ago, # |   -8 Give me some positives here, looks like in the contest I'm not getting it!
 » 19 months ago, # | ← Rev. 3 →   +152
 » 19 months ago, # |   +17 Do russian kids know about video games?
•  » » 19 months ago, # ^ |   +26 Some of them are video games creators.
 » 19 months ago, # |   +19 I still have nightmares from 657
 » 19 months ago, # |   +14 No scoring distribution for this round!?
 » 19 months ago, # |   0 Score distribution?
•  » » 19 months ago, # ^ |   +55 There will be six problems with following scoring distribution. 1500 2000 2500 3000 3500 ${\displaystyle \infty }$
 » 19 months ago, # |   +4 RIP to my ratings in Advance , I got green in last round.
 » 19 months ago, # |   +6 What about score distribution?
 » 19 months ago, # | ← Rev. 2 →   0 ch_egor there are less then 25minutes to start. score distribution did not update yet.
•  » » 19 months ago, # ^ |   +19 1500,3500,3500,3500,3500.
•  » » 19 months ago, # ^ | ← Rev. 2 →   -17 Why it's so important? For real, what you use that information for?
•  » » » 19 months ago, # ^ |   +12 Because many people create code files in advance (like me) and for that we need to know the number of problems
•  » » » » 19 months ago, # ^ |   +6 Just create more files! It's free, nothing bad gonna if you create more files than problems
•  » » » » » 19 months ago, # ^ |   +5 There can be subtasks tooobviously I am not gonna create every letter number combination
•  » » » 19 months ago, # ^ |   -10 To estimate difficulties of problems.
•  » » » » 19 months ago, # ^ |   -8 Why would you need that?
•  » » » » » 19 months ago, # ^ |   0 For cheating purposes.
•  » » » » » 19 months ago, # ^ |   0 To understand — how many problems I can solve and do I need to solve them faster or normal speed is enough?
•  » » » » » » 19 months ago, # ^ |   0 Just always solve as many as you can as fast as you can
 » 19 months ago, # |   0 Wish it be easy:(
 » 19 months ago, # |   +3 Here we go again.
 » 19 months ago, # |   0 hope for no googleforces
•  » » 19 months ago, # ^ |   +8 how about cheatforces?
•  » » » 19 months ago, # ^ |   0 yes too many cheaters
 » 19 months ago, # |   +5 left 3 minutes, hope this time I can be green!
•  » » 19 months ago, # ^ |   0 this time I just solved 3 problems. I am not sure whether I could go up or down.
•  » » » 19 months ago, # ^ |   +8 you can use CF predictor!
 » 19 months ago, # |   +5 WYSI
 » 19 months ago, # |   0 I want an extra registration for this contest sir. Please I didn't know about this timing. I thought it is at 8PM.
•  » » 19 months ago, # ^ | ← Rev. 2 →   -8 Nightmare Round
•  » » » 19 months ago, # ^ |   0 Is it possible to get register now?
•  » » » » 19 months ago, # ^ |   0 Participate virtually. Anyways Only 40 mins are left Now
•  » » » » » 19 months ago, # ^ |   0 Completed three problems offline that's why asking for registration.
•  » » » » » » 19 months ago, # ^ |   -8 Nothing cant be done now
 » 19 months ago, # |   +36 Huuuuuge gap between D and E,F
 » 19 months ago, # |   +3 Again a contest with great problems and a hell lot of cheaters.
 » 19 months ago, # |   +3 tourist giving div 2 round very rare
•  » » 19 months ago, # ^ |   0 tourist missing Russian Olympiad based contests is even rarer (check past rounds)
 » 19 months ago, # |   0 Bruh, They either come up with div1 round or div3 round everytime. Give us a round with div2 difficulty variant. :weary:
 » 19 months ago, # |   +3 First time solved four questions in any div2 contest :)
•  » » 19 months ago, # ^ |   0 Hope you solve four questions next round too
 » 19 months ago, # |   -8 Hoping the pretests for D are strong.
 » 19 months ago, # |   +4 problem A was very annoying , I solved BCD but not A
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 give you a test: 2 1 2000000000. I hack myself use this test.
 » 19 months ago, # |   +21 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.
•  » » 19 months ago, # ^ |   +5 And to me A was much harder than D xD
•  » » 19 months ago, # ^ |   +1 I was able to solve A easily but got struck in D :). Can you give some ideas for solving D?
•  » » » 19 months ago, # ^ |   +4 If we can buy products for price 1 we do. Else we buy some items of the product with max(b[i]).
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +4 Buy the products with higher bi until you reach level of lowest bi
•  » » » » 19 months ago, # ^ |   0 I tried similar solution. Could you please tell my mistake. Submission
•  » » » 19 months ago, # ^ |   0
•  » » 19 months ago, # ^ |   +3 Yes i took only 10-10 mins for B and C but A took me 1 hour just to find out that t/x can be > n-1 so we have to make it n-1.
•  » » 19 months ago, # ^ |   +3 What was your mistake in pretest 7 of problem D ?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Actually I am not sure.Looking at the diff of the two submission, they look like doing the same. So, maybe overflow?
 » 19 months ago, # |   +28 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.
 » 19 months ago, # |   +1 After participating in this round, I QUIT :(
 » 19 months ago, # |   +41 speedforces
 » 19 months ago, # |   +1 payed back more than what i got in last round.
 » 19 months ago, # |   +7 A is the hardest problem among A,B,C,D :))
 » 19 months ago, # |   +21 Goddamn A
•  » » 19 months ago, # ^ |   +1 I spent 35 mins on A, 9 mins on B and 15 mins on C... amazing round, what can I say.
•  » » 19 months ago, # ^ |   0 *Goddamn A,C,D :(
•  » » » 19 months ago, # ^ |   +3 Well, C&D were simple, just not codeforces-pypy-friendly
 » 19 months ago, # | ← Rev. 2 →   +139 MEET AN EXPRIENCED & SHAMELESS CHEATER This is how Master_Jiraya bypasses Plagiarism testing.Master_Jiraya 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 MikeMirzayanovPeople like Master_Jiraya 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++;
 » 19 months ago, # |   0 Was D easy? I had no idea how to solve D. Can anyone tell what they did
•  » » 19 months ago, # ^ |   +24 every question is easy when you have answers floating around on youtube and telegram
•  » » 19 months ago, # ^ |   +4 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.
•  » » 19 months ago, # ^ |   0 D solution: https://www.youtube.com/watch?v=kJsyu1MfwOc
 » 19 months ago, # |   +42 Dear problem setters if solution is short doesn't mean the problem is easy and should be A
 » 19 months ago, # |   +23 feels like educational round :<
•  » » 19 months ago, # ^ |   +9 It was made for 5 to 8 graders, so no suprise it feels educational.
 » 19 months ago, # |   +13 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. :DBut still, I liked the tasks! Looking forward for Editorial E and F.
 » 19 months ago, # |   0 I lost the round because of the unusual time :((((
 » 19 months ago, # | ← Rev. 2 →   0 How to solve D? Thanks.
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 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.) Spoilerll n; cin>>n; pair a[n]; for(ll i=0;i>a[i].second>>a[i].first; } sort(a,a+n); ll ans=0; for(ll i=0,j=n-1,c=0;i<=j;){ if(c>=a[i].first){ ans+=a[i].second; c+=a[i].second; a[i].second=0; i++; } else{ if(a[i].first-c>=a[j].second){ ans+=(2*a[j].second); c+=a[j].second; a[j].second=0; j--; } else{ ll d=a[i].first-c; ans+=(2*d); c+=d; a[j].second-=d; } } } cout<
•  » » 19 months ago, # ^ |   0
 » 19 months ago, # | ← Rev. 2 →   +3 Can we solve F by finding the maximum values and (n(i)-n(j)) where a[i]>=a[cur] and a[j]
 » 19 months ago, # |   +10 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 .
•  » » 19 months ago, # ^ | ← Rev. 2 →   +11 https://www.youtube.com/watch?v=xpuLhmR5rZcWondering how 1800 got it in 1 hr 57 min. Here is the guy posting solutions for last 2 contests
•  » » » 19 months ago, # ^ |   +5 They are making it hard for contestants who do all the hardwork to get +ve delta and growth, what they deserve .
•  » » » 19 months ago, # ^ |   +3 This idiot deserve IP ban
•  » » » 19 months ago, # ^ |   +3 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.
•  » » » » 19 months ago, # ^ |   +4 Sometimes I do the same thing, at first sort, then reverse, with my template it is just faster to type.
•  » » » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +3 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.
 » 19 months ago, # |   +14 Was D really that easy?
•  » » 19 months ago, # ^ |   0 I thought I will just sort the pairs but it's not that simple if I had more time it can be solved maybe
•  » » 19 months ago, # ^ |   0 I felt it was easier than your usual Div2. D
 » 19 months ago, # |   +1 Everything was going fine until I got TLE.
 » 19 months ago, # |   +5 Can someone tell why am I getting WA in B 120121669
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   +5 Ohh thanks += shouldn't be done
 » 19 months ago, # |   +4 I got destroyed after seeing this was meant for students of grade 5-8...
 » 19 months ago, # | ← Rev. 3 →   +16 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.
 » 19 months ago, # |   +6 A was tougher than B.
•  » » 19 months ago, # ^ |   +11 And tougher than C & D, I think.
 » 19 months ago, # | ← Rev. 2 →   +85 I think in Russia they don't like int they only like long long.
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   +5 The values were long long, not int.
•  » » » 19 months ago, # ^ |   0 I have used long long only
•  » » » » 19 months ago, # ^ |   +5 k,x can also be long long
•  » » » » » 19 months ago, # ^ |   +5 Oh yes. This was a terrible mistake :(
 » 19 months ago, # |   0 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;i0){ if((v[i]-v[i-1])<=2*x){ ans--; k--; } } } cout<
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » 19 months ago, # ^ |   +3 3 2 21 2 8 -->ans : 1 try this
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +1 Also got 4 TLE seemingly just because codeforces doesn't use the latest pypyIt 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
•  » » 19 months ago, # ^ |   +3 And now I have FST in C for the same reason
 » 19 months ago, # |   0 Anyone tried Top-Down approach for D?
•  » » 19 months ago, # ^ |   0 its greedy, not dp
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   +5 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 your complexity is n * q, that is 10^10, and that is hundred times 10^8
 » 19 months ago, # |   +1 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 . :/ .
 » 19 months ago, # |   +8 Contest was amazing but Why There is A problem very Annoying :( killed me
 » 19 months ago, # | ← Rev. 6 →   0 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 ll n,x,t; cin>>n>>x>>t; ll y=t/x; n--; ll ans=1; if(y%2==0) ans= (y/2)*(y+1); else ans= ((y+1)/2)*y; ll z=ans+ (n-y)*y; cout<
•  » » 19 months ago, # ^ |   +5 Check for testcases with t/x > n
•  » » 19 months ago, # ^ |   0 The number of participants can be smaller than t/x.
•  » » 19 months ago, # ^ |   0 use this test n=5 x=2 t=100
 » 19 months ago, # |   0 How to solve F? Any hint??
•  » » 19 months ago, # ^ |   +16 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
 » 19 months ago, # |   +61 Just ban cheaters accounts. It's getting out of control.
•  » » 19 months ago, # ^ |   +29 Honestly, still surprised 2k+ people were able to solve D
•  » » » 19 months ago, # ^ |   +3 And here I am, getting WA in D cause I mistakenly wrote i>0 instead of i>=0 in a for loop.
 » 19 months ago, # |   0 After sys failing C; Don't believe floating-point arithmetic.
•  » » 19 months ago, # ^ |   +3 Yeah, just never use floating point numbers unless you absolutely have to
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 why Don't you just use (x + y — 1) / y for ceil. >.<
 » 19 months ago, # |   0 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 ?
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +3 A was really interesting.Mind negetive numbers. And it's my first turn solve many problems in div2 thanks a lot!
 » 19 months ago, # |   +5 Why did C not have multiple testcases in each pretest? It has so many FSTs.
 » 19 months ago, # | ← Rev. 2 →   +4 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 codeN, K, X = map(int, r().split()) L = list(map(int, r().split())) L.sort() ans = [] for i in range(N-1): if L[i+1]- L[i] > X: ans.append((L[i+1]- L[i]-1)//X) ans.sort() cnt = 0 for i in ans: if K >= i: K -= i cnt += 1 else: break print(len(ans)+1-cnt) 
 » 19 months ago, # | ← Rev. 2 →   +5 I think TL on problem C is too tight for Pypy3. Or I was wrong?(Edit: I got TLE while system testing.) coden, k, x = mip() a = lmip() a.sort() p = [] g = 1 for i in range(1, n): di = a[i] - a[i - 1] if di > x: p.append((di - 1) // x) g += 1 p.sort() for i in p: if i > k: break k -= i g -= 1 print(g) 
•  » » 19 months ago, # ^ | ← Rev. 4 →   +4 It is not so much pypyIt is that the specific version of pypy codeforces uses is bad with numbers above int32, it isfixed in later versionsAnd both C&D (at least in my implementation) use such numbers a lotHere are more detail https://codeforces.com/blog/entry/90184
•  » » » 19 months ago, # ^ |   0 Thanks!
•  » » » 19 months ago, # ^ |   +1 I think it is pypy in this case.The same code for C: 1. PyPy3 got TLE: https://codeforces.com/contest/1539/submission/120095637 2. Python3 got AC: https://codeforces.com/contest/1539/submission/120126977
 » 19 months ago, # |   0 I thought tourist will be streaming for today's contest when he registered.
 » 19 months ago, # |   0 can someone give counter case for pretest 7 of problem D, I tried similar to solution mentioned by others above. Submission
 » 19 months ago, # |   +33 Just Python Things :) 
•  » » 19 months ago, # ^ |   +4 Lol FSTs. What just happened there? I see a lot ppl getting FST on C and D. XD
•  » » » 19 months ago, # ^ |   +2 In case of python int64 numbers which are really slow in codeforces version of pypy on windowsD should be fine if you solve it with two pointers, but gets the same problem if you use binary search like I did
•  » » » » 19 months ago, # ^ |   +2 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 :(
•  » » » » » 19 months ago, # ^ | ← Rev. 3 →   +4 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
•  » » » 19 months ago, # ^ |   +1 TLE on test 18 ╥﹏╥
•  » » » » 19 months ago, # ^ |   +1 me too
•  » » 19 months ago, # ^ |   0 Does Russian Olympiad allow Python? This might be part of the issue?
•  » » 19 months ago, # ^ |   0 What extension do you use ?
 » 19 months ago, # | ← Rev. 2 →   -16 Why this gives WA on test 37 in C I didn't expect that :( cin>>n>>k>>x; for(int i=0;i>a[i]; } sort(a,a+n); vectortmp; for(int i=1;ix) tmp.push_back(a[i]-a[i-1]); } sort(tmp.begin(),tmp.end()); int si=tmp.size(); si++; //cout<
•  » » 19 months ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » 19 months ago, # ^ |   +20 actually how the hell this passed 36 test cases
 » 19 months ago, # | ← Rev. 3 →   +4 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 :)
 » 19 months ago, # |   +4 Please give some relief in tightness of time bounds for python users. My O(n) solution for Q. C gave TLE during system testing.
•  » » 19 months ago, # ^ |   0 Hey, a couple of things. Your solution is actually nlogn, since you are sorting. 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.
 » 19 months ago, # |   +85 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.
•  » » 19 months ago, # ^ |   +16 Exactly my thoughts as well. Surprisingly, each explanation bullet for the first sample also agrees with the other interpretation of the problem xD
 » 19 months ago, # |   0 Why do I have TLE? I don't understand.120075328
•  » » 19 months ago, # ^ |   0 Too many sum operations. Google "prefix array".
•  » » » 19 months ago, # ^ |   0 I got AC with same code 120078694
•  » » » » 19 months ago, # ^ |   0 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)
 » 19 months ago, # |   +121 Feel my pain
•  » » 19 months ago, # ^ |   0 Rough day for many of us, bad contest $\implies$ good upcoming contest :)
•  » » 19 months ago, # ^ | ← Rev. 2 →   +8 YES !
 » 19 months ago, # |   -32 Short Solutions Solution Avoid solve() { ll n,i,j,k,m,x,t; cin>>n>>x>>t; m=t/x; k=(n-1)*x; ll nn=min(n,m); n-=nn; ll ans=(n*m)+(nn*(nn-1))/2; cout<>n>>q; string s; cin>>s; vector> v(n+1,vector(26)); for(i=1;i<=n;i++) { v[i] = v[i-1]; v[i][s[i-1]-'a']++; } while(q--) { ll l,r; cin>>l>>r; ll ans=0; vector v1=v[r]; vector v2=v[l-1]; for(int i=0;i<26;i++) { ans+=(i+1)*(v1[i]-v2[i]); } cout<>n>>k>>x; vector v(n); for(i=0;i>v[i]; } sov(v); priority_queue,greater> pq; ll grp=1; for(i=1;ix) { grp++; pq.push((v[i]-v[i-1]-1)/x); } } while(!pq.empty() && k>0) { auto it=pq.top(); if(k>n; vector> v(n,vector(2)); for(ll i=0;i>v[i][1]>>v[i][0]; sov(v); i=0;j=n-1; ll ans=0; ll tot=0; while(i<=j) { if(tot>=v[i][0]) { ans+=v[i][1]; tot+=v[i][1]; i++; } else { ll diff=v[i][0]-tot; ll z=min(v[j][1],diff); ans+=z*2; tot+=z; v[j][1]-=z; if(v[j][1]==0) {j--;} } } cout<
 » 19 months ago, # |   +4 Why did python O(N) TLE in C;-;Time to reject python embrace c++
•  » » 19 months ago, # ^ |   0 They should rejudge the submissions. O(n) is definitely sufficient enough for 1s Time-limit.
•  » » » 19 months ago, # ^ |   +1 python TLE on test 18 https://codeforces.com/contest/1539/submission/120107086same code C++ code AC with 93 ms https://codeforces.com/contest/1539/submission/120127276
•  » » » » 19 months ago, # ^ |   0 same, my python solution TLEd for test case 18 and it passed after adding the fast IO class. AC with Fast IO
•  » » » » » 19 months ago, # ^ |   +1 I can't belive what I just did The same code that TLE'd in a contest in pypy 3 passed in python 3python 3https://codeforces.com/contest/1539/submission/120128958pypy 3https://codeforces.com/contest/1539/submission/120107086
•  » » » » » » 19 months ago, # ^ |   0 pypy3 is suck at big integers https://codeforces.com/blog/entry/91905?#comment-806750
 » 19 months ago, # |   -49 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/23636854But 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 ?
 » 19 months ago, # |   +35 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 dv.jakhar, https://codeforces.com/contest/1539/submission/120121675 by Abhijeet007There 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.
 » 19 months ago, # |   0 greedy forces
 » 19 months ago, # |   +9 What is disappointment? spoilerWhen you are 2 lines of code away from the correct solution and time up! PS — gree-D
 » 19 months ago, # |   +1 For 1539C - Stable Groups, 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?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +11 I presume this is the reasonhttps://codeforces.com/blog/entry/90184
•  » » » 19 months ago, # ^ |   0 Thanks. Fortunately, this is not a rated competition for me.
 » 19 months ago, # |   +1 Please try to make pretests stronger. T~T. My Global rank fell from 63 to 1807, because C failed on main tests!
•  » » 19 months ago, # ^ |   0 that's the point of the pretests, they are not supposed to cover ALL testcases. They are giving meaning to hacks.
 » 19 months ago, # |   -10 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 :(
 » 19 months ago, # |   +62 To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 19 months ago, # |   0 I can't believe what I just did The same code that TLE'd in a contest in pypy 3 passed in python 3python 3https://codeforces.com/contest/1539/submission/120128958pypy 3https://codeforces.com/contest/1539/submission/120107086CAN ANYONE PLEASE EXPLAIN THIS TIA
•  » » 19 months ago, # ^ |   0 Maybe you can see this post: When is PyPy slower than Python?
 » 19 months ago, # |   -17 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I don't think so.I did that in my first submission and It showed wrong answer on pretest 3
•  » » » 19 months ago, # ^ |   0 Compare solution 1 and solution 2Only thing I changed here is k-- to k-=co[i] in the last loop.
 » 19 months ago, # |   +4 editorial please
 » 19 months ago, # | ← Rev. 2 →   0 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?
•  » » 19 months ago, # ^ |   +4 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.
 » 19 months ago, # |   +9 Pretest of problem C seems very weak (╥╯^╰╥)
 » 19 months ago, # | ← Rev. 2 →   +13 How to solve E?
 » 19 months ago, # |   0 Where is editorial?
 » 19 months ago, # |   0 For problem C, can someone please explain why the difference between two students' level is supposed to be (a[i+1]-a[i]-1) instead of straightforwardly taking (a[i+1]-a[i]). I can find some of the examples where the formula without minus 1 fails, but I can't find a reason that explains why :(
•  » » 19 months ago, # ^ |   0 There is -1 because if you won't put it then suppose a[I+1]-a[I] is 8 and X is 4 , so 8/4=2 whereas you need only one person if a[I] is 1 and a[I+1] is 9 then putting 5 in between will be sufficient.
•  » » 19 months ago, # ^ |   0 made same mistake that costed me 2 WA's and 40 mins to figure
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 If we have 2 students with 1 and 7 values and x=2 the difference =6 and it's divisible by x in this case you need two students to fill the gap it becomes 1 3 5 7 so without this -1 answer will be 3 students which is wrong
 » 19 months ago, # |   0 How to solve D using binary search?The premise was to binary search the number of "Twos" I want such that I try to get as minimum Twos as possible but my checking algorithm isn't correct, any ideas?
•  » » 19 months ago, # ^ |   +1 I solved with binary search, you can look at my submissionWell, it got TLE FST because of the pypy issues, but that's a different story
•  » » 19 months ago, # ^ |   +9 I solved it using binary search as you explained. You do search on number of items, that you will buy without discount (so for price of $2$). This bases on a simple fact: If you can buy all needed items using only $k$ purchases without discount, when you always can buy all needed items using $k_1 > k$ purchases without discount. So, the minimal $k$, such as you can buy all, buying only $k$ items without discount will yield the solution.To check inside binsearch you should firstly sort all items by their $b_i$, before search. Logic behind it is pretty intuitive, you do not want to spend $2$ bucks on items, that potentially could be unlocked with discount later, so inside binary search you firstly simulate buying $mid$ items without discount from the end of sorted list (so, buying the most hard-to-unlick items). Then you basically go from the beggining of this list, and check that for items you need and did not buy yet for 2 bucks, you have discount. If you can buy all needed items with only $mid$ undiscounted purchases, then do $r := mid$, searching for more optimal solution, else do $l := mid + 1$. After binsearch answer is $2 * k + ((\sum a_i) - k)$. Submission: 120089991
 » 19 months ago, # |   +20 https://www.youtube.com/channel/UCm-7dkk1fHId1hy5vY5VVCQ this guy is spreading live solutions.plz take serious actions
 » 19 months ago, # |   -13 I solved D in O(n) using MITM technique. You can check it out: https://codeforces.com/contest/1539/submission/120088638
 » 19 months ago, # | ← Rev. 2 →   0 Can someone please explain this to me this is the solution I had submitted for problem D during the contest and it gave TLE but after the contest I submitted the same solution with a small change in the compare function and it worked Same solution for D with change in compare function
•  » » 19 months ago, # ^ |   +11 I guess this blog should clarify the issuehttps://codeforces.com/blog/entry/70237
 » 19 months ago, # |   +3 PROBLEM A LOOKING AT QUESTION B,C,D TODAY (JUST FOR FUN)...
 » 19 months ago, # |   0 CF-DIV2D shinigami676 kriborz Mnltrix vineet_02 akhilesh.k gsamarth882 Adarsh_29 Harsh18064 there are some users 100% cheat in this contest and almost are India. Pls check and give them heavy penalty.
 » 19 months ago, # |   +2 Its my humble request to the cheaters please don't ruin the Codeforces contests by cheating , if you really want to improve do the hard work and trust me efforts never go in vain someday or the other you gonna get what you have worked for.
 » 19 months ago, # | ← Rev. 5 →   +18 Can someone help me out with F? I tried using segment trees. The idea basically is that in a given subsegement for a particular x what matters is the number: No. of elements greater than x — No. of elements less than x. this will be the sum over that subsegment if I represent a number greater than x as 1 and -1 otherwise(it get's a little more complicated when you consider equal elements but the idea is same). The code seems to be working correctly, except the fact that I am getting TLE. And given that I just do 2*n updates and 4*n queries in total I don't understand why it is so. Here's my code
•  » » 19 months ago, # ^ | ← Rev. 3 →   +30 Hey there! Try using ar instead of vt
•  » » » 19 months ago, # ^ |   +24 Oh Thanks! It worked!!!!!!
•  » » » » 19 months ago, # ^ |   +18 Did you forgot to shift to alt while answering the question yourself, or you really did that ?
•  » » » » » 19 months ago, # ^ |   +17 identity crisis ig
•  » » » » » 19 months ago, # ^ |   +38 I thought it was funny. lol
 » 19 months ago, # |   0 Why you have not published the editorial till now ch_egor?
•  » » 19 months ago, # ^ |   +6 Chill bro. Every contest doesn't get an editorial this fast.
•  » » 19 months ago, # ^ |   0 ch_egor ping
 » 19 months ago, # |   0 Waiting for editorial. Have been waiting for 5 hours already. Where. is. editorial.
 » 19 months ago, # |   0 Me, waiting for editorial........
 » 19 months ago, # |   -12 Contest was div-3 type and my performance was div-4 type
 » 19 months ago, # |   -22 Speedforces.
•  » » 19 months ago, # ^ |   -23 Also fstforces.
 » 19 months ago, # | ← Rev. 3 →   -22 Test: 5 3 10 2 12 1 11 3 10 1 8 Submission: Your text to link here...Output : 20 Correct Output: 19This submission is getting accepted but however the above test case shows wrong output. Correct Output should be 19, instead of 20._tryhard
•  » » 19 months ago, # ^ |   0 you are right bro this is my submission LOL. and I find my mistake. Thanks
 » 19 months ago, # | ← Rev. 2 →   0 Why I am getting runtime error?Anyone please tell.My submission.
•  » » 19 months ago, # ^ |   0 See the problem constraints, n can be 10^9, which is too large, results in a runtime error
•  » » » 19 months ago, # ^ |   0 That's why I have used long long int.It can take upto 10^18 as an input
•  » » » » 19 months ago, # ^ |   0 I mean size of array is arr[n] which is too large. You can see this error by declaring array of size 10^9. size can be upto 10^8
 » 19 months ago, # |   +3 Anyone has any idea if the contest has been officially deemed unrated or there's an issue with the rating? I don't see any posts about this round going unrated, and it's the first time I'd touched the Specialist tag so I really really want the round to stay rated.
•  » » 19 months ago, # ^ |   0 I guess they made it unrated because there were too many cheaters
 » 19 months ago, # |   0 Harsh18064 this user was cheated why he still rated ? MikeMirzayanov check this
•  » » 19 months ago, # ^ |   0 he 100% cheat in problem D pls skip him
 » 19 months ago, # |   0 getting tle in 'C' in testcase 61 using java, the same code works well in c++