Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Alexdat2000's blog

By Alexdat2000, 7 weeks ago, translation, ,

Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest.

Hello, Codeforces!

Codeforces Round #645 (Div. 2) will start at May/26/2020 17:35 (Moscow time). This round will be rated for the participants with rating lower than 2100. You will have 2 hours to solve 6 problems.

Problems of this round were prepared by Alexey Alexdat2000 Datskovskiy, Ilian ilian04 Andrianov, Vsevolod Sevlll Lepeshov. We have made an effort to create interesting problems, beautiful statements and strong tests. We wish you like problems and your rating increase.

We would like to express our gratitude to:

UPD 1: Scoring distribution: 500 — 750 — 1500 — 1500 — 2000 — 2500

UPD 2: editorial

UPD 3: Congratulations to winners!

Top 5 official participants:

Place Participant Problem solved =
1 OI_Blacksmith 6 6910
2 HackerDemon 6 6752
3 Potassium 5 5543
4 qwertz73355a 5 5478
5 SorahISA 5 5446

Top 5 all participants:

Place Participant Problem solved =
1 Egor 6 7821
2 kort0n 6 7495
3 Golovanov399 6 7365
4 nuip 6 7346
5 Geothermal 6 7332

Participants who sent the first correct solution to the problems:

Problem Participant Penalty
A Geothermal 0:00
B IgorI 0:02
D neal 0:11
E Geothermal 0:27
F chemthan 0:40

• +313

 » 6 weeks ago, # |   +252 "coronavirus contest" I won't risk taking part in it.
•  » » 6 weeks ago, # ^ |   +177 Everything is thoroughly sanitized!
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +12 hopefully my addresses will be sanitized
•  » » » 6 weeks ago, # ^ |   -43 Hacks should be sanitized.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +63 Just sanitize your hand after attempting each task.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   -64 .
•  » » » » 6 weeks ago, # ^ |   0 Before is better
•  » » » » 6 weeks ago, # ^ |   +40 I WANT MAXIMUM NEGATIVE CONTRIBUTION PLZ HELP ME.
•  » » » » » 6 weeks ago, # ^ |   +46 You are not doing well man. :(
•  » » » » » » 6 weeks ago, # ^ |   -10 he used reverse psychology to get so many upvotes.well done @Mr_Frustrated
•  » » » » » » » 6 weeks ago, # ^ |   0 And then how would you analyse the way i get upvotes?
•  » » » » » » » 5 weeks ago, # ^ |   +11 alas! my friend it will not work for u. IN YOUR FACE
•  » » 6 weeks ago, # ^ |   -294 I was trying to create a funny comment on your message. But I couldn't think of one. Can you like my comment it for trying?
•  » » 6 weeks ago, # ^ |   +6 use mask ….
•  » » 6 weeks ago, # ^ |   +61 Don't worry! CF will maintain long distant Queues.
•  » » 6 weeks ago, # ^ |   0 Actually it is a special kind of coronavirus vaccine. The higher score you achieve — the stronger immunity you get.
•  » » 6 weeks ago, # ^ |   0 Don't worry — your rating makes you immune to rating change as well as coronavirus.
 » 6 weeks ago, # |   -11 I hope this would be a very good contest for everyone.enjoy coders...
 » 6 weeks ago, # |   +21 This is what we all love to have — "beautiful statements and strong tests".
•  » » 6 weeks ago, # ^ |   +13 I thought it was "short* statements ... " :p
•  » » » 6 weeks ago, # ^ |   +12 It's beautiful when it's short xD
•  » » » » 6 weeks ago, # ^ |   -16 Check April Fool's contest and change your mind :D
•  » » » » 6 weeks ago, # ^ |   +2 -That's what she said :P
 » 6 weeks ago, # |   +207 I'll keep social distance between me and good results.
•  » » 6 weeks ago, # ^ |   +9 You don't need to bother — good results will be keeping social distance from you.
•  » » » 6 weeks ago, # ^ |   +1 Damn, u was right!
 » 6 weeks ago, # |   +13 It's a Сoronavirus contest! Amazing! hope problem-set will be related to it!
•  » » 6 weeks ago, # ^ |   +16 it will
•  » » » 6 weeks ago, # ^ |   0 Every contest maker say that.
 » 6 weeks ago, # |   -41 Sadly this comes from Russia, not China. (If you know what I mean)
•  » » 6 weeks ago, # ^ |   -45 Yes, I know what u meant lol:)
 » 6 weeks ago, # |   +12
•  » » 6 weeks ago, # ^ |   +355
 » 6 weeks ago, # |   +293 As a tester, I can confirm that this contest requires programming and/or problem-solving skills. The problem statements may or may not be short, just as the pretests are possibly strong.
•  » » 6 weeks ago, # ^ |   +21 Schrödinger's Contest
•  » » 6 weeks ago, # ^ |   +46 In other news, water is wet.
•  » » » 5 weeks ago, # ^ |   +3 WATER IS SINK
•  » » » 5 weeks ago, # ^ |   +19 I see I was mentioned?
 » 6 weeks ago, # | ← Rev. 2 →   +71 P R O B L E M — — — S T A T E M E N T S — — — W I L L — — — F O L L O W — — — S O C I A L — D I S T A N C I N G — — — N O R M S.
•  » » 6 weeks ago, # ^ |   +27 Lmao expecting a problem which asks to find the longest distance between two nodes in a graph.
 » 6 weeks ago, # |   +59 The time shown in calendar differs.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +74 You're the only man on earth who checks the calendar in Codeforces.
•  » » » 6 weeks ago, # ^ |   +64 I was born in last century.
•  » » 6 weeks ago, # ^ |   0 fixed, thanks
 » 6 weeks ago, # |   +29 The funny thing is that when you go to Codeforces, whose logo says Make Codeforces, not Coronaforces, the first thing you see is that announcementI hope that there will not be any new disputes on this topic
 » 6 weeks ago, # |   0 Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest. LOVE THOSE LINES
 » 6 weeks ago, # |   +34 Сoronavirus work, coronavirus school, coronavirus rest, coronavirus time spending, coronavirus contest. I really hope this does not mean the problems will be themed on the coronavirus.
•  » » 6 weeks ago, # ^ |   +10
•  » » » 6 weeks ago, # ^ |   +12 Ah. What an absolute shame. I really thought Codeforces would have the decency to not use a virus responsible for killing hundreds of thousands of people to simply make the statements more amusing. Also, some people retreat to websites like CF to not think about the ongoing situation and reduce anxiety; sadly, this act completely defeats that purpose.
•  » » » » 6 weeks ago, # ^ |   +33 Yeah, they should maintain absolute distance from it. But who knows may be the problem statements will be anti-corona.
•  » » » » » 6 weeks ago, # ^ |   +3 The statements might be related to people wearing masks and maintain social distancing, but it might be about the coronavirus spreading as well... Who knows. Let's just wait for the contest to come! :D
•  » » » » 6 weeks ago, # ^ |   +23 I hope problems will be related to fighting coronavirus.
•  » » » » » 6 weeks ago, # ^ |   +88 Given a map of Italy. Surprisingly, Italy can be represented as a tree! If at the moment, there's an outbreak in city i, the next moment, there will be outbreaks in all cities adjacent to i. Dr. Evil created the virus and wanted you to help find the city to plant the virus in, so that it will take over Italy the quickest.
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   -66 You spelled CHINA wrong.
•  » » » » » » » 6 weeks ago, # ^ |   0 DO YOU MEAN IT？
•  » » » » » » 6 weeks ago, # ^ |   +69 Hey I got nothing to do with that.
•  » » » » 6 weeks ago, # ^ |   +142 Your concern for the fresh wounds of the world is commendable, but all the same, different people having different coping methods. For some, breaking the taboo by incorporating it in humor and mundane activities in daily life is a way of normalizing the scope of the tragedy! Given the huge volume of jokes and memes spreading on corona, I think not that the humanity's response has been to shy away from involving corona in different aspects of life. For those who, rightfully, are sensitive to the topic, they have been notified and can skip the contest or solve some virtual in the meantime. As for fighting corona, if we take it seriously in our real life measures, I don't see the harm in using it as a theme in the virtual world. All my respect to those who have lost loved ones.
•  » » » » » 6 weeks ago, # ^ |   -24 good words
•  » » » » » 6 weeks ago, # ^ |   -47 While your argument isn't completely untrue, I highly suspect that this is a result of the lack of creativity of the authors rather than a motive of "breaking the taboo". To compare this with memes about the subject is borderline absurd. My argument is why must problems be themed on issues which have the potential to hurt the sentiments of a significant amount of people? Why must they skip taking this contest due to the lack of originality and thoughtfulness of the authors? While we are at it, why don't we "normalize" other tragedies such as the forest fire in Australia or even the 9/11? What's stopping us from creating problems about terminal illnesses such as cancer? In the end, problem statements are supposed to enhance the contest through light humor not become a reason for people to decide not to participate in a round beforehand.
•  » » » » » » 6 weeks ago, # ^ |   +31 Which tragedies are normalized and which ones aren't is a complex question beyond the reach of this discussion. I've heard though plenty of jokes about terror groups, and lots of WW2 games glorifying the traumatic event are frequently released.That being said, society will often make a clear distinction between acceptable and unacceptable. If (I doubt) there is an uproar over the covid problems (we still don't know what they will be like) we will inevitably see it in due time..
•  » » » » » » » 6 weeks ago, # ^ |   +12 But the stories were really sh**ty.
 » 6 weeks ago, # |   +31 I'll wear my mask during the round. Gotta play it safe
•  » » 6 weeks ago, # ^ |   +11 mhm good job. Also remember to wash your hands and sanitize the environment lol
 » 6 weeks ago, # | ← Rev. 4 →   -274 Disclaimer: Contains Offensive ContentI request you guys to take it as JOKE
•  » » 6 weeks ago, # ^ |   -14 we aren't
•  » » » 6 weeks ago, # ^ |   -148 Then its Safe
•  » » » 6 weeks ago, # ^ |   +7
•  » » 6 weeks ago, # ^ |   +5 Who cares if a joke is offensive. What cannot be forgiven is a joke not being funny.
•  » » » 6 weeks ago, # ^ |   +2 You R wrong my son, history is the witness that offensive content gets downvoted not the low level jokes. RIP my post
•  » » » » 6 weeks ago, # ^ |   +3
•  » » » » » 6 weeks ago, # ^ |   -18 No my son,then they are called Daddy of Americans God will help u, son. Have faith in GOD
•  » » 5 weeks ago, # ^ |   +11 Look, this is really insulting. Imagine yourself being one of the Chinese people, would you consider this as a "funny" joke anymore?
•  » » » 5 weeks ago, # ^ |   0 Foremost rule of a joke is that its never meant for insulting somewhat like a healthy roast.
•  » » » » 5 weeks ago, # ^ |   +10 Whatever. But I don't quite like that though. Sorry.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -9 Has someone asked that you like this or no? Who cares?UPD: This was made for people like you only. So Mission Successful!
 » 6 weeks ago, # |   0 Can you please clarify the exact timing ? It differs from that of the announcement and the contest page !!! @Alexdat2000
•  » » 6 weeks ago, # ^ |   -13 It is 14:35 UTC. There is Moscow time in announcement
 » 6 weeks ago, # |   -6 300iq always makes so interesting contests :D
 » 6 weeks ago, # |   0 I don't want beautiful statements, I want short statements.
•  » » 6 weeks ago, # ^ |   +16 They are not mutually exclusive.
•  » » 6 weeks ago, # ^ |   +23 Short statements, like April Fools Day Contest.
 » 6 weeks ago, # |   0 your your rating increase in English version, Alexdat2000
•  » » 6 weeks ago, # ^ |   0 thanks, fixed
 » 6 weeks ago, # | ← Rev. 2 →   +6 I'm tester of this round. I like problems very much and i strongly recommend everybody to take part in this contest
•  » » 6 weeks ago, # ^ |   +74 Lol..Every tester copy pastes the same line.
•  » » 6 weeks ago, # ^ |   0 pls check for problem B I have checked my code's sample output on 3 different compilers but when I submit it is giving wrong on pretest 1 itself. If anybody can tell why this is happening I will be very grateful. Pls check what is wrong
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 did you try it on codechef ide? sometimes testing contest code on codechef ide helps!
•  » » » » 6 weeks ago, # ^ |   0 yes
•  » » » » » 6 weeks ago, # ^ |   0 cur=0
•  » » » » » » 6 weeks ago, # ^ |   +3 THNX BRO. I TOTALLY MISSED IT.
 » 6 weeks ago, # |   0 I hope I can get a big positive $\Delta$, good luck to everyone!
 » 6 weeks ago, # |   +1 Alternatives to names Alexdat2000Coronavirus and Programming, Coronavirus and Sanitization , Coronavirus and Social Distancing , Coronavirus and Quarantine , Coronavirus and Prediction, Coronavirus and Symptoms.
 » 6 weeks ago, # |   +17 After the contest everyone should be quarantined for 14 days. :p
 » 6 weeks ago, # | ← Rev. 2 →   +15 Deleted
 » 6 weeks ago, # | ← Rev. 2 →   -16 First I thought it will kill my rating, but now I decided to take part in the contest. Happy Coding. 
 » 6 weeks ago, # | ← Rev. 2 →   -20 i don't want to end up in lockdown
 » 6 weeks ago, # |   +4 Stay home and Code because Codeforces will never let you go away from coding. These days are really helpful for many developers like me who now has interest in coding. Thank you MikeMirzayanov.
 » 6 weeks ago, # | ← Rev. 2 →   0 Deleted
 » 6 weeks ago, # |   +4 i hope to find nice problems and nice ideas
 » 6 weeks ago, # |   0 That illustration looks like it's from a Rick & Morty episode. "Covid Riiiick!"
 » 6 weeks ago, # |   +164
 » 6 weeks ago, # |   0 Y'all got any more of that bat juice? Cause I'm running short of supply.
 » 6 weeks ago, # |   +3 Nice score distribution:)
 » 6 weeks ago, # | ← Rev. 2 →   -9
 » 6 weeks ago, # |   -61
 » 6 weeks ago, # |   +110
•  » » 6 weeks ago, # ^ |   +120
 » 6 weeks ago, # |   -20 Got to learn a lot !
 » 6 weeks ago, # |   0 What about social distancing???
 » 6 weeks ago, # | ← Rev. 2 →   -11 .
•  » » 6 weeks ago, # ^ |   -8 No
 » 6 weeks ago, # |   0 Corona Virus Contest! Expecting Bats in problem statements!!
 » 6 weeks ago, # |   +22 Hope "Accepted" wouldn't make social-distancing from "Pretests Passed" :)
 » 6 weeks ago, # | ← Rev. 2 →   -17 Deleted
 » 6 weeks ago, # |   +1 Would be wearing a mask inside my home for the first time, thanks to Codeforces :)
 » 6 weeks ago, # |   +68 I bet there gonna be a bit masking problem!
•  » » 6 weeks ago, # ^ |   -6 Implementing Bit masking is a kind of tough job. ₍ఠ ͜ఠ₎
•  » » » 6 weeks ago, # ^ |   +1 Well you've got 4 hours to study it though. :)
•  » » » » 6 weeks ago, # ^ |   0 Thanks for helping me to figure this out!! LOL!
•  » » 6 weeks ago, # ^ |   +7 Sorry was thinking the problems are about saving ourselves and social distancing not a romantic story with Coronavirus-chan!
 » 6 weeks ago, # |   +22 The problem setters of this round are hosting their first round on Codeforces.Best of luck to them!
•  » » 6 weeks ago, # ^ |   +19 thanks :)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Do setters contact MikeMirzayanov or anyone from Codeforces contact high rated people?
•  » » » 6 weeks ago, # ^ |   0 when you are eligible to proposing contests/problems the option to do so will appear on your account (read this)
 » 6 weeks ago, # | ← Rev. 2 →   -14 Deleted
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I think you should fix yourself(your bug) first .Your memes are being boring .
•  » » » 6 weeks ago, # ^ |   +4 Please downvote me.
 » 6 weeks ago, # |   +9 I'm in!
 » 6 weeks ago, # |   0 By the way Image of corona Virus in post can be like original corona virus with pricking peaks and magenta colour. for real feel.
•  » » 6 weeks ago, # ^ |   +16 The "original coronavirus" isn't magenta
•  » » » 6 weeks ago, # ^ |   0 Ohk!
 » 6 weeks ago, # | ← Rev. 3 →   -13 Nice flop. I pretty much knew the meme was gonna flop but still went with it.
 » 6 weeks ago, # |   +66 Is it r̶a̶t̶e̶d̶ sanitized?
•  » » 6 weeks ago, # ^ |   +38 yep
 » 6 weeks ago, # |   0 Сoronavirus work!!coronavirus school!! coronavirus rest!! coronavirus time spending!! coronavirus contest.!!
 » 6 weeks ago, # |   +12 Make sure everyone sanitize their code before compiling.
 » 6 weeks ago, # |   +3 Prevent corona-unrate virus through queue-distancing.
 » 6 weeks ago, # |   0 Scoring of C and D are same. Let's See #ofsubmission(c)?#ofsubmission(D) (? = ).
 » 6 weeks ago, # |   +34 Coronavirus contest should include bit-mask problems
 » 6 weeks ago, # |   0 bulmanupje? kut!!
 » 6 weeks ago, # |   +27 As you got used to it, upsolving is on us 5 mins after the round ends:https://youtu.be/KfiUrDLad4QOn Algopedia. Bring your masks!
 » 6 weeks ago, # |   -6 Previously I need water,pen and pencil. For this contest I need extra 2 things: Mask, Hand sanitizer.
 » 6 weeks ago, # | ← Rev. 2 →   0 Nice
 » 6 weeks ago, # | ← Rev. 2 →   -18 It is strictly recommended to hate 300iq
•  » » 6 weeks ago, # ^ |   -30 Yeah, he removed a lot of good stuff. For example, small memes under each problem :(
•  » » » 6 weeks ago, # ^ |   +39 As tester I can say that this memes were typical shitty Facebook boomer jokes for me. They were completely unrelated to statements.So removing it from statements was necessary.
•  » » » » 6 weeks ago, # ^ |   -52 There were other testers besides you who liked the pictures.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +58 You can share this memes so everybody can judge on their own.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 As tester, I totally agree with you.
 » 6 weeks ago, # |   0 I'm hoping vaccine for corona virus is found by scientists in problem statements
 » 6 weeks ago, # |   +1 is the new rating system starting from this contest?
 » 6 weeks ago, # |   +10 I like it
 » 6 weeks ago, # |   +5 How do you prepare yourself 30 minutes before the contest?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +2 making tests for the problems
•  » » 6 weeks ago, # ^ |   +9 We try to keep ourselves calm before the contest, if i talk about myself then i go for a short evening walk before contest, which relax my mind, also i prepare all my templates, charge my laptop, take a water bottle, go to washroom and start contesting... you don't need to be preparing hard by solving problems just before the contest...its not my a university exam...
 » 6 weeks ago, # |   +7 Expecting a question to maximize social distance between all people on a grid.
 » 6 weeks ago, # |   +15 Nice problems, thanks for your effort, but in my opinion the gap between problems were just too much(they were growing harder so fast), you could have added two problems to make it a nice div1 contest.(i know its not as easy as it seems to be)
 » 6 weeks ago, # |   +51 I came here after solving D (in between contest).The problems are nice, the statements are ugly.
•  » » 6 weeks ago, # ^ |   -9 How would you modify the statements to make then nicer?
•  » » » 6 weeks ago, # ^ |   +15 Mainly D, I don't like such themes (and then maybe you can win the heart of Coronavirus-chan).Also coronavirus-chan???
•  » » » 6 weeks ago, # ^ |   +11 I'll still thank you guys for the contest because the problems in themselves were very nice.
•  » » » » 6 weeks ago, # ^ |   +17 thanks
 » 6 weeks ago, # |   +25 C and D do not deserve same points. Change my mind :|
•  » » 6 weeks ago, # ^ |   +16 Strongly agree
•  » » 6 weeks ago, # ^ |   -20 We are really sorry for this, all our testers who solved C also solved D :(Hope, you enjoyed problemset anyway
•  » » 6 weeks ago, # ^ |   +1 Agreed. The coordinators asked us to change D from 1750 to 1500.
 » 6 weeks ago, # |   +11 1st half hour solved A,B and rest of time just thinking about solution C and D.but fail to find any way to reduce time complexity.This called life of pupil :( sad life :(
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -6 C is just observation based. :)
•  » » » 6 weeks ago, # ^ |   0 again tried bro..but failed (bad luck or my little knowledge)..
 » 6 weeks ago, # |   -6 C was certainly not worth 1500.
•  » » 6 weeks ago, # ^ |   +12 You mean its worth more or less? lol
•  » » » 6 weeks ago, # ^ |   -38 Less xD, if you get the pattern, it is just 2 lines of code per test case, else you'll just be scratching your head for the rest of the contest.
•  » » » » 6 weeks ago, # ^ |   +2 Yeah, I was scratching all right. Now tell me the pattern already
•  » » » » » 6 weeks ago, # ^ |   -13 1+(x2-x1)*(y2-y1)
•  » » » » » » 6 weeks ago, # ^ |   +13 WTF
•  » » » » » » 6 weeks ago, # ^ |   0 Can you please explain, how you arrived at the formula? I'll be much obliged sire, Thank you!
•  » » » » » » 6 weeks ago, # ^ |   0 can you tell why and what exactly was the question asking us to calculate?
•  » » » » » » 6 weeks ago, # ^ |   0 i tried with (x2-x1)+(y2-y1) in the last minute without any logic though..my unfortunate..
•  » » » » 6 weeks ago, # ^ |   +3 I haven't found the pattern, so I coded brutforce and facepalmed a lot after it
•  » » » » 6 weeks ago, # ^ |   +34 it is short in code but idea is not really easy
•  » » » » » 6 weeks ago, # ^ |   0 True AF :3
•  » » » » » 6 weeks ago, # ^ |   -25 Write a generator and observe, is it that hard?
•  » » » » » » 6 weeks ago, # ^ |   0 not hard, but not too easy for div2C
•  » » » » » » 6 weeks ago, # ^ |   +6 I don't think one can say "hard" or "easy". It is hitting the right spot, or knowing the pattern beforehand. The idea is not hard, but you need to guess there might be a pattern, come up with bruteforce to check, and finally write (w-1)(h-1)+1 XD
•  » » » » » » 6 weeks ago, # ^ |   0 Are you familiar with the concept of proof?
•  » » 6 weeks ago, # ^ |   +12 It really took me almost an hour to realise that you can solve C with only 1 formula :))
•  » » » 6 weeks ago, # ^ |   +1 Same here buddy. XD
•  » » » 6 weeks ago, # ^ |   +7 It really took me almost an hour to realise how foolish I am. :(
•  » » » » 6 weeks ago, # ^ |   +1 lmao, I felt the same
•  » » » 6 weeks ago, # ^ |   0 Can you share your approach please !!
•  » » » 6 weeks ago, # ^ |   0 what is the solution of C... isn't it (x2-x1)*(y2-y1)+1?
•  » » » » 6 weeks ago, # ^ |   0 it is
•  » » » » » 6 weeks ago, # ^ |   0 https://codeforces.com/contest/1358/submission/81529915I forgot to convert in long long ... my bad
 » 6 weeks ago, # | ← Rev. 2 →   -17 Looks like more of a Maths Contest than a Coding Contest, special credits to "C".
 » 6 weeks ago, # | ← Rev. 4 →   -20 pls check for problem B I have checked my code's sample output on 3 different compilers but when I submit it is giving wrong on pretest 1. If anybody can tell why this is happening I will be very grateful. void solve() { ll n; cin>>n; ll a[n]; loop(i,0,n) cin>>a[i]; set S; unordered_map M; loop(i,0,n) { S.insert(a[i]); M[a[i]]++; } ll cnt=0,cur,nany=0; for(ll x : S) { nany+=M[x]; if(cur+M[x]>=x) { cnt+=nany; nany=0; } cur+=M[x]; } cout<
•  » » 6 weeks ago, # ^ |   0 U did n't send ur code, how can anyone check it?
 » 6 weeks ago, # |   +11 Nice problemset. Thanks!
 » 6 weeks ago, # | ← Rev. 2 →   +11 1358B - Maria Breaks the Self-isolation Now I see what the point of grannies near to my house is
 » 6 weeks ago, # | ← Rev. 2 →   +8 Loves the problemsets, but apparently statements are too long. Would have been nice if statements were a bit shorter
 » 6 weeks ago, # | ← Rev. 2 →   +118 Me after solving C
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +9 What's the pattern? Edit: I'mma cry myself to sleep.
•  » » » 6 weeks ago, # ^ |   +3 $(x2-x1)(y2-y1)+1$
•  » » » » 6 weeks ago, # ^ |   0 I also came up with the same solution .. but can't figure out when the paths will have same sum...help me with C
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 For $(1,1)$ to $(3,3)$: $1-2-5-9-13$ and $1-3-5-8-13$. You can work the pattern out similarly for other values.
•  » » » » » » 6 weeks ago, # ^ |   0 https://codeforces.com/contest/1358/submission/81529915I forgot to convert in long long.. my bad
•  » » » 6 weeks ago, # ^ |   0 (x2-x1) * (y2 — y1) + 1
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Can you please explain how you got there ?? though I observed a zig-zag matrix of different sizes same sum
•  » » » » » 6 weeks ago, # ^ |   +9 Maximum possible sum — minimum possible sum + 1. I shifted to origin and calculated both sums using double AP. Minimum was when you go RRRRDDDD and maximum was when you go DDDDDRRRR.
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 AdsT I got the same observation. But couldn't make it to formula.How did you get it?Would you please elaborate?
•  » » » » » » » 6 weeks ago, # ^ |   0 There is a better solution available now, in editorial. I feel stupid now for solving so much maths. But anyway if you wanna look into the formula here you go https://www.quora.com/How-do-I-find-the-sum-of-a-sequence-whose-common-difference-is-in-a-p
•  » » » » » » » » 5 weeks ago, # ^ |   0 I too did the same thing but without shifting the points and hence got the wrong answer, can you kindly explain your logic of how you shifted the points.
•  » » » » » » » » » 5 weeks ago, # ^ |   +1 I assumed my starting point was 1, 1. So I calculated the ending point as r = x2-x1+1 and c = y2-y1+1. Now I need the sum from 1 to cth term (for RRRRR). Then sum of r terms starting from previous term (for DDDD).Similarily doing the same for DDDDRRR, now notice this time starting term of difference AP was 2. Don't forget to subtract the corner term which could be counted twice.You can look at this solution of mine https://codeforces.com/contest/1358/submission/81527124 It has my logic, although it failed test case 5 because of long long oferflow while calculating the sums. It gives correct output for all the values less than 1e8. So I had to do the calculation on paper and arrived at r*c+1.
•  » » 6 weeks ago, # ^ |   +9 Imagine you have some path and you changed a "corner" from (x,y) to (x-1, y+1), path value changes by 1.
•  » » 6 weeks ago, # ^ |   +4 Well we have the upper and lower bound. Just take the diff
 » 6 weeks ago, # |   +23 Humorous and awful......
 » 6 weeks ago, # |   -50 Problem D was failing in Pretest 12. could you tell me why. here is my codeimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class TheBestVacation { public static int getMaxSum(int arr[], int x) { int s = 0; int maxSum = 0; for (int i = 0; i < x; i++) { s += arr[i]; } maxSum = Math.max(s, maxSum); for (int i = x; i < arr.length + x; i++) { s += arr[i % arr.length] — arr[(i — x) % arr.length]; maxSum = Math.max(s, maxSum); } return maxSum; } public static void main(String[] args) throws IOException { BufferedReader sc = new BufferedReader(new InputStreamReader(System.in)); String[] s = sc.readLine().split(" "); int m = Integer.parseInt(s[0]); int x = Integer.parseInt(s[1]); String[] days = sc.readLine().split(" "); int totaldays = 0; int arr[] = new int[m]; int i = 0; for (String _s : days) { arr[i] = Integer.parseInt(_s); totaldays += Integer.parseInt(_s); i++; } int input[] = new int[totaldays]; int idx = 0; for (int j : arr) { int k = 1; int a = 0; while (j > a) { input[idx] = k; k++; a++; idx++; } } int sum1 = getMaxSum(input, x); System.out.println(sum1); }}
•  » » 6 weeks ago, # ^ |   +3 x should be a long
•  » » » 6 weeks ago, # ^ |   0 Lol, I spend 1 hour and can't find this problem in my solution. Now I send same code (except reading x) and get AC.
•  » » 6 weeks ago, # ^ |   0 maybe you forgot to double the size of the size of array. I too was getting Runtime Error because of this.
 » 6 weeks ago, # |   +19 Hello Specialist Rank
•  » » 6 weeks ago, # ^ |   0 come to me! u get a partner!
 » 6 weeks ago, # |   0 Can somebody explain how to solve problem C ??
 » 6 weeks ago, # |   0 Very informative problem statements for a hard time like this pandemic.
 » 6 weeks ago, # |   +53 Why did $n = 2$ have to be allowed for F?
•  » » 6 weeks ago, # ^ |   +70 To make solution much more shitty!
•  » » 6 weeks ago, # ^ |   -34 to make it not div2D-E
•  » » » 6 weeks ago, # ^ |   +16 So (Div2D-E) + (some awful implementation) = Div2F? Wow!
•  » » » » 6 weeks ago, # ^ |   0 Lol it literally took me 130 lines to deal with it, and it's still wrong
•  » » » » 6 weeks ago, # ^ |   -22 afwul implementation? okk, but you can solve any problem and make it "some awful implementation"
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 When you solve good problem (on cf) implementation may be a bit heavy, but not awful.Since case with n = 2 is obvious when you have solved n > 2 it is pure implementation with many cases.
•  » » » » » » 6 weeks ago, # ^ |   -22 n=2 is obvious after n>2? many testers disagree with you
•  » » » » » » » 6 weeks ago, # ^ |   +13 I don't think that argument that uses "many testers" is good since many testers is your friends.
•  » » » » » » » » 6 weeks ago, # ^ |   -19 What's obvious for a Div1 might not be obvious for a Div2.
•  » » » » » » » » » 6 weeks ago, # ^ |   +18 Is div2F intended to be solved by Div2 participant during round?
•  » » » » 6 weeks ago, # ^ |   0 The implementation wasn't awful in my solution and I enjoyed writing it. Some problems were non-classic, e.g. the problem was with small $n$, not large $n$, and that was enough for me to think of it as an interesting problem.
•  » » » 6 weeks ago, # ^ |   +18 But then it just becomes a more annoying version of this problem (same basic idea with more casework), and as it's the only hard part ("go backwards" observation is necessary for $n = 2$ as well, so it's strictly easier to solve with larger $n$), you might as well have not allowed $n > 2$ then.Maybe my idea is wrong, I'll check myself after testcases become visible, but at least one part seems unnecessary and just to add on extra annoying implementation.
 » 6 weeks ago, # |   0 i have written a recursive function for C but it gives tle on pretest 4..could someone help me convert it into a dp solution using memoization or something like that?
•  » » 6 weeks ago, # ^ |   +3 We can't use dp, limits are of x and y are 10^9.The answer is just 1+(x2-x1)*(y2-y1)
•  » » » 6 weeks ago, # ^ |   0 Can you please explain how you are coming up with this formula?
•  » » » » 6 weeks ago, # ^ |   +1 For C, We know that sum will be least if we go from (x1,y1)->(x2,y1)->(x2,y2) and sum will be maximum if we go from (x1,y1)->(x1,y2)->(x2,y2). So the answer is basically each sum between max_sum and min_sum. You can also notice that the max_sum is min_sum + no. of rectangles below it. Hence the answer is 1+(width-1)(height-1)
•  » » » 6 weeks ago, # ^ |   0 Please elaborate.
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 The constraints are too big. DP Solution will be $O(N^2)$ which means about $O(10^{18})$ operations which'll take months to pass ig.EDIT: Okay, maybe you were asking about how he arrived at the formula....
•  » » » » » 6 weeks ago, # ^ |   0 I wanted about formula
•  » » » » » » 6 weeks ago, # ^ |   0 Yep, I edited right before your reply, sorry :)
•  » » » » » » 6 weeks ago, # ^ |   0 So let's have MxN rectangle:the least sum that you can get is when you first go right as much as possible and and then down. Each time you decide to go down before you reach right corner you add number of numbers left to right corner.So, max sum is the least sum + rectangle below, of size (m-1)(n-1). So the ans is (m-1)(n-1)+1
•  » » » » 6 weeks ago, # ^ |   0 Maximum possible sum — minimum possible sum + 1. I shifted to origin and calculated both sums using double AP. Minimum was when you go RRRRDDDD and maximum was when you go DDDDDRRRR.
•  » » » » 6 weeks ago, # ^ |   0 What my idea is: The sum will be minimum will we will just travel right and then down. And for maximum, travel down and then right.So, the answer will the total distinct sums between minimum and maximum.
•  » » 6 weeks ago, # ^ |   0 Even DP will be too slow for this problem since the points are in the range of $[1, 10^9]$. A test case could be $x_1 = 1, y_1 = 1, x_2 = 10^9, y_2 = 10^9$, and then the DP solution would require both $O(10^9*10^9) = O(10^{18})$ time and memory complexity (way too slow and too much memory).
•  » » » 6 weeks ago, # ^ |   0 but let's just say the if the limits would have allowed for a dp solution to pass...then could u tweak my code from purely recursive to recursive +dp? Thx in advance.
•  » » » » 6 weeks ago, # ^ |   0 This article has implementation details of the purely recursive solution, DP algorithm, and a combinatorics solution. Hope that helps!
 » 6 weeks ago, # |   +34 Recent contests are just about finding patterns and adhoc solutions rather than any algorithms.
 » 6 weeks ago, # |   +35 How to solve E?
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -25 I think this should pass if x > 0 : only possible k is n else : optimal k is ceil(n/2)+-1 or ceil(n/2) I did not submit though.
•  » » » 6 weeks ago, # ^ |   0 It doesn't pass. Wait for the editorial, we're going to release it soon.
•  » » 6 weeks ago, # ^ |   0 I applied if second val is > 0 , then total sum > 0 for ans to exist. if (x < 0) , then k >= (n+1)/2, so start traversing from back and find min length > 0 as increasing len further will make more negative for initial ones. but my failed somehow .
•  » » 6 weeks ago, # ^ |   +21 Suppose, there exists a $k < \bigl \lceil \frac{n}{2} \bigr \rceil$ which satisfies the given condition, then for any $p > 1$, $pk$ also satisfies given condition. So it is just enough to search for $k \geq \bigl \lceil \frac{n}{2} \bigr \rceil$. Let $m = \bigl \lceil \frac{n}{2} \bigr \rceil$. Also, let $s_i = a_1 + a_2 + ... + a_i$. So for $k \geq m$, the consecutive sums are equal to $p_1 + (k - m)x, p_2 + (k - m + 1)x ....$All of these terms should be positive. Now consider first $i$ terms and you get an upper bound or a lower bound (depends on whether x is positive or negative) and check if $n - i + 1$ satisfies that bound. For case when $x = 0$, just check if $p_i > 0$ for all $i$.
•  » » 6 weeks ago, # ^ |   0 Isn't it allways optimal to use k=n? If sum of all is positive this works, if negative ans=-1 anyway. What did I miss?
•  » » » 6 weeks ago, # ^ |   0 Look at the third example case.
•  » » » » 6 weeks ago, # ^ |   -11 The example outputs 4, but 6 would be a valid answer, too. n is allways an valid answer if sum of all n months is positiv.
•  » » » » » 6 weeks ago, # ^ |   -10 Consider the 3rd case again: -2 -2 6 -3, total sum = -1, but k=3 is valid :D
•  » » » » » » 6 weeks ago, # ^ |   -8 Ok, thanks. I think I misunderstood the problem statement.
 » 6 weeks ago, # |   0 How come so many people solved D? What is the trick in D?
•  » » 6 weeks ago, # ^ |   +3 There isn't really a trick, you just see that it is always optimal to end the last day of a month, and then you iterate over ends of month adjusting the beginning of the window so it is $x$ days large and "dynamically" calculate the hugs in the window with arithmetic progression sum formula.
•  » » » 6 weeks ago, # ^ |   +7 Literally thought the same but failed to implement during the contest. Thanks to C.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Couldn't submit in time. But you can instead find min sum subarray with elements equal to total days — x in the cyclic array of days (Note a cyclic array is just a concatenation of 2 arrays). Now its always optimal that min sum subarray will start from day 1 or (last day) of any month. So just iterate over the months, and get sum using prefix arrays. And return "total sum — min".
•  » » 6 weeks ago, # ^ |   +3 Key observation: the holiday must end at the end of some month. SolutionIterate over each month and do binary search to find in which month the holiday starts.
•  » » » 6 weeks ago, # ^ |   +11 I am not able to come up with a counter-example to this observation, but it's not really very clear either that it must hold.
•  » » » » 6 weeks ago, # ^ |   -6 The official editorial explains this, we'll release it soon.
 » 6 weeks ago, # | ← Rev. 2 →   0 Did anyone else wrongly overthink B as 2 pointers and screw up the timer?
 » 6 weeks ago, # | ← Rev. 2 →   0 I know that C was easy 1 line formula and so and so...... I don't get that, I m very stupid!! Now plz explain the logic!!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-1 2 43 5 86 9 13As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.
 » 6 weeks ago, # |   -12 Im so sad...Problem C was really EZ but I spent most time of the contest and I couldn't solve it ;-;
•  » » 6 weeks ago, # ^ |   0 Same thing... I don't know how, but just multiplying difference between x and y + 1 works
•  » » » 5 weeks ago, # ^ |   +1 You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-1 2 43 5 86 9 13As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.
•  » » » » 5 weeks ago, # ^ |   0 It's not best way. I count it like summ of number in row 0 1 2 3 4 5 ... 5 4 3 2 1 0 and it wasn't correct for some of cases where n != m. The main problem is to count all these numbers.
•  » » » » » 5 weeks ago, # ^ |   +1 Try to look at my submission. I know it is not the best way but the question was not obvious to me when I tried it in the contest.Try to look at my formula in the submission. If you don't get it, I will explain how i arrived at it.
 » 6 weeks ago, # |   +123 These were one of the worst problemsets ever, if we want to read newspaper we would go to other site not here
•  » » 6 weeks ago, # ^ |   +1 agree
•  » » 6 weeks ago, # ^ |   +7 I can't disagree with that.
 » 6 weeks ago, # | ← Rev. 3 →   -27 secrof tnemetats
 » 6 weeks ago, # | ← Rev. 3 →   +3 I tried to use something of sort of exponential search for D, but couldn't write it. Is the algorithm below correct for Div2D? If $max(d_i) \ge x$ then we can just choose that month in reverse order, that is $max+(max-1)+..(max-x+1)$ If not then we set end point at a month and try to reach as far before as possible. For this we can concatenate $d$ with itself so it becomes size $2n$ and precalculate arrays presum and presumsq each of size $2n$ (presum array is for presum of $d$ and presumsq is holding presum of $\binom{d_i+1}{2}$ Is this correct approach, what is the correct approach
•  » » 6 weeks ago, # ^ |   -19 ternary search over start date of each month
•  » » 6 weeks ago, # ^ |   0 Yes
•  » » » 6 weeks ago, # ^ |   0 I tried writing it in my own way using exponential search (or binary search) submission can you check out and tell if theres a way to simplify
 » 6 weeks ago, # | ← Rev. 2 →   +5 I spent most of the contest trying to calculate sums of difference series in question C until I figured out the simpler solution... oof
 » 6 weeks ago, # |   +12
•  » » 6 weeks ago, # ^ |   -8 you talk too much!!! just tell the logic and move on!!
•  » » » 6 weeks ago, # ^ |   +4
 » 6 weeks ago, # |   +14 Question B exposed my reading skills.
 » 6 weeks ago, # |   0 How To solve E if $x <= 0$ $?$
 » 6 weeks ago, # |   0 can C be solved using recursion+dp?
•  » » 6 weeks ago, # ^ |   +2 No. DP is too slow because x, y can get very large.
 » 6 weeks ago, # |   +10 I feel like I'm getting worse each contest. Took an awful amount of time for A,B and I'll barely stay expert thanks to C
 » 6 weeks ago, # |   +39 Problem C is cool.(Only after you get it)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 can you please explain it's approach..i still did't get it thanks in advance.
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   +1 The difference between max and min sum + 1.
 » 6 weeks ago, # | ← Rev. 2 →   0 I can't figure out why my solution for E gives WA. I did the following: If the sum of $a$ is positive, answer is $n$. Otherwise, if $x$ is not negative, there's no answer. Otherwise, let $w$ be the smallest integer such that the sum of $a_{n-w+1}, a_{n-w+2}, ..., a_n$ is positive. If all subarrays of size $w$ are positive, $w$ is the answer. Otherwise, there's no answer.
•  » » 6 weeks ago, # ^ |   +5 9-1 -1 2 -2 5 -1 -1 -1 -1I think this can be one of the counterexample.
•  » » » 6 weeks ago, # ^ |   0 Thanks, this was very helpful to correct my solution.
•  » » 6 weeks ago, # ^ |   0 6 4 -4 4 -1 
 » 6 weeks ago, # |   +1 Misinterpreting and misreading questions since 4-5 rounds. Fucking up every contest like a boss.
 » 6 weeks ago, # |   +24
 » 6 weeks ago, # |   0 It took me to see comments to get the pattern in C and still don't understand. please explain why it works
•  » » 5 weeks ago, # ^ |   0 You need to think about the max possible sum and min possible sum. For example, take (1,1) and (3,3) as the coordinates. The grid is like this:-1 2 43 5 86 9 13As you can see, max possible sum will come when we go column first and then row i.e. 1->3->6->9->13. min possible sum will come when we go row first and then column at the end i.e. 1->2->4->8->13. Now you have to realize the difference in the terms . Draw 2-3 examples you will get it.
 »