### ReD_AwHiLe's blog

By ReD_AwHiLe, 2 months ago, ,

Hello, Codeforces!

I'm glad to invite you to my first round Codeforces Round #632 (Div. 2), which will take place on Apr/08/2020 17:35 (Moscow time).

"Thank you" time!

I'd like to thank:

You'll be given 6 problems and 2 hours to solve them. Point distribution will be announced as soon as possible.

Hope you will enjoy the round! Good luck and have fun!

P.S: YES, IT'S RATED.

UPD: Score distribution: 500 — 750 — 1250 — 1750 — 2000 — 2500.

UPD2: Congratulations to the winners!!

Div2:

Wow, there is no unrated in div2 round!

All:

UPD3: I will post solution in several hours.

UPD4: It was very long several hours, I'm very sorry for that :( Editorial

• +878

 » 2 months ago, # |   +1 Auto comment: topic has been updated by ReD_AwHiLe (previous revision, new revision, compare).
•  » » 7 weeks ago, # ^ |   -9 Hope it will be rated. But im pretty sure it won't.
•  » » » 7 weeks ago, # ^ |   +8 Actually it is rated
•  » » » 7 weeks ago, # ^ |   +99 Is that your real face in your profile ?
 » 2 months ago, # |   +81 I'm sad because I won't be able to score in this round
•  » » 2 months ago, # ^ |   -21 But still your rating will not be updated .
•  » » 7 weeks ago, # ^ |   -9 why not?
•  » » » 7 weeks ago, # ^ |   +24 I think Masters aren't trusted participants in Div 2.
•  » » 7 weeks ago, # ^ |   0 Hope your dream of become rated in div2 contest come true one day
 » 2 months ago, # |   +8 why aren't there more contests?? :(
•  » » 2 months ago, # ^ |   +107 Because it takes time and effort. You can solve practice problems at any time.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -102 :v
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +163 You can solve practice problems right now and become expert in only one rated contest!
•  » » » » » 2 months ago, # ^ |   +65 But... This requires work... I want instant gratification! (•̀o•́)ง
•  » » » » » » 2 months ago, # ^ |   -12 But there is no shortcut for instant gratification in competitive programming.if u practice more then u will need less contests to become expert.
•  » » » » » » » 2 months ago, # ^ |   +71 Aaaaaaand you missed the joke :))...
•  » » » » » » » » 2 months ago, # ^ |   +11 OH.Cool next time i will try not to miss.
•  » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +10 Whoosh
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Because it's not easy for problem setters to set a problems with good test cases within a day. It takes a lot of effort to think corner test cases. One of my friend was problem setter it took 2-3 days to make 1 problem with test cases.
•  » » » 7 weeks ago, # ^ |   0 yes definitely and it is codeforces not normal coding platform such that problem makers will make problem easy ; they have to think twice while making it a problem whether it will be very easy or not or something else.
•  » » 7 weeks ago, # ^ |   0 You can find list of competitions on other platforms here
 » 2 months ago, # |   +17 Good Job. It is your first contest. I hope it will be good
 » 2 months ago, # |   +30 I think I saw a few days ago that the round was of 2.5 hours. Correct me if I am wrong.
•  » » 2 months ago, # ^ |   +70 Its true and it was my mistake. Sorry for misleading. Round will be 2 hours long.
•  » » » 7 weeks ago, # ^ |   0 can you post link of previous contests by you ?
 » 2 months ago, # |   +55 Hoping for no queueforces and strong pretests!
•  » » 7 weeks ago, # ^ |   +23 I pledge not to submit without checking the sample cases.
•  » » » 7 weeks ago, # ^ |   +74
•  » » » » 7 weeks ago, # ^ |   +42 Nope! I code in submit page and I submit without compiling.
•  » » » » » 7 weeks ago, # ^ |   +12 Great bro! I need that level of confidence in my life XD.
•  » » » » » » 7 weeks ago, # ^ |   +1 That level of confidence in real life can be real baad!
•  » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Well, this kind of joke in real life is very baad.
•  » » » » » » » » 7 weeks ago, # ^ |   +1 are you sure?
•  » » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   -19 I am pretty sure. :P
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 Now I'm thinking there should be such a round every few months. A 'No IDE' round, only Notepad.
•  » » » » » » 7 weeks ago, # ^ |   0 No need for Notepad, just type into the "submit code" tab! ;-)
 » 2 months ago, # |   -124 Is it really RATED???????
•  » » 2 months ago, # ^ |   0 yes it will be rated for division 2 .
•  » » 2 months ago, # ^ |   -6 Of course and without jokes
•  » » 2 months ago, # ^ |   +21 Nah,man.We are all messing with you (even the contest statement) :/
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +4 Coding > Singing
 » 2 months ago, # |   -85 isitrated?
•  » » 2 months ago, # ^ |   -6 Yes of course it is rated.
•  » » » 7 weeks ago, # ^ |   0 no, itisrated
•  » » » » 7 weeks ago, # ^ |   -20 I think u are trying to comment some thing.lol
 » 2 months ago, # |   0 I hope i'll become expert in this contest
•  » » 2 months ago, # ^ |   -13 Me too , good luck :)
 » 2 months ago, # |   -105 is it rated?
•  » » 2 months ago, # ^ |   +25 Of course rated.It's a normal division 2.
•  » » 7 weeks ago, # ^ |   0 Why are so many people asking this question over and over again？
•  » » » 7 weeks ago, # ^ |   +31 May be to get downvotes
•  » » » 7 weeks ago, # ^ |   +39 May be they wanted to increase their absolute value of contribution.
 » 2 months ago, # | ← Rev. 3 →   +32 Many contestants had trouble entering competitions at work and study times, but now everyone in home, so let's have fun. good luck everyone ^_^
 » 2 months ago, # |   -62 rtd?
•  » » 2 months ago, # ^ |   +5 Yes, in bold at the bottom, it says:"P.S: YES, IT'S RATED."
•  » » » 2 months ago, # ^ |   +41 rtd for me?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +24 In that case, no, as div. 2 means under 2100 rating
•  » » » » » 2 months ago, # ^ |   -13 thx
 » 2 months ago, # |   +7 Darn had to be one day before my birthday T-T
 » 2 months ago, # |   +6 I hope strong pretests are there this time.. Can't we have both strong and small number of pretests?
•  » » 2 months ago, # ^ |   +80 I tried to do so :)
 » 2 months ago, # |   +19 I hope to become a specialist in this round!
•  » » 2 months ago, # ^ |   +18 good luck!
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +4 All the best :D
 » 2 months ago, # |   +273 *Codeforces round starts* Codeforces servers:
•  » » 2 months ago, # ^ |   0 наелся и спит
•  » » 7 weeks ago, # ^ |   +2 Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com.
 » 2 months ago, # |   +5 I hope to get Candidate Master in this round!
•  » » 7 weeks ago, # ^ |   +14 You didn't even participate...
•  » » » 7 weeks ago, # ^ |   0 Perhaps he started, and did not submit anything. Like me.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 Thanks, you both didn't participate, otherwise my rank must be (current_rank + 2)
•  » » » 7 weeks ago, # ^ |   0 I just had a sleepless night, so I skipped. It was unfortunate. However, I participated today but was slow on D. I will try my best on the next one!
•  » » » » 7 weeks ago, # ^ |   +3 I know, you will very soon become Candidate Master..
 » 2 months ago, # |   +7 Congrats on your first round. Looking forward to solve your problems
 » 2 months ago, # |   +12 contest made life easier to pass quarantine
 » 2 months ago, # | ← Rev. 2 →   -78 Why so negative?
 » 2 months ago, # |   -72 GO CORONA CORONA GO ....
 » 2 months ago, # |   +9 Ｉ got 2 "fst" in the last round, then I became blue. So I hope this round will have strong pretests.
 » 7 weeks ago, # |   -21 Any suggestion how should I practice to become a blue coder? Nowadays codeforces is giving hard implementation problems in c no and I find it hard to solve somehow.
•  » » 7 weeks ago, # ^ |   +2 Solve a lot of Div. 2 C and D problems, they are great for practice. Also, try to upsolve at least one problem after each contest. For example, I see you solved A and B in the last contest. Try to solve C, it's a good problem.
•  » » » 7 weeks ago, # ^ |   0 I'll try :) Thank you
•  » » » 7 weeks ago, # ^ |   0 C was a nice one
•  » » » » 7 weeks ago, # ^ |   0 how to solve C ?
 » 7 weeks ago, # |   +11 May i ask how many hours you and whoever helped you with making problems in polygon spent on the contest?
•  » » 7 weeks ago, # ^ |   +55 Hm, I don't know... Maybe about 15-20 hours I was spent only with polygon, without creating test scenarios and problems, just for writing code and statements. It took much longer to come up with the tasks (~1 year). But it was passive work. One month I didn't do anything, and the next I create 2-3 tasks.
•  » » » 7 weeks ago, # ^ |   +29 Thanks for reply, i hope you get better and better in problem-setting, i think 20 hour is very nice for the first time :).
•  » » » 7 weeks ago, # ^ |   +4 Thank you for putting in the effort to create the contest! Wishing everyone luck.
•  » » » 7 weeks ago, # ^ |   0 you make me green this time i dare you
 » 7 weeks ago, # |   +13 Congrats, I'm excited :) I hope there is going to be more contests.
 » 7 weeks ago, # |   -36 Constest starts... ... Codeforces servers down
•  » » 7 weeks ago, # ^ |   -6 True :(
 » 7 weeks ago, # |   0 If we register for the contest but don't enter it. Will my rating still go down?
•  » » 7 weeks ago, # ^ |   0 If you don't submit anything, it doesn't count as a participation.
•  » » » 7 weeks ago, # ^ |   -6 thanks :)
 » 7 weeks ago, # |   +387
•  » » 7 weeks ago, # ^ |   +55 What about F? :)
•  » » » 7 weeks ago, # ^ |   +39 I wanted to put it but each line has 2 photos I Didn't want to ruin that :P
•  » » » 7 weeks ago, # ^ |   +29 Press F...
•  » » 7 weeks ago, # ^ |   +246
•  » » » 7 weeks ago, # ^ |   0 no me
 » 7 weeks ago, # |   -31 We want more contest!!!!!!!!!!!
•  » » 7 weeks ago, # ^ |   +15 Don't be so entitled, just be happy for the contests we get and for the efforts that the creators put into it. If you want more contests you can solve old ones at any time.
 » 7 weeks ago, # |   +5 Any particular reason for thanking antontrygubO_o twice for coordinating the round?
•  » » 7 weeks ago, # ^ |   +53 This round would not have existed without his help during the entire preparation process. This is my way of especially thanking him :)
•  » » 7 weeks ago, # ^ |   0 I think if someone accepts my contest proposal after 3-4 months or more, then i would be too happy to just thank whoever accepted my contest less than 2 times, or maybe just because anton helped him with making problems(then its one for accepting the proposal and reading it perfectly, and one for helping with making problems as a coordinator).
 » 7 weeks ago, # |   +6 Even if there aren't a lot of contests on CF,there are a lot of contests on different platforms.Stay inside and safe!
 » 7 weeks ago, # |   -66 Codeforces contest coordinators have been pretty lazy recently. Bad pretests, not many contests to begin with. Out of all the contests they still turn out bad.
•  » » 7 weeks ago, # ^ |   +27 I don't think you have a good understanding about coordinators' work, they are not making contests, they check contests made by Codeforces Community and help them to prepare the contest as well, which really takes time.Maybe it takes 2-3 day to prepare a contest, and there is tuns of contest proposals, it means tuns of tuns of problems, reading a contest should take about two hour at least, so even if 4 man are working 6 hours a day for preparing contests and checking contest proposals, then they can at most check 10 contest proposals in a day, which i dont think is enough for such a big community.So guess what, can coordinators spend some time on they're own?, far away from working and reading random proposals? for sure they have to sleep.I know there is few number of coordinators, and not all of them work full time for codeforces, probable the only way to increase number of good contests is to support community to make contest proposals more perfectly and prepare they're contests faster(codeforces is really doing it very well i think), or if the problem is the really long queue of contest proposals(which i think is the case), they may increase the number of coordinators and support them.Fully related to the topic: I wanna be a coordinator later in my life, so i should plant the seeds from now, yes? =P
 » 7 weeks ago, # |   0 Thank you!
 » 7 weeks ago, # |   +1 @ReD_AwHiLe hoping for the short statements and strong pretest.....?
 » 7 weeks ago, # |   +6 We want more contest in this quarantine :(
 » 7 weeks ago, # | ← Rev. 2 →   +139
•  » » 7 weeks ago, # ^ |   +6 I don't understand why people commented asking this and got lots of downvotes, though it's clear in the post. Maybe people are getting bored staying home and commenting to have fun.
•  » » » 7 weeks ago, # ^ |   -34 I don't understand why you are getting so much downvotes .
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +39 Is she rated?
•  » » 7 weeks ago, # ^ |   0 And then you make memes xD
 » 7 weeks ago, # |   +79 Div 1 coders in Div 2 contest everytime
•  » » 7 weeks ago, # ^ |   +1 I will just print Hello world then
•  » » 7 weeks ago, # ^ |   0 I was doing this today for div2 C XD
 » 7 weeks ago, # |   -10 Please arrange more contest during these corona days. :p
•  » » 7 weeks ago, # ^ |   +233 We try T_T
 » 7 weeks ago, # |   0 I hope there won't be a long queue, good luck:)
 » 7 weeks ago, # | ← Rev. 2 →   0 I can't able to submit solutions in JAVA, getting RUNTIME error, tried with previous accepted submissions. I don't know where to post this, this site doesn't even have a contact page.Got it I forgot to remove package declaration at top.
•  » » 7 weeks ago, # ^ |   +3 Better post a link to one of those submission, then somebody can tell you why it fails.
 » 7 weeks ago, # |   0 hope this contest not to be like previous one !!
 » 7 weeks ago, # |   +376 !
•  » » 7 weeks ago, # ^ |   0 TRUE AF
 » 7 weeks ago, # |   +11 I will provide you video tutorials for the round after it's done!
•  » » 7 weeks ago, # ^ |   0 yes please
•  » » 7 weeks ago, # ^ |   0 Whats ur channel?
•  » » » 7 weeks ago, # ^ |   0 I think it's called Algopedia (not sure tho)
•  » » » » 7 weeks ago, # ^ |   0
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Here it is brothers: https://www.youtube.com/watch?v=SS5eONgsluE&feature=youtu.be
 » 7 weeks ago, # |   +30 Your photo is so cute.
•  » » 7 weeks ago, # ^ |   +18 O kawaii koto
 » 7 weeks ago, # |   +10 All the best for your first contest. Nice time to get better at CP in this quarantine. Thank you guys.
 » 7 weeks ago, # |   0 what is score distribution for this contest?
•  » » 7 weeks ago, # ^ |   0 It will be announced 10 minutes before the contest
 » 7 weeks ago, # |   +10 CF-Predictor, In the last 6 contests he was giving wrong results, I hope that the mistake has been fixed and gives correct results in tomorrow contest.
•  » » 7 weeks ago, # ^ |   -6 Maybe, CF-Predictor has Coronaforces XD
 » 7 weeks ago, # |   +25 I am here after almost 11.5 months! 18 months if we ignore one-off contest I participated last year! Feels great to be back!And I see that the number of participants has gone ~23-24k over past few contests. Used to be ~7-8k back in my days!Great job guys!
•  » » 7 weeks ago, # ^ |   -37 It's Corona time!
•  » » » 7 weeks ago, # ^ |   0 Don't you guys use TikTok? Why so many downvotes??
 » 7 weeks ago, # |   +11 Contest registrations are increasing at a higher rate than the COVID-19 cases.
 » 7 weeks ago, # |   0 I hope to become a specialist and stay that way .....
•  » » 7 weeks ago, # ^ |   0 Best of luck ^_^
•  » » 7 weeks ago, # ^ |   +2 and i thought my graph was funny
 » 7 weeks ago, # | ← Rev. 11 →   0 I cannot register for the contest.
•  » » 7 weeks ago, # ^ |   0 Yea, I'm facing the same issue
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Me too.
 » 7 weeks ago, # |   0 Я почему то не могу зарегаться, выходит окошко Ooops! Something has broken down in Codeforces. Do not panic, you can try to reload the page or return Home Шо делать?
 » 7 weeks ago, # |   -11 give me one contest please let me be green
 » 7 weeks ago, # |   +18 I will be master tonight. Screen it
•  » » 7 weeks ago, # ^ |   0 Wait, 2 more hours!! :p
•  » » 7 weeks ago, # ^ |   0 Wow, you really did it
•  » » 7 weeks ago, # ^ |   +1 I became Candidate this round)
•  » » » 7 weeks ago, # ^ |   0 nice done :3
 » 7 weeks ago, # |   +30 Dear Codeforces web developers, there is a typo in setting->social->city section which is "City where you live ot city you are representing"
•  » » 7 weeks ago, # ^ |   0 It is city where u are representing.
•  » » » 7 weeks ago, # ^ |   0 I highlighted the typo! it should be or not ot
•  » » » » 7 weeks ago, # ^ |   +3 ohh i mistaken it .I thought whether u are asking about the city.
 » 7 weeks ago, # |   0 Hope we can all score and make progress in this contest!
 » 7 weeks ago, # |   -23 Finally, a contest after so long...
 » 7 weeks ago, # |   +6 Hoping for small queus, and strong pretests, gud luck guys...
 » 7 weeks ago, # | ← Rev. 3 →   0 I think the round isn't simple(for a newbie) My English isn't very good，please forgive me.
•  » » 7 weeks ago, # ^ |   +13 Why make such a pointless comment in the first place if you're so worried about your english.
•  » » » 7 weeks ago, # ^ |   0 Sorry，it's my problem
 » 7 weeks ago, # |   +17 Why hasn't the score distribution been published yet?
•  » » 7 weeks ago, # ^ |   0 Already published . you can check that now .
•  » » 7 weeks ago, # ^ |   0 Here it is!
 » 7 weeks ago, # |   +8 I am enjoying by reading comments.
 » 7 weeks ago, # |   0 First contest for me too, wish me good luck :D
 » 7 weeks ago, # |   -9 I hope it is a nice competition and we earn points in it ..
•  » » 7 weeks ago, # ^ |   0 best of luck.
 » 7 weeks ago, # |   -6 this my first contest. hope to solve many as possible..
•  » » 7 weeks ago, # ^ |   0 good luck.
 » 7 weeks ago, # |   +3 I did some virtual contests of division 2 ,i would try to give my 100%. No matter whether my rating increases or decreases .wish me luck and beft of luck to everyone.
 » 7 weeks ago, # |   +1 Hope this raund will help to me be 1600+, good luck all
•  » » 7 weeks ago, # ^ |   +1 hope so.
 » 7 weeks ago, # |   +1 22k participants ? can a rank under 3k will make me XXXprt
 » 7 weeks ago, # |   +3 on each contests .. people ask "is it rated" for atleast 5 times.. probably gonna change my username to "alwaysRatedPleaseReadFirst".
 » 7 weeks ago, # |   +19 thats moment when div1 participants not able to solve div2 D or even Cthats mean it will be fair contest for div2 participants!thanks!!
 » 7 weeks ago, # |   +37 nice round. I solve F and fail at C.
•  » » 7 weeks ago, # ^ |   0 Seriously man. After seeing div 2C, I was like I am no more div 1 :D
•  » » » 7 weeks ago, # ^ |   -8 I used Segment Tree to solve C:) It's more like a Div2D, if you ask me.
•  » » » » 7 weeks ago, # ^ |   0 Can you explain your idea on how to solve using segment trees.?
•  » » » » » 7 weeks ago, # ^ |   +7 Basically I try to count the number of bad segments. Lets fix the right border $r$. Now the segment is bad if it has some zero sum subsegment. For each $r$ lets find the biggest $l$, such that sum of $[l, r]$ is zero. Now if our right border is more (or eq) than $r$ and left border is less (or eq) than $l$ it's a bad segment. Now we are doing scanline and whenever we see $[l, r]$, we update some prefix with ones. You can do this even without sgtree, but I didn't think of it on the contest.
•  » » » » » » 7 weeks ago, # ^ |   0 My approach is somewhat similar, but I don't know why I'm getting TLE my code
•  » » » » » » » 7 weeks ago, # ^ |   +3 Try using map instead of unordered_map
•  » » » » » » » » 7 weeks ago, # ^ |   0 Thanks! It worked, but why unordered_map was giving TLE?
•  » » » » » » » » » 7 weeks ago, # ^ |   +3 Welcome to the club buddy. C++ unordered_map uses a fixed modulo, so it can be blown up to $O(n^2)$. You can look at this blog, to know more.
•  » » » » » » » » » 7 weeks ago, # ^ |   0 Thanks for enlightening me :D
 » 7 weeks ago, # |   +140 Interesting problems, but I think they are too hard for Div2
•  » » 7 weeks ago, # ^ |   +13 I have never related to something so hard.
•  » » 7 weeks ago, # ^ |   +5 Even though I didn't solve C but I solved D and I think it's because my mind was not clear.
•  » » 7 weeks ago, # ^ |   0 relatable :/
 » 7 weeks ago, # |   0 In Problem C I dont know what the Pretest 8 was but I wasnt able to pass it till end of contest
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Maybe this: 5 7 9 -7 5 2 ans = 12
 » 7 weeks ago, # |   -11 Why the hell would you make 4 heavy implementation problems in a row. We are so fucking tired of debugging and shit lord.
•  » » 7 weeks ago, # ^ |   +28 What are you talking about? These problems required a few good observations and had simple implementation. I mean first three problems needed less than 40 lines of code.
•  » » 7 weeks ago, # ^ |   +55 Hilarious
 » 7 weeks ago, # |   -7 I Got Internet disconnection due to my provider problems and i got connected about 30 mins agoIs there any solution for me ?
•  » » 7 weeks ago, # ^ |   +144 Yes. Get a new Internet provider.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +18 LOL! For some reason, I pictured Jian Yang from Silicon Valley saying this..
•  » » » 7 weeks ago, # ^ |   0 I have friends who face similar issues. All internet providers in Egypt are terrible. I don't think codeforces will do something about though, since it's not an issue a lot of people face.
 » 7 weeks ago, # |   +6 In Div-2B, I was first solving the wrong question and stuck thinking that we can a[i] to a[j] and a[j] to a[i], instead of only able to add a[i] to a[j] for i
 » 7 weeks ago, # |   +58 Video editorials for C and F out!CF
•  » » 7 weeks ago, # ^ |   0 I think it's great to have short explanations in video just after the end of the contest. If only I could press like multiple times!
•  » » 7 weeks ago, # ^ |   +2 Still didn't get C. During the contest I figured out how to find out bad subarrays using prefix sums. But then I need to remove all superarrays of this bad subarray as well. I was counting it twice in some cases. How are you handling this? I didn't get that.
•  » » » 7 weeks ago, # ^ |   0 Basically, I keep the rightmost starting position of such a subarray.This helps me to count only the subarrays starting at positions which are bigger than that position.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +6 for each index i, find how many subarray ending on that index have sum non zero, for that, we find the highest index j < i starting from which, sum is 0, then we know ans += (i — j);
 » 7 weeks ago, # |   +1 How to solve C?
•  » » 7 weeks ago, # ^ |   +18 Right above you :))
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   +8 I solved using map and prefix sum .We can calculate number of bad segments .Suppose while doing prefix sum we calculated value 'a' till position 'i' and suppose last such value 'a' has been found at position 'j' , then sum of numbers from 'j'+1 till 'i' is zero and number of bad segments it contributes is equal to (j+1-las)*(n-i+1) (provided (j+1-las) is positive) where 'las' is left position of previous such segment whose sum is zero. We include 'las' to avoid adding contribution multiple times.
•  » » » 7 weeks ago, # ^ |   +1 How comes that it contributes $(j+1-las)*(n-i+1)$
•  » » » » 7 weeks ago, # ^ |   +1 suppose array has length 20 . Let first segment whose sum is zero is [3,6] then number of bad segment is contributes = 3*15 . Now let next segment whose sum is zero is [8,12] then number of bad segment it contributes is 8*9. But [2,13] is calculated for both segments . Hence we use las = 3 for second segment.
•  » » » 7 weeks ago, # ^ |   0 I thought in the same way. But couldn't implement it. I missed the point of multiplying it by (n-i+1) and I ended up adding n-i+1 only :-(
•  » » » 7 weeks ago, # ^ |   0 Hey. I was trying on similar grounds during the contest and I am still trying to figure out my mistake. Can you please help me out?Here is my submission: 75899238
•  » » » » 7 weeks ago, # ^ |   0 I think it would be more convenient if you count the number of good subarrays. Just store last index position of the prefix running sum and the answer is equal to the i-map[prefix_sum], update map and last position at each index.
•  » » » » » 7 weeks ago, # ^ |   0 It would be very helpful if I could get any feedback on my code.
•  » » » 7 weeks ago, # ^ |   +3 Your explanation is very clear, thanks!! I was just facing the problem of adding contribution multiples times.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 even I did the same way..problem was not that difficult. My code is clean so may be easy to understand MY CODE: https://codeforces.com/contest/1333/submission/75954346Another problem on similar concept is : https://codeforces.com/contest/385/problem/B ENJOY
•  » » 7 weeks ago, # ^ |   0 1333C - Евгений и массив It can be solved using hashing/ mapping. Firstly calculate the prefix sum or cumulative sum. To check the 0 sum subarray. Visit this link for more details ... https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/ ...Then, iterate through the prefix sum and check whether it came before. If the prefix sum is repeated, then it indicates that the 0 sum subarray has.Then, increasing the pointer to that place, where all valid subarrays have found. My solution : 75964709
 » 7 weeks ago, # |   0 Cheers, another crowded contest end. Look at the number of participants.
•  » » 7 weeks ago, # ^ |   +10 The contest ran smooth tho (for me, atleast). Normally, I'd face lag while submitting and loading problems but today it was different. Submissions didn't last in queue for more than 2 secs. Really nice problems too.
 » 7 weeks ago, # | ← Rev. 2 →   +8 Was the n=3 case for E possible or not? I thought it wasn't (couldn't find a good proof but spent a while trying to construct cases to no avail, but I got WA and I was pretty confident about my construction for n > 4.
•  » » 7 weeks ago, # ^ |   0 It's possible
•  » » 7 weeks ago, # ^ |   +5 Same problem, for n>4 you can just copy his solution and add stuff the border, but not sure for n = 3.
•  » » 7 weeks ago, # ^ |   +5 1 2 4 5 3 8 9 7 6
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 Spoiler$1,2,4$ $5,3,8$ $9,6,7$Seems to work for n = 3
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   -30 Hey man , How your contest rating went up ?
•  » » » 7 weeks ago, # ^ |   0 ??? This has nothing to do with the contest lol you can just message me about that
 » 7 weeks ago, # |   0 bruh
 » 7 weeks ago, # |   +2 what is pretest 5 in C
•  » » 7 weeks ago, # ^ |   +1 I suppose this is the test like:5 -1 0 0 0 1or5 0 1 2 -2 -1or6 1 2 4 -5 -1 -1After I fixed this I got all pretests passed.
•  » » 7 weeks ago, # ^ |   +6 the same as memy solution was failed at pretest 5 too!!!!
•  » » 7 weeks ago, # ^ |   +5 I am not sure, but try this: 4 3 0 1 0 Expected answer should be 2
•  » » » 7 weeks ago, # ^ |   0 your testcase is very helpful ,thanks a lot
 » 7 weeks ago, # |   +2 For me the text of problems was hard to understand. Especialy 1333A - Маленький Артем was demotivating, since the expectation to solve a more or less nice first prob was not met.
 » 7 weeks ago, # | ← Rev. 2 →   +49 In D i was getting TLE just because i was using endl instead of "\n".
 » 7 weeks ago, # |   +17 What is pretest 7 in D?
•  » » 7 weeks ago, # ^ |   +5 I think it is something like 6 6 RLRLRL After accounting for this TC, i got AC. Previously, my solution too was failing on TC7
•  » » » 7 weeks ago, # ^ |   +1 My code gives the correct answer for this test case. So, it must be something else.
•  » » » 7 weeks ago, # ^ |   0 I don't think so. My code is also giving WA on Test Case 7 but it is giving the correct answer on the Test Case that you mentioned. T-T
•  » » » » 7 weeks ago, # ^ |   0 Lol i randomly started my comment like you xD.
•  » » » 7 weeks ago, # ^ |   +4 I dont think so, i know what i missed and i got wrong answer in testcase 7, but i'm pretty sure that its not the case, i say something like 6 7 RRLRLL.
•  » » » » 7 weeks ago, # ^ |   0 DeadlyCritic bingo
•  » » » » » 7 weeks ago, # ^ |   -10 Did you know how happy i was when i saw that after years someone called me? happy to hear that.
 » 7 weeks ago, # |   +54 WTF, how to solve B and C?
•  » » 7 weeks ago, # ^ |   +8 For C, check my video editorial, the comment is on the blog!
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 For B, I think:If $B[0] != A[0]$, solution is not possible.Else, for every position starting from 1, if $A[i] > B[i]$, you need to check if a -1 exists in A [1...i-1], if $A[i] < B[i]$, you need to check if 1 exists in A[1...i-1].Something like this maybe: Code#include using namespace std; typedef long long ll; typedef unsigned long long ull; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.precision(10); cout << fixed;// << boolalpha; int T; cin >> T; while (T--) { int N; cin >> N; vector A (N), B (N); vector > T (N, {false, false, false}); for (int i = 0; i < N; ++i) { cin >> A [i]; if (i > 0) T [i] = T [i - 1]; if (A [i] == 1) get <2>(T [i]) = true; else if (A [i] == 0) get <1>(T [i]) = true; else if (A [i] == -1) get <0>(T [i]) = true; } bool Okay = true; for (int i = 0; i < N; ++i) { cin >> B [i]; if (i == 0) { if (A [i] != B [i]) { Okay = false; } } else { if ((B [i] > A [i] && !get <2>(T [i - 1])) || (B [i] < A [i] && !get <0>(T [i - 1]))) { Okay = false; } } } if (Okay) cout << "YES"; else cout << "NO"; cout << '\n'; } return 0; } 
•  » » » 7 weeks ago, # ^ |   +1 Can you tell me how did you post your code such that we can collapse it? I always wanted to know lol
•  » » » » 7 weeks ago, # ^ |   +4 Use Spoiler.
•  » » » 7 weeks ago, # ^ |   0 Zeus_Not_Zues I have a doubt, A=[-1 3 0] B=[-1 1 2]. Output is 'NO',But if we choose (0,1) twice -> A=[-1,1,0] and (1,2) twice -> B=[-1,1,2],we can convert array A to array B. any help would be appreciated.
•  » » » » 7 weeks ago, # ^ |   0 Your A is an invalid array. A can only contain elements {-1,0,1}.So, if you go step by step through my code, you'll see that A = [-1 3 0] would become equivalent to [-1 -1 0]. And it is impossible to obtain B from this A.
•  » » » » » 7 weeks ago, # ^ |   0 yeah,,how did i miss this!!!! Thank you very much....
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Nice Solution.
 » 7 weeks ago, # |   +6 My first two submissions in the contest: WA Time I finally solved A: 16 minutes into the contest Codeforces DELTA: +125
 » 7 weeks ago, # |   +36 This round was so cool! Thank you all who preapred this wonderful competition!
 » 7 weeks ago, # |   +13 when will the editorials be out??
 » 7 weeks ago, # |   0 The verdict I got for problem E seemed wrong to me, am I missing something?Input : 4Output: 1 2 3 4 13 15 16 5 14 12 11 6 10 9 8 7 Verdict: wrong answer rook teleports: 0, queen teleports: 0Doesn't queen teleports 1 time?Link to submission: http://codeforces.com/contest/1333/submission/75904855
•  » » 7 weeks ago, # ^ |   0 No it wont teleport at all, u could use the output examples in the statement instead of finding the answer for $n = 4$.
•  » » 7 weeks ago, # ^ |   +1 No. The queens route is:1 2 3 4 5 6 7 8 9 10 12 11 14 13 15 16If I'm not wrong.
•  » » » 7 weeks ago, # ^ |   +1 oh i see now, i thought we cant go through visited cells. Thanks.
 » 7 weeks ago, # |   0 Can anyone explain how to solve C ?
•  » » 7 weeks ago, # ^ |   +5 Its a simple prefix sum problem.For each index i, calculate the next index next[i] such that the interval [i..j] has a sum of 0 (this can easily be done with a map and prefix sums). If no such index exists, let next[i] = N+1.Then, the answer is just the sum from 1 to N of (next[i]-i), since these are the number of arrays that don't have a subarray whose sum is zero.
•  » » » 7 weeks ago, # ^ |   0 Thanks for the explanation it really does make sense now. However, I am still failing test case 5, I have no idea why, do you mind taking a look at my submission (anything I am doing wrong)
•  » » 7 weeks ago, # ^ |   +3 My solution: maintain on the prefix $[0, p]$ such maximum $i$ that there exists $j$ such that $[i, j]$ is a bad subarray.Then let's count the number of good arrays that end in $p$. For that we notice that any array $[l, p]$ with $l \leq i$ is bad, and any with $l > i$ is good.
•  » » 7 weeks ago, # ^ |   +13 When I see such questions like counting subarrays I usually think in two ways: Iterate over lengths of subarrays i.e. count valid subarrays of length = 1,2,3,..,n and so on. OR Count number of valid subarrays starting from index i = 1,2,3,4 (assuming 1-based indexing). In this case, I used the 2nd way.For each index i, count how many good subarrays exist.How? Find ending indexes of 0 — sum subarrays starting from each index i. If there exist multiple such subarrays, take the subarray with minimum ending index. (Why?). If there is no such subarray starting from i and having sum = 0, then store (n+1) for that index. Let this be stored in subarray_becomes_zero_at[].subarray_becomes_zero_at[i] = j implies subarray from [i+1,....,j] is a 0-sum subarray. This basically happens when prefix_sum[i] = prefix_sum[j]. For iterate from right, and store what is the minimum j >= i and k >= i such that subarray_becomes_zero_at[k] = j. Let this j be stored as can_go_till[i] = j. This means, from every starting index i you can go till jth index without having any 0 sum subarrays in it. ans = sum( can_go_till[i] — i ) for every 1 <= i <= N.
 » 7 weeks ago, # |   +20 looks like Div 1.5
 » 7 weeks ago, # |   +25 God I literally misread B and for the entire contest I thought there was no restriction $l < r$.It was a horrible feeling of absolute stupidity when you see over 9k people having solved it and having absolutely no idea of even approaching it.Luckily I could notice it in the end and implemented it in the remaining 5 minutes but god was it stressful.Also it is actually now interesting how to solve that (apparently MUCH harder) problem.
•  » » 7 weeks ago, # ^ |   0 same :-(
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Lol same here. I made the same comment above. I was stuck in B for a long time, then moved to C and was able to solve in 15 minutes and again came to B and thankfully saw it.
•  » » » 7 weeks ago, # ^ |   0 i dont know ..what i did wrong in B? couldn't think of any case failing?
•  » » 7 weeks ago, # ^ |   0 same :P
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 How could we solve the harder version B? If i
•  » » » 7 weeks ago, # ^ |   0 I actually thought that this was B and was not able to solve it till the end when I noticed the constraint $i < j$
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I believe the question becomes slightly easier if the constraint i < j is omitted.If A does not contain -1, but B contains a number lesser than its counterpart in A, solution is impossible. Likewise, if A does not contain 1, and B contains a number greater than its counterpart in A, solution is impossible. 0 in A would not play any significant role.I think a harder version of this problem would be if we were only allowed to use a pair of indices (i, j) only once to construct B or maybe if A consisted of other elements instead of just (-1,0,1).
•  » » » » 7 weeks ago, # ^ |   0 It is not possible in those cases. But they are not the only cases where it is impossible. It gets very tricky to choose the order and which element to use first.
 » 7 weeks ago, # |   +6 the hardest c I’ve ever met.
•  » » 7 weeks ago, # ^ |   -7 Yup, A and C were extremely hard for their problem class.
•  » » » 7 weeks ago, # ^ |   +10 A was pretty simple. Just print white in the top left cell and black for all the rest.
•  » » » » 7 weeks ago, # ^ |   +3 i am crying now!!!
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 Yup, I figured it out too in 7 minutes. But still, I think A was extremely hard for a D2A.Doesn't make it a bad problem though, just should've been a B and C should've been a D.
 » 7 weeks ago, # |   +12 yeh, 30 mins for solve A, unsolved C and -100 rating! Good job
•  » » 7 weeks ago, # ^ |   0 me either lol
•  » » » 7 weeks ago, # ^ |   0 me toooo..
 » 7 weeks ago, # |   +39 Needed swap(E, F)
•  » » 7 weeks ago, # ^ |   +8 swap(F,D) would be better
•  » » » 7 weeks ago, # ^ |   -16 Actually I think swap(C,D) and swap(E,F) would be ideal. D is more straightforward than C IMO.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 swap(A,B), since A has some pitfalls if you do not see one of the simplest solutions in the first place.
•  » » 7 weeks ago, # ^ |   +3 I think F is even easier than C,it took me half an hour to solve C and got WA one time,an hour to solve D and got 3WAs and 1TLE,but only 7 minutes for F and passed it.
 » 7 weeks ago, # |   0 Pending system testing.... There are nervousness in Codeforces... XD HI! How solve C?
 » 7 weeks ago, # | ← Rev. 2 →   +9 The problem C bothered me too much, This is not an enjoyable contest.
 » 7 weeks ago, # | ← Rev. 2 →   -54 listOfAuthorsWhoSetBadContests.push_back("ReD_AwHiLe")Why such a hard C?
 » 7 weeks ago, # |   -8 You know it's a fair contest when div 1 Candidates have to go through div2 Problem C and D's editorial !
•  » » 7 weeks ago, # ^ |   +1 I dont have any idea how people could solve problem D, the solution for E was expectable, sadly i got stuck in case $n = 3$ for an hour i guess, after all it wasn't a bad contest if it had a little less ad-hoc problems, in fact i say solving problems in this contest needed luck more than coding power and knowledge.
•  » » » 7 weeks ago, # ^ |   0 It was a little modified bubble sort, you have to sort the array. Record all the swaps you can do in one pass, then make those changes, then do the same again. After we have all the operations required. Just distribute them into k groups.
•  » » » » 7 weeks ago, # ^ |   0 I tried this algorithm, but am getting Wa at test case 7 -> submission
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 Here is my submission Let me explain a bit moreWe just have to sort the array. We traverse the array and store the places we can do an operation. Now after we have recorded the possible operations in one pass. Now make those swaps. This way do it n times. Store all the swaps required to sort the array in n arrays. So we store in a vector operations all the operations we can do in the ith pass.At the end, you will have all the swaps that are needed. Thus we also have the operations.size(), which denotes the number of passes required to sort. Let's call this min_operations.Total count of all operations is max_operations needed to sort.Now min_operations <= k <= max_operationsLet's take an example k = 6 string = RRRLLL 1st Pass: 3 2nd Pass: 2 4 3rd Pass: 1 3 5 4th pass: 2 4 5th pass: 1 3 so min_operations = 5 (if we swap all possibilities at once) max_operations = 9 (if we swap one by one)now if k = 6, we divide them into 6 groups instead of 5 I just used greedy for that, I filled them by one by one and k-=1 Until k was equal to the number of groups(indexes left) So we got our final answer. Group 1: 3 Group 2: 2 Group 3: 4 Gruop 4: 1 3 5 Group 5: 2 4 Group 6: 3 Here is my submission for reference. https://codeforces.com/contest/1333/submission/75908994 Can you stop downvoting me now guys. T_T
•  » » » » » » 7 weeks ago, # ^ |   0 Thanks a ton for the detailed explanation! I'm finally able to understand what's happening
•  » » » » » » 7 weeks ago, # ^ |   0 My approach was exactly similar, but couldn't pass TC 7. I guess there was some mistake in the implementation. Thanks a lot, bruh.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 @sonu628 The mistake you have made is you have made the changes while storing the swaps. So in a case like RRRLLL You first swap RR LR LL Then you can again swap here, which is wrong. So we will first record the indexes we can store in an array. And when the inner loop is over, then we make those changes. So you should do something like this Code...  for (int i = 0; i < n; i++) { vector temp; for (int j = 0; j < n-1; j++) if (s[j] > s[j+1]) { temp.eb(j+1); cnt++; } for (auto i : temp) swap(s[i-1], s[i]); if (temp.size()) operations.eb(temp); } Also note that inner loop goes till n-1 now everytime.
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 yeah, saw that after some time. The algo does work, thanks mate finally ac submission
 » 7 weeks ago, # |   +1 I had an off-by-1 error on D, which I noticed a couple of seconds after the contest ended. I haven't felt such frustration in a long time.
•  » » 7 weeks ago, # ^ |   0 Can you discuss your approach to D?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 You can notice that the head turn has the effect of turning a RL into a LR i.e. moving one L one position to the left. It's easy to see now how many moves you have to make (i.e. the number of times you have to move an L to the left, until all L are to the left). Let's call this number needed.The maximum amount of seconds you can have is if you do only 1 move per second, so that is needed seconds. Therefore, if needed is less than K, we have no solution. Then, during each of the K seconds, while needed is still bigger than K, greedily do as many moves as possible. Each move decreases needed by 1. At some point, needed will either become equal to K, meaning you will successfully finish with 1 move per second, OR it will stay bigger until the end, which means there is no solution.
•  » » » » 7 weeks ago, # ^ |   0 It's no were written that if "needed" is less than K, we have no solution.
•  » » » » » 7 weeks ago, # ^ |   0 It says you have to do the process in exactly K seconds. If you only do 1 move per second, you will have needed seconds, and that is the maximum amount of seconds you can have. Therefore, if that maximum number of seconds is less than K, you cannot do it in exactly K seconds.
•  » » » » »