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:

Div. 1 + Div. 2:

uh oh, another russian middle school olympiad

Yet another $$$Div$$$ $$$1.5$$$ round

just gave a div 2.5, its time for payback xd

Your account name said it all ROFL.

Finally, it was

Div 2only, lolIt turned out to be div-2.75 if not div-3

Div.3 combined with Div.1, more precisely.

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

RIP brain of upvoters!

WYSI

WYSI

WYSI

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

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

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

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

NostalgicAfter 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)

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

Note the unusual time

The scariest rounds on CF.

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

That explains it all :)

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

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

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

Aireu from osu must see this contest.

MemeWYSI

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

the_nightmare

As a setter I hope you will enjoy our problems!

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 ).

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:)

it was a good question that reminded you to check constraints

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

It was a Good Problem with pigeonhole principle.

Don't get Dijkstracted. :)

TeaTime orz

Relatable afis this gonna be tough??

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 .

But after solving Problem C.

Sus

meme"Huee Huee Hueee"

LoL how to break this loop bruuhh !!

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

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.

ahh, humour based on my pain :')

All circular array problems be like.

Back Story?

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

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 >.<

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

:Danger:

I hope I am wrong though and everyone

~~except pupils and newbies~~get +ive delta.An irrelevant meme.

2+(2*5)!=12????? do they different in Japan????

First, answer this.

2!=2

True or False?

True.that is false. Right?

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

Round 657 was arguably the hardest round of last year.

How many question will be there??

Please HELP!!

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

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];`

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

problems were hard, but interesting.

When you see it!!

Does anyone else's latoken rating reduced today after rating returned ?

This round https://codeforces.com/contest/1537/standings

hard div 2 :V

will this round be harder than normal div 2??

Yep,it's equivalent to div 1.5

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

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

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

Do russian kids know about video games?

Some of them are video games creators.

I still have nightmares from 657No scoring distribution for this round!?

Score distribution?

There will be six problems with following scoring distribution.

1500 2000 2500 3000 3500 $$${\displaystyle \infty }$$$RIP to my ratings in Advance , I got green in last round.

What about score distribution?

Time to get my ratings higher downwards again!

A, B -->> AcceptedHope all these positive ratings of this round's announcement should not convert into negatives after the contest.

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

1500,3500,3500,3500,3500.

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

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

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

There can be subtasks too

obviously I am not gonna create every letter number combination

To estimate difficulties of problems.

Why would you need that?

For cheating purposes.

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

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

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

Wish it be easy:(

Here we go again.

hope for no googleforces

how about cheatforces?

yes too many cheaters

10 minutes to go!

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

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

you can use CF predictor!

WYSI

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

Nightmare Round

Is it possible to get register now?

Participate virtually. Anyways Only 40 mins are left Now

Completed three problems offline that's why asking for registration.

Nothing cant be done now

Huuuuuge gap between D and E,F

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

tourist giving div 2 round very rare

tourist missing Russian Olympiad based contests is even rarer (check past rounds)

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

How to solve A? Please reply once contest ends

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

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?

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

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?

First time solved four questions in any div2 contest :)

Hope you solve four questions next round too

Thank you!

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.

You can add more than 1 student in between

fuck my life :(

Hoping the pretests for D are strong.

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

give you a test: 2 1 2000000000. I hack myself use this test.

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.

And to me A was much harder than D xD

I was able to solve A easily but got struck in D :). Can you give some ideas for solving D?

If we can buy products for price 1 we do. Else we buy some items of the product with max(b[i]).

Buy the products with higher bi until you reach level of lowest bi

I tried similar solution. Could you please tell my mistake. Submission

Problem D: https://www.youtube.com/watch?v=kJsyu1MfwOc

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.

What was your mistake in pretest 7 of problem D ?

Actually I am not sure.

Looking at the diff of the two submission, they look like doing the same. So, maybe overflow?

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.

After participating in this round, I QUIT :(

speedforces

payed back more than what i got in last round.

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

Goddamn A

I spent 35 mins on A, 9 mins on B and 15 mins on C... amazing round, what can I say.

A looks so innocence, but after you start solving it...

*Goddamn A,C,D :(

Well, C&D were simple, just not codeforces-pypy-friendly

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

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

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++;

Didn't get how is he cheating?

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

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

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

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.

D solution: https://www.youtube.com/watch?v=kJsyu1MfwOc

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

feels like educational round :<

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

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 EandF.I lost the round because of the unusual time :((((

How to solve D? Thanks.

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.)

Spoilerhttps://www.youtube.com/watch?v=kJsyu1MfwOc

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?

For problem

D:-ACsubmission in1hour 57 min--->1800ACsubmission inlast 3 min--->300+All due to legends like this shivam.utube23

He is one of many others .

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

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

This idiot deserve IP ban

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.

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

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.

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.

Was D really that easy?

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

I felt it was easier than your usual Div2. D

Everything was going fine until I got TLE.

Ikr, I was stuck in B pretest 4.

yup

Can someone tell why am I getting WA in B 120121669

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

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.Ohh thanks

+=shouldn't be doneI got destroyed after seeing this was meant for students of grade 5-8...

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.

A was tougher than B.

And tougher than C & D, I think.

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

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.

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

I think in Russia they don't like

intthey only likelong long.Scoring distribution is wrong.It should be 1000-1250....and so,on

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

The values were long long, not int.

I have used long long only

k,x can also be long long

Oh yes. This was a terrible mistake :(

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

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

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.

You can add multiple students between elements.

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

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.

Got it!!! Thanks.

3 2 2

1 2 8 -->ans : 1 try this

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.

Yeah, I got it, AC now 120125882 Thanks.

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

And now I have FST in C for the same reason

Anyone tried Top-Down approach for D?

its greedy, not dp

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

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.

Ya, I got it thanks man

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

Sorry, my bad.

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

Can you plz. explain more briefly problem A

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 . :/ .

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

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 SolutionCheck for testcases with t/x > n

The number of participants can be smaller than t/x.

use this test n=5 x=2 t=100

How to solve F? Any hint??

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

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

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

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

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

Yeah, just never use floating point numbers unless you absolutely have to

This thing has ruined many contests

why Don't you just use (x + y — 1) / y for ceil. >.<

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 ?

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.

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

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

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

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

(Edit: I got TLE while system testing.)

codeIt is not so much pypy

It is that the specific version of pypy codeforces uses is bad with numbers above int32, it isfixed in later versions

And both C&D (at least in my implementation) use such numbers a lot

Here are more detail https://codeforces.com/blog/entry/90184

Thanks!

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

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

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

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

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

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 :(

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

TLE on test 18 ╥﹏╥

me too

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

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

What extension do you use ?

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

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.

actually how the hell this passed 36 test cases

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 :)

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

Hey, a couple of things.

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.

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

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

120075328

Too many sum operations. Google "prefix array".

I got AC with same code 120078694

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)

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(?))

Feel my pain

Rough day for many of us, bad contest $$$\implies$$$ good upcoming contest :)

YES !

Short Solutions

Solution ASolution BSolution CSolution DWhy did python O(N) TLE in C

;-;

Time to reject python embrace c++

They should rejudge the submissions. O(n) is definitely sufficient enough for 1s Time-limit.

python TLE on test 18

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

same code C++ code AC with 93 ms

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

same, my python solution TLEd for test case 18 and it passed after adding the fast IO class. AC with Fast IO

I can't belive 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

pypy3 is suck at big integers https://codeforces.com/blog/entry/91905?#comment-806750

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 ?

i goofed up!

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.

greedy forces

What is disappointment?

spoilerWhen you are 2 lines of code away from the correct solution and time up!

PS — gree-D

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?

I presume this is the reason

https://codeforces.com/blog/entry/90184

Thanks. Fortunately, this is not a rated competition for me.

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

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

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 :(To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Maybe you can see this post: When is PyPy slower than Python?

;(

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.

I don't think so.I did that in my first submission and It showed wrong answer on pretest 3

Compare solution 1 and solution 2

Only thing I changed here is k-- to k-=co[i] in the last loop.

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

editorial please

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?

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.

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.

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

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

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

How to solve E?

Where is editorial?