Всем привет!
В воскресенье состоится всероссийская олимпиада школьников для 5-8 классов имени Келдыша. Удачи всем участникам! Олимпиада проходит под чутким руководством московской методической комиссии в лице GlebsHP, ch_egor, Endagorion, vintage_Vlad_Makeev, Zlobober, meshanya, cdkrot, voidmax, grphil и, конечно, Андреевой Елены Владимировны.
Мы рады представить Codeforces Round #657 (Vintage Codeforces Round #3) на основе задач олимпиады. Это будет Div. 2 раунд, который состоится в 19.07.2020 12:00 (Московское время). Возможно, вы уже и раньше участвовали в раундах на основе олимпиад, подготовленных московской методической коммисией (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626), а также винтажных раундах (раунды 626 и 628).
Задачи этой олимпиады были придуманы и подготовлены DebNatkh, grphil, KiKoS, voidmax, I_love_myself, 300iq, isaf27 под координацией grphil.
Также спасибо ch_egor, vintage_Vlad_Makeev и meshanya за помощь с организацией Codeforces версии соревнования и MikeMirzayanov за системы Codeforces и Polygon.
Также хотелось бы поблагодарить компанию Tinkoff и лично Татьяну TKolinkova Колинкову за неоценимый вклад в организацию соревнования.
Желаю удачи!
UPD1: Разбалловка: 500 — 750 — 1250 — 1500 — 2500 — (1500 + 1500)
UPD2: Разбор
UPD3: Победители!
Div. 2:
Div. 1 + Div. 2:
Number of problems?
[Deleted]
[Deleted]
You can not call it back , until it finish !
I am excited to see problems of Russian olympiad
Now after seeing them, u should be depressed.
yes I am depressed
А чем отличаются винтажные раунды от обычных? Это просто какой-то сложный мем?)
.
[DELETED]
.
The last time I saw these many reds was when I witnessed an accident.
What are vintage rounds?
I think those rounds in which vintage_Vlad_Makeev is involved.
I don't know what's a vintage round,but it's definitely not a round in which vintage_Vlad_Makeev is involved . (This round for example)
Can I be BLUE....
not with the HARDEST div.2 ever.
Atleast for me it was the hardest.
Уже соскучился по рейтинговым раундам)) Держу кулачки, чтобы все получилось))
Пожелайте мне удачи на Келдыше
No offence to anyone
So true!
Damn true. Even the school kids will solve till F and we would be struggling with C and D XD
Well I take offense
I wanted to hack Google Headquarters in my first semester.
Some big aim you had in your first year! Most desi Indians only think about hacking Facebook when starting in CS :P
And some opt cse only for this aim :)
Our education system needs improvement, If I would have started coding from my 5th grade then I think I would have been red coder till now, and I beleve its true for all Indians.
Nah ! If i ask a random 5th grade Indian student to start cp ,he/she would not be even be excited or motivated about it. Exceptions do exist but i am talking with respect to general population . I was more interested in playing football and cricket at that age .
but what they taught in schools can be changed to what we want to be taught depending upon your interests which will eventually help us in future
Even I was more interested in playing cricket, but I do wonder if I got introduced to CP I may have latched on to it because I had a good interest in maths and aptitude at that age and also CP has a gaming front to it with all the rankings and points, you just need a given the proper introduction and some good peers to compete with :)
True Indian education system sucks
Yeah many of us feel the same, but no probs curently CP is rapidly evolving in India. India will have good number of GM's after a decade or so. And we need to create awareness about CP for a 5th grade student.
I remember learning paint in 5th grade in school lol
If coding from (5th grade -> today) = red coder then coding from (today -> today + 10 years) = red coder too. On top of that at this stage one will need much lesser time maybe 4-5 good years is enough.
The same happens in Peru, but with the 5th semester students. From the 1st to 4th semester they just use microsoft excel.
I wanted to code when I was a kid but didn't know where to start
Logged in, only to upvote you.
Our tradition is to memorize maths to pass exams.
Would gladly take this over 70 years of communism.
So hard to accept our education system
you can't blame it on education system ..... NO
If this contest was for 5-8 grade students, I feel like I am a new born baby.
Can feel this bro :')
Schools are like:
Taught in Class: Div2 A
Solved for practice: Div2 B
Homework: Div2 C
Exams: Div2 D,E,F
credits: adzo261
copied from Here ?
why is that unusual time ?
Because problems took from olympiad and for prevent leaking it, round will be in the same time as olympiad
tks :))
me in 8th grader : tell my friend to open page 69th of biology book where there is a picture of penis anatomy
russians 8th grader : solve div2 problems
Will the round be rated ch_egor? Asking because its not stated in the blog post:)
See the last word!!!
great !! we have 300iq now ... I am excited !!
Wow! Even einstein had 160. CF must be proud to have you guys :p
I've got 204.
I'm really surprised you don't have 420, that's not that far away.
"People who boasts about IQ are losers"
(f + f)iq = 204iq. It was just a joke :)
I would have upvoted you if you've said 255iq (ffiq)
Explain. I'm actually dumb.
ff in hex to decimal == 255
Now I see why I failed to solve even a single problem today.
same
That's a lot of red handles
Too many...
https://imgur.com/a/Awy9IQJ
Nice catch
Why are there so many down-voted comments in this blog?
(Notice the unusual timing)
I think people should think before voting because even the comments which are not at all negative are downvoted heavily.
I think people downvote it for fun...lol
we will b enjoying this contest
This is 5 AM in America where I live
Considering the lockdown, does the time even mean anything anymore?
Yes, there's something called body clock, which when affected can cause various health problems
Hmmm Point
Score Distribution?
....
cook off bro!!!
Any reason why start time is 09:00 UTC, but not 09:05
Probably because it's going to be held in parallel with All-Russian olympiad. Also to avoid clash with Topcoder and Codechef rounds.
Hope the problem statements are clear and interesting xD
How many problems and Score Distribution?
Unfortunately, the last 6 months we have seen this instead of the exciting confrontation between tourist and jqdai0815 :)
Nice!!!
Rating: users participated in recent 6 monthsSince his last contest was on Feb 17, either he'll take part in another contest or disappear from the global rating in a month.
At least he's visiting the site which means he is still alive. :)
Never mind. :)
What's the Score Distribution? ch_egor
No Score Distribution and No. of Problems yet? ch_egor
where scoring distribution and number of problems will be published?? ch_egor
ch_egor ping
ch_egor ping
ch_egor ping
ch_egor ping
ch_egor ping
ch_egor ping
ch_egor ping
ch_egor ping
lmao. That is some ratism right there.
exit(0)
I like to think this was a game of Russian Roulette and this guy just got killed. RIP
everyone except him who replied had something to do with the round
tester/coordinator/psetter
There will be 5 problems
Noo !! It's 6 distinct problems :/ lier !!
Scoring distribution says it's gonna be SpeedForces.
You were totally right.
This aged well.
the first round during my summer vacation lol
I'm sure some people will join 5 minutes late thinking that round will start at 14:35 IST. :v
Is this Div1?
Seems so! Not able to TOUCH a question!!
I think we really need the help of pavan putra hanuman to solve the questions in this contest Xd.
There has been a small typo guys.. it is a Div 1 round..
one hand pushups were easier for me than this round's problems!
I've never seen such DIV 2 contest.
I guess this is what "vintage" rounds are :-P
Now I get why Russians dominate in competitive programming. :)
This is for 5th-8th grades?? OKK
I wasn't able to enter codeforces for almost 20 minutes. Anyone else facing the same issue?
I entered code forces but couldn't think what to do for the past 40 minutes. Anyone facing this same issue??
Good that you didnt enter brother! God saved you from a heart attack!
Yea me too
5-8 graders solve this?? Srsly??
Should have rather rushed Bombsite B. On a serious note, is this really what 7th Grade Russians study? That is really impressive, no wonder Russians are such good coders.
Great div1 round!!!!!!!!!
2 minutes silence for all those who were too eager for the round to be rated.
__now__or__never__ broh feelings...? :D
After walking through first 3 question:
How to unregister???
Will be waiting for this ninja technique
Same ..
OK now I'm looking forward to the editorial after the contest.
I'm feeling numb :( Is it a
Div.2round orDiv.1Round?Round by Red round for Red . Screaming Red.
Lul bruh, I have the exact same pattern of submissions, except I'll become specialist by today evening.
This is meant for students of grades 5-8? Wow.
worst div2 i ever seen !!
upd: I said worst cause its seems more div1 than div2 but named div2.
*Hardest
so more room to learn :P
I am proud that I have participated in Div 1 round.
I was getting 504 server error during first 20 minutes. I am feeling blessed.
Are you the lucky one?
I was having the same issue for a very long time. I think this happened with many people and not just a few of us. There were more than 15k people who registered and on the scoreboard there are only 8000 who have attempted a single problem.
I think this could have been because it was very early morning in the US, so lots registered but not many woke up that early.
You can always use these lightweight websites m1.codeforces.com m2.codeforces.com m3.codeforces.com in such trouble of server in my case these websites work almost everytime in a live contest.
glad to hear it wasn't only me xD
I was afraid I was the only one
feels like DIV1 to me
New technique to manage server load.
This is Div 1 :(
Are you trying to kill those poor 5-8 graders ?
They might have completed the problemset by now. Russian kids are seriously genious.
No wonder why tourist is so perfect.
is there any way to undo submission?
Ah, it was good that my connection was lost during the first 30 minutes.
When you realize that this was actually a Div. 1 contest
Hell lot difficult contest!
Was this div 2? this was Div 1 ! Even more difficult , Div 0 maybe
div -2147483648
I registered for the contest, I planned to participate in it, but I slept and couldn't wakeup on time. I was feeling bad but then i read the problems and number of submissions. Thank god, i didn't wake up on time! xD
You miss 100 percent of the shots you don't take.
why there is no extra registration?
so that no one else falls into this trap
this is my first ever contest....I havent even solved a single question
Don't worry, its my 21st, and even I couldn't solve a single problem.
Can I see how many problems those 5th-8th graders solved? Might be a motivation for me or myth buster for many!!
Sure you can! Check this!
How long was the real round?
4 hours, we had problems from B to F.
Before reading the comments I thought I don't deserve to be yellow on CF...
The the last four div2 contests (excluding the Global round):
654 — widely disliked
655 — good set but queueforces
91Edu — good set but major crash
657 — Mere mortals can't solve more than 2
(I agree I'm not of high enough calibre to say all of this but damn it a man needs to vent — I've been at 1750 for 10 contests and I couldn't solve a single one — damn pretests 2)
Try to concentrate more on developing problem solving skills than on rating.
Finally, I found you another expert, that did 0. And you have a much higher rating than me. I am sorry but I feel better now. ;_;
A hint : abacab*bacaba needs to Output "NO"
Woops, wrong person, sorry.
can u translate it for us who doesn't know the language?
My son was in 8 grade, Now I don't have a son...
ROFL
So much implementation :(
Div 0 round
What is wrong with my A:87342260
1 11 abac???caba, answer should be no as they want "abacaba" exactly once
You are right, Thanks for the test. Does that mean that I just need to add some cases to my code? Or I will code another solution
What is the third testcase for C?
It's a record. First time 20k participant in div — 1 round.
Yet only 8000 dared to submit. Salute to those!
*F for those!
Exactly XD.
New technique to manage server Load
Haha! :D
Discovered by Anton and team
How to solve C?
We will only buy more than one flowers of only one type iterate to choose this and greedily take other flowers who have ai >= chosen bi
I tried to do like this but it hasn't worked(
I tried similar approach but couldn't get past test 5. What did you fix to pass that?
I didn't consider if no ai > chosen b
I did that too at the end, still failed :( Guess something is wrong with my implementation. Thanks.
Oh I found my mistake, I didn't handle this case: Number of Ai >= b is already >= n, in that case, I shouldn't take this b.
my idea was similar but I implemented it wrongly I guess. Thanks for replying.
I did the same and got WA2 T_T
Probably it was the hardest was the A ever
I don't see why is it rated for me when I'm clearly not a div1 participant
any hint for problem C !
you knew that you should take a[i] at least once to take b[i]. so, first sort all array A, then if we take a[i] once, then we have two options in the next step. take a[i + 1] or (b[i] for all remaining flowers), so think where you will know that you will take b[i] for all remaining flowers. i think this enough as hint. if u wanna more hint or there is anything ambiguous , tell me.
What's tc18 for F1?
It is kind of funny I visit the CF blogs comment section to see memes.
this contest is for grade 5 to 8,OMG i can only imagine level of Russian kids
Are you still a kid or it's just the old dp?
It wouldn't be a surprise if he actually turns out to be an 8th grader
no offence :P
Winning ICPC world finals in 6th and 7th grade :orz:
Problem A is not as easy as I though, it actually requires more implementation than usual :)
How to solve C? I tried a greedy strategy but it is not always optimal, and I believe fixing it would require m^2.
Why greedy is not always optimal?
I think it is something related to convex hull optimization technique.
I don't think so! I believe, greedy will work! Even though, I couldn't reach up to a correct solution.
Notice that you will only take b_i of one type in the entire process (if you could improve the answer by taking another b_k, you would just take all b_k as it would be better), and that it is optimal to take all a_j >= to this b_i before taking it and that you must take a_i before you can take b_i.
Now you can just iterate over b_i in descending order and do something like two pointer to keep track of the sum of a_j >= b_i taken while maintaining a used array to see if you've taken a_i already when taking b_i, so answer will be max of (asum till now + (n — a_taken) * b[i]), minus b[i] plus a[i] if we haven't used it yet.
I tried same thing. But, might have missed out something in the implementation! :(
Did you clear the used array? I got 2 WAs and wasted 10-15 mins thanks to that
Actually, I used 2 PQ's to implement this. Maybe, I missed something in the casework.
Ahh I see. I tried to implement it backwards (iterate over all a_i in descending order and find the best candidate for b, which I thought was O(1) since you can keep track of the max b already taken and not already taken, but the max is not always optimal. Nice solution!
It seems Div1 round for Div2 participants. Too Hard! ToT
Counter case for taking times modulo m / 2 (and ignoring hours), sorting and finding largest range with distance of max m / 2 — k using two pointer in D?
I kind of did the same thing. My solution was failing on this-
4 24 4 2
16 0
17 1
18 2
19 3
Try this
"Wrong answer on pretest 2"
5 words which summarize the contest
Seems like old codeforces rounds are back. Kudos to the author , Nice educational problemset. I hope more of such rounds which teaches how to solve real algorithmic problems in future, A B C were absolutely fabulous and not as per the score given to them , B is much more worthy than 1000 also. Again Thank You for such a brilliant round.<3
Yes true many people will complain about how bad the round was just because it was hard but the truth is it was really educational as even the implementation was hard and required debugging skills and the problems logic was also good.
Specialists are dumb
Please have a look at my graph before making assumption :P
yeaheverybody is crying but it was quite a challenging round and a nice change
Should I register for next DIV2 round or not?
Never fear for ratings always assume that they are a sideffect of Leaninig. If losing rating hurts you then also its normal try not looking at standings during the contest and also not at all look at your colour, just believe that giving contest and one like this is making you a learn something new, everyday. and also training you on what you already have learnt. Especially do all those contests given in a list combined in the announcement above. These are some of nowadays rare contest problemsets and amazing. Once again do register and solve problems for fun.
My First Div 1 contest done !! -_-
Can someone give a hint for D? Is it a ternary search?
can anyone tell me what is wrong in this solution?? https://ideone.com/rajqqD. This solution is for Acacius and String.
Buddy submissions won't be visible for 1st hour after the contest(check the announcement) better paste your formatted code here
All these comments and the round is still running? seriously guys!!!
what?
I think people didn't have anything else to do.
OK I understand the problems were harder than usual ( and much more interesting :D ) but admins should shout down comments during the contest, what if someone talks about his solution for one of the problems!!!
[Delete]
How to solve B?
Nvm
Didn't understand the statement completely
You can't get 2 if l > 2
But what if l > 2, than a cannot be 2, because a >= l
but l is not always 2 so, we can not fix a = 2 always
My bad
I didn't read the problem statement carefully
Fix a and then try to find b, c.
did same still WA.
Actually you should check for both $$$rem = m$$$ % $$$a$$$ and $$$rem = (m + a - 1)$$$ % $$$a$$$
You have $$$n*a + b - c = m => n*a = m + x$$$ where $$$ x = c-b $$$ and $$$ m+x \in [-maxr+m,m+maxr]$$$ where $$$maxr = r-l$$$ Iterate over a and do a binary search over $$$n$$$ and check if $$$n*a \in [-maxr+m,m+maxr]$$$
So if you have $$$n$$$ and $$$a$$$ you can simply fix $$$b = l$$$ and calculate $$$c$$$.
No need for binary search, just find closest values to m you can get by taking positive amounts of a using division.
Thanks for the great contest.
Too difficult for me...fighting!!!!
For problem D, I think the hour value of trains wasn't necessary.
Was it supposed to be solved by iterating on all "minute" values of trains as a candidate of $$$t$$$ and then finding how many minute values intersect the range $$$[t-k+1, t-1]$$$?
Ofcourse, this will have few cases to consider like $$$k=1$$$ or $$$t<k$$$ but was this the overall idea for D?
is it just me?? the codeforces were saying "can't connect right now" by the time contest was starting and after 5 or so minutes later it started. I submitted my C problem solution before 2 minutes but it keeps loading and loading after the contest I checked whether it submitted or not. But it wasn't submitted?
People before contest were asking — how many problems? Meanwhile ch_egor to himself : Actually there are two problems.
How to solve C ? is there a greedy approach to it?
optimal flowers choice is to take some flowers only once, and then take one flower and put it to the rest of the slots in bouquet.
you have to iterate through that flower which is gonna be put to the rest of the slots and update the answer.
Can anyone from Russia covert 5-8 grades to the equivalent level of American or Indian Education system, or at least tell me students of what age group study in Grade 5-8 in Russia?
12-15 years old
13-15 y.o.
Problem B seems easier than Problem A.
it just seems so DDD:
I misread the contest as DIV-2 and registered it. I didn't knew it was DIV-1
why my B solution is wrong?
...
There are some cases that n*a have to be above m
In this case for example
7 8 13
the answer will be
7 7 8 , where n = 2 and 2 * 7 > 13
and the m%i method won't work for these cases.
try this test case if you are getting WA on pretest 2, problem A.
My code says "NO", and I was still getting WA on pretest 2
Try this test case for problem A
1
11
???????caba
Yes ddddabacaba
Is the output. I did consider the fact that changing from start and end can have different effects, So I checked in both.
Thanks for the test, but what is the true solution?
super difficult problem sets, but it was very interesting!
implementation-heavy round...
How is the answer for the 2nd test case in problem C is 16.Shouldn't it be (5+4+5+4+5)=23
you can choose 5,4,3 only once according to the question
Where it was written in the problem that we can choose those values exactly once.I thought that whenever we switch from one flower to other flower then we can use the ai and whenever we use the same flower consecutively then only bi comes into account or I understood the problem wrong?
try reading these lines from ques again
_ He knows that after receiving the first flower of the i-th type happiness of his wife increases by ai and after receiving each consecutive flower of this type her happiness increases by bi. That is, if among the chosen flowers there are xi>0 flowers of type i, his wife gets ai+(xi−1)⋅bi additional happiness (and if there are no flowers of type i, she gets nothing for this particular type)._
Ok I got it. I was confused by the consecutive part. Thought the value bi is added only when we take same number of flowers consecutively,that lead to the confusion of ai part.
[Deleted]
Where i can get Russian students Textbook for Computer , Maths (class 5 — 8th) in English . How they prepare , any resource which they use ?? Please tell , (currently i am in university , but was unable to solve this contest).
There are lots of people (me included), who find the problems to be too hard for Div2 round. Please don't be so dissatisfied about it, because:
Rating. The problems were harder for everybody. Everybody solved less problems than they expected to, and the rating changes will be generally the same.
It's ok to solve 0 problems in this round. It's not because you're bad, it's because the round is hard! Remember to check editorials and solve some of the problems after the round ends!
First time absolutely sure before System Tests that my solutions wouldn't fail because they didn't get accepted in the first place.
I feel injured
Anyone solved C using Priority_Queue?? what approach you used to solve Problem C
[Deleted]
can use sweep line on Problem D. But I have no time to implement it.
For E, is there a more efficient construction than:
I believe this should work for $$$2k + 3 \leq n$$$, but I'm not super sure...
I solved E with this technique, but there is a special case: if n =9 and k=2, then the answer is NO.
In Problem B. :(
In all problems :((((((
One word to describe today's contest for me — CHAOS.
I request Codeforces to make it unrated for those , who were not able to solve even single problem . I never thought a contest for 5-8th grade student will be so much tough .
Very interesting idea. Also good idea is to make it unrated for people who are losing rating.
You don't know how stressfull it was, and now predictor says imma get 93 rating increase. so i would never want it go unrated.
How to solve B ?? looked easy but was not.
My approach : I iterated from l to r and took the modulas and checked
for m % i != 0 is l + (i — m % i) <= r.
for m % i == 0 just print i
but this approach is wrong can anyone explain why ??
CHoose a particular value of i between l to r as a and binary search from 1 to m for n. and choose any feasible numbers n,b,c which satisfy the equation. n*a+b-c=m
Test case for A: abacab?bacaba -> NO abac?b?bacaba -> YES -> abaczbabacaba
I couldn't access the codeforces site the moment this contest started and I can access again after the contest has ended. I had to use vpn to give the contest. Did something like this happen with anyone? Also, any solution?
Same. Just use m1.codeforces
They should at least give a warning for such a contest.
But they thought we were as good as the Russians kids DD:
A historic moment! Everyone including the newbies were allowed to get a feel of DIV-1 contest :P
In problem D, what was the point of printing the indices of cancelled freight trains too? We are already printing minimum cancellations and the optimal starting time.
Test case for A: 1. abacab?bacaba -> NO 2. abac?b?bacaba -> YES -> abaczbabacaba
i solved prob A just 20 minutes and prob B 3 minutes before contest ended, there was some corner cases that i did't come up with during that time, in my opinion i really like this round, great problemsets with non-trivial test cases, reminds me of how airheaded i am
What is the counter for the following approach in D. Find the time intervals for each train where it will be skipped because of passenger trams. Then do something similar to prefix sums and find the time where minimum trains will be skipped.
The intervals follows a certain sequence for each time so they can be calculated.
Not to offend anyone, but keep in mind that the mere fact that tasks for 5-8 grade students are hard doesn't imply they're really good at CP. Measure the skills of participants by the number of problems solved, not by the hardness of the problems prepared by organizers.
me:
if a participant make no submission in a round, round will be unrated for him/his ?
Yes, he/she will not be in the standing if he/she don't make submissions
Damn, I wish I knew this
Better read B before submitting A.
My video Solution For Problem A And Problem B. Hope you like it
Such a difficult div 2!
Do the students have a competition of 2 hours, as long as we do? That's terrible.
Besides, how old are students of 5-8 grades in Russia? They are so awesome to solve these difficult problems!
10-14 years old
My First Div 1 contest done !!
8776-4593= 4183 participants(including me) can't solve a single problem! :((
There were 20,000 registrations, so about 16,000 people (including me).
Oh, you are right, I not include participants who make no submission :(
Note that there are a lot of people not submitting at all if they do not like the problems. Even if they are able to solve some.
Div2 spirit revived!!! Kudos to problem-setters
My First Div 1 contest done !!
30 minutes more for such implementation heavy round would have helped :( nice problem set tho
I think it was a hardest A problem in Div.2 among the things I saw
Can anyone share their code for C. and explain if possible..
Solution C:
Every type of flower has two values of happiness A and B, the main hint was that B value of happiness will only be used from a single type or we can say that value of B if needed will be taken from a single type of flower. Now we will loop for all m types and for every type we would check no of happiness of A-type which is greater than current B. So to take a B from a particular type of flower we would first use all the A-type happiness which are more than current B and for remaining(if any) we would use current A + (B * rem)-happiness. And looping over all flowers we can find the max ans.
Codeforces Be Like:
Maybe there are many "wrong answer on pretest 2" and more submissions XD
"This Sunday will take place All-Russian olympiad for students of 5-8 grades"
5-8 grade students :
I wish i could upvote it more than once. xDD
Well I am a student of grade 7 in China and I solve 3 problems in this contest.I think the problem is not too hard and it's suit for grade 5-7 if the contest get longer.The problems have some details but it does'n need too much algorithm knowledge XD
All in all it's still a div 1.9 contest lol
orz. When I was in your age, I was playing mud.
Next time I see a Russian 5th grader, I'm running away.
I'm in 7th semester. Thinking of taking admission in grade 4. :-(
i got my mistake we need to count substring after doing changes not before 1 13 abacab?bacaba
I guess you did not have to be 2100+ to be in a Div1 contest! :-P
Fastest system testing ever xD
I was about to say contest was tough but then I remember,
After how much time will the problems be uploaded in problemset?
Hello low rating
First time (after the initial struggling days) when I couldn't solve a single problem. Also, what do they teach 5-8 grade students in Russia? I'm very curious....
Loved the round. No speedforces, queueforces or mathforces. Strong pretests and interesting A (which is rare :p). Thankyou so much for this round.
PS : Missed getting to master due to WA's. Let's hope next round marks the day I become orange.
what was interesting in A? It was only implementation.
Did you mean:
Bad round. No logic. Just implement like a brainless robot and handle all corner cases. That is basically A,B in today's round.
This was a just a normal round with a bit heavier implementation. A and B's are never that special so I don't really get why are you upset.
I am not upset. But that round is not supposed to be for Div 2 xD. It is something similar to Div 1.5
Just curious what are the corner cases for A? I did a fairly brute force implementation and there's not a single corner case. Same goes for B.
Weak pretest for B.
People after doing 1 question in this contest:
"pRobLeMsEt waS gReAt"
"tHaNks tO aUthERs"
"rAtInG dOEs nOt mAtTer"
"i aM gOnNA bE lEgUnDAirY gRaNDmAsTeR"
what we learned from this round: don't participate in rounds based on Olympiad :(
These Russians man! Flashbacks of Irodov failures was back today . Couldn't solve a single problem :')
I think Codeforces was making up for some previous easy div2 rounds.
Or it just wants the community to see the power of Russian 5-8 graders.
This contest is too damn hard for Div.2, and the problem setter is shaco.
this contest suggests the best way to reduce the load on cf servers.
only 8k participants attempted the first problem out of 17k.
and almost 3700 got it submitted correctly amazing stuff.
If you get WA on pretest 3 of Problem D, you can compare the submissions 87347894 and 87328303 to get the idea. :(
Codeforces Round #657 (Div. 2, based on All-Russian olympiad in the name of Keldysh)Codeforces Round #657 (Div. 1, based on All-Russian olympiad in the name of tourist)
Is this contest really made for students of grade 5-8 in Russia ??? I am a final year UG in India and yet unable to solve even 2 problems on time. If those children solved more than that then "Unhe 21 topo ki salami"!!!
The Russian education system is praiseworthy truly! kids of 5-8th grade are solving these! Here in Bangladesh the education system must be changed like them too.
Can anyone tell whether the logic for D is correct?.
Will first take all n flowers of one type (Let's call it good). Then try to inc the answer by taking other flowers.
To find the good flower I chose the one with maximum value of a+(n-1)*b. Then I maintain priority queue containing the other candidate flowers ('a' if it is used for the first time and 'b' if not). If I can increase my answer by decreasing the count of good flower and choosing other, I will do that.
It is failing on test case 3. My submission[submission:87339385]
It's just me or someone also felt that problem A does not seem like div-2 A... it's more like div-2 C.
Can someone tell whether my logic for C is correct.
First chose all flowers of one type (let's call it good). I considered the good flower as the one with maximum value of a+(n-1)*b.
Maintain a priority queue containing other candidate flowers ( with values 'a' if it is used for the first time and 'b' otherwise).
I will iterate while I can increase my answer by dec the count of good flowers by 1 and taking the top element from priority queue. I am getting wrong answer on test case 3. My submission 87350479
try this case,
By mistake I gave the wrong submission link (Now updated). The code for the above logic is giving 17 as answer which is correct I guess.
Your assumption to start from the best possible case from beginning is not correct imo. Try this case,
Also, according to me, you should be able to distinguish between the ai value and the bi value in the priority queue, because they hold different properties.
You can refer the editorial for a better explanation.
Thanks I will refer the editorial
when will the rating update?
help！I don't know why it went wrong. Please T_T 87353258 here's my submission
Please check the question difficulty before uploading, the div2 problems felt like div1 and clearly were way above the difficulty level. Disappointed
If it is a mirror of the official event nothing really can be done about the difficulty
One change I would've done though is explicitly specify in the announcement that difficulty would be higher than usual
I can't solved anything during 2 hours...
Div 1.5
Felt like Div. 1.5 Perhaps.
Anyways, Great Contest. Absolutely Loved the Problems!
Guys, it may be a dumb question but I am forced to ask this after the setback in this round. Generally, A and B questions with n<=200000 and having a time limit of 1 sec have O(1) solutions. But here, in ques B r-l<=499999 but it still has O(n) solution, is TLE not expected in this case? Please solve my issue> Thanks in advance.
It is because the number of test cases are less(upto 20), so total = 20 * 500000 = 10^7. So we do not need an O(1) solution here. As a generic rule you can follow this, if T*N <= 10000000, then O(n) solution usually passes.
Can someone help me understand where my code for problem C is giving wrong answer.Thanks in advance https://codeforces.me/contest/1379/submission/87357034
The hardest div2 I've ever solve
Older guys, please tell me if Mike Myrzayanov care about mentions in comments
https://codeforces.me/blog/entry/8790
I think Div2 B has weak test cases, my solution got AC https://codeforces.me/contest/1379/submission/87373765, but it should be TLE at this simple test case:
A small fact: there was no problem A in the Keldysh Olympiad, it was added to Сodeforces as a consolation.
I think the weak examples make the problem harder than other round...