Всем привет!
В воскресенье состоится всероссийская олимпиада школьников для 5-8 классов имени Келдыша. Удачи всем участникам! Олимпиада проходит под чутким руководством московской методической комиссии в лице GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil и, конечно, Андреевой Елены Владимировны.
Мы рады представить Codeforces Round #727 на основе задач олимпиады. Это будет Div. 2 раунд, который состоится в 20.06.2021 13:05 (Московское время). Возможно, вы уже и раньше участвовали в раундах на основе олимпиад, подготовленных московской методической коммисией (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707).
Задачи этой олимпиады были придуманы и подготовлены talant, Siberian, shishyando, Artyom123, TeaTime, Tikhon228 под координацией grphil.
Также спасибо KAN, Aleks5d и isaf27 за помощь с организацией Codeforces версии соревнования и MikeMirzayanov за системы Codeforces и Polygon.
Также хотелось бы поблагодарить компанию Tinkoff и лично Татьяну TKolinkova Колинкову за неоценимый вклад в организацию соревнования.
Желаю удачи!
UPD1: Спасибо _overrated_ и Ormlis за тестирование.
UPD2: Разбалловка: 500 — 750 — 1250 — 1500 — 2000 — 2500
UPD3: Разбор
UPD4: Победители!
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 2 only, lol
It turned out to be div-2.75 if not div-3
Div.3 combined with Div.1, more precisely.
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.
Извините за баян, но это шедевр!
Nostalgic
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)
There's a simple solution, just think of the correct/intended approach from the get-go.
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 :)
Интересно успеют ли участники Келдыша поучаствовать и тут.
Нельзя, дисквалифицируют.
Даже если и не узнают организаторы, то большого смысла в этом нет.
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.
WYSI
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
is this gonna be tough??
But after solving Problem C.
"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.
Back Story?
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 newbiesget +ive delta.An irrelevant meme.
2+(2*5)!=12????? do they different in Japan????
First, answer this.
2!=2
True or False?
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://mirror.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 thenarr[aa] = new string[b];Hope history doesn't repeat itself ಠ_ಠ Looking forward for interesting but moderate round.
problems were hard, but interesting.
aryan57 remember 707?, hehe
When you see it!!
Does anyone else's latoken rating reduced today after rating returned ?
This round https://mirror.codeforces.com/contest/1537/standings
hard div 2 :V
will this round be harder than normal div 2??
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 timing
Give 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.
No 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?
wonderful writer!!!%%%
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
Wish it be easy:(
Here we go again.
hope for no googleforces
how about cheatforces?
yes too many cheaters
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:
First time solved four questions in any div2 contest :)
Hope you solve four questions next round too
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.
*Goddamn A,C,D :(
Well, C&D were simple, just not codeforces-pypy-friendly
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 MikeMirzayanov
People 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++;
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. :D
But still, I liked the tasks! Looking forward for Editorial E and F.
https://www.youtube.com/channel/UCm-7dkk1fHId1hy5vY5VVCQ/videos
WE NEED TO STOP THIS GUY
Stop sharing it. You only make it worse
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.)
https://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 :-
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 .
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.
Can someone tell why am I getting WA in B 120121669
is in a function (
main), so it is uninitialized. After initializingx[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 done
I 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.
I think in Russia they don't like int they only like long long.
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?
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.
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.
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.
your complexity is n * q, that is 10^10, and that is hundred times 10^8
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.
Check 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
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
I think TL on problem C is too tight for Pypy3. Or I was wrong?
(Edit: I got TLE while system testing.)
It 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://mirror.codeforces.com/blog/entry/90184
Thanks!
I think it is pypy in this case.
The same code for C: 1. PyPy3 got TLE: https://mirror.codeforces.com/contest/1539/submission/120095637 2. Python3 got AC: https://mirror.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'stime 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?
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.
Correct me, if I am wrong, but why do people even try to use Python in CP? If you have even minimal knowledge of languages and how computers/compilers/interpeters work, you should understand that giving Python users higher TL is kind of giving slow cars bonus in time in racing. CP is not all about algorithms only, it is about optimizations of that algorithms as well. So why do you try it using initially unoptimized environment? Of course, it is just my opinion about such comments, feel free to discuss.
It is now an outdated idea, python users are also increasing in this field. You can check the number of python users in other platforms such as Leetcode, binarysearch.io
Well, honestly, I do not think that number of python users is somehow related to this topic. My point is that C/C++ and Python is two different languages for different tasks. If you need productivity and speed — you use C/C++, if you need very cool calculator, or some web-scrapping script, or some ML stuff — you use Python. You won't enter the Formula 1 race with larry truck, because it is for just other purposes. Also you won't submit solutions in C++ on kaggle, or do some scripting stuff with it, etc..
And also, why do people, who are trying to do CP in Python just TLE'ing almost every contest and then going straight to comment section to blame strict time limits. If you want to get better in CP, use appropiate tools.
PS. A lot of participants use python to submit A/B problems, where you need some simple not TL related stuff to code fast
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)
Feel my pain
Rough day for many of us, bad contest $$$\implies$$$ good upcoming contest :)
YES !
Short Solutions
Why 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://mirror.codeforces.com/contest/1539/submission/120107086
same code C++ code AC with 93 ms
https://mirror.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://mirror.codeforces.com/contest/1539/submission/120128958
pypy 3
https://mirror.codeforces.com/contest/1539/submission/120107086
pypy3 is suck at big integers https://mirror.codeforces.com/blog/entry/91905?#comment-806750
Problem B was easier than Problem A, the question rating should be B <A.
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 ?
Ideone Link: D solution Link Matching submissions which I have found till now: https://mirror.codeforces.com/contest/1539/submission/120121120 by Harsh18064, https://mirror.codeforces.com/contest/1539/submission/120121447 by dv.jakhar, https://mirror.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?
When you are 2 lines of code away from the correct solution and time up!
PS — gree-D
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?
I presume this is the reason
https://mirror.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 longfor 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://mirror.codeforces.com/contest/1539/submission/120128958
pypy 3
https://mirror.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.
where's the editorial? grphil
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.
Pretest of problem C seems very weak (╥╯^╰╥)
How to solve E?
Where is editorial?
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 :(
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.
made same mistake that costed me 2 WA's and 40 mins to figure
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
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?
I solved with binary search, you can look at my submission
Well, it got TLE FST because of the pypy issues, but that's a different story
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
https://www.youtube.com/channel/UCm-7dkk1fHId1hy5vY5VVCQ this guy is spreading live solutions.plz take serious actions
I solved D in O(n) using MITM technique. You can check it out: https://mirror.codeforces.com/contest/1539/submission/120088638
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
I guess this blog should clarify the issue
https://mirror.codeforces.com/blog/entry/70237
...
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.
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.
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
Hey there! Try using ar<ll,3> instead of vt
Oh Thanks! It worked!!!!!!
Did you forgot to shift to alt while answering the question yourself, or you really did that ?
identity crisis ig
I thought it was funny. lol
Why you have not published the editorial till now ch_egor?
Chill bro. Every contest doesn't get an editorial this fast.
ch_egor ping
А вот и разбор. https://drive.google.com/file/d/1jLyZYqJggeXPateMQdXNtEG3IXiAnw4n/view https://drive.google.com/file/d/1SQou7jQL2UlTPYh0xNDJU5CEtIDKTN5v/view текстовый разбор на сайте олимпиады
Если бы мне в 5 классе сказали, что в разборах есть аниме тян в юбочках, то я бы уже туриста обогнал только ради них.
Waiting for editorial. Have been waiting for 5 hours already. Where. is. editorial.
Me, waiting for editorial
........
Speedforces.
Also fstforces.
Test:
Submission: Your text to link here...
Output : 20 Correct Output: 19
This submission is getting accepted but however the above test case shows wrong output. Correct Output should be 19, instead of 20.
talant
you are right bro this is my submission LOL. and I find my mistake. Thanks
Why I am getting runtime error?Anyone please tell.
My submission.
See the problem constraints,
ncan be 10^9, which is too large, results in a runtime errorThat's why I have used long long int.It can take upto 10^18 as an input
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
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.
I guess they made it unrated because there were too many cheaters
Harsh18064 this user was cheated why he still rated ? MikeMirzayanov check this
he 100% cheat in problem D pls skip him
getting tle in 'C' in testcase 61 using java, the same code works well in c++