By awoo, history, 8 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: The contest is delayed by 10 minutes.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 341
2 natsugiri 7 362
3 LayCurse 7 387
4 GyojunYoun 7 415
5 Proszek_na_ludka 7 430

Congratulations to the best hackers:

Rank Competitor Hack Count
1 celestialcoder 15:-2
2 dapingguo8 9
3 kamer 6:-2
4 WiwiHo 3:-1
5 FelixArg 4:-3
48 successful hacks and 88 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A bekzhan29 0:01
B LUV 0:08
C H.A.R.D 0:09
D duyenn_khong_ngu 0:32
E dorijanlendvaj 0:45
F bekzhan29 0:36
G Geothermal 0:59

UPD: Editorial is out

• +515

 » 8 months ago, # |   +191 Please, arrange a testing round before this round. If not, this contest will also have possibility to become a unrated contest. Please...
•  » » 8 months ago, # ^ |   +15 hahaha, and it has :) !
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 They must have solved the problem of long queue, so they held the contest. But unfortunately this time website errors made the contest unrated.
•  » » 8 months ago, # ^ |   0 So is it rated?
•  » » » 8 months ago, # ^ |   +2 no it's unrated at last. Poor problem writer, two rounds wasted.
•  » » » » 8 months ago, # ^ |   0 *writers :(
•  » » 8 months ago, # ^ |   +13 have you come from future?
•  » » » 8 months ago, # ^ |   +3 It's a general knowledge. :(
•  » » » » 8 months ago, # ^ |   0 Suprise twist: Abdullah_Sheehan hacked the contest and pretended to have predicted its downfall
•  » » 8 months ago, # ^ |   +10 This aged well
•  » » 8 months ago, # ^ |   +1 @ClCN He didn't "JINX" it, instead it was a good thought ! Would have saved the hard work of the setters ! Its bad to see their work going waste, as we don't even feel like attempting it in live contest now !
•  » » 8 months ago, # ^ |   +35 OP be like "They called me a madman"
•  » » 7 months ago, # ^ |   0 man you are a prophet
 » 8 months ago, # |   0 I wonder how many people are about to wait the LONG queue or to register for tomorrow's contest?
•  » » 8 months ago, # ^ |   +5 Maybe Mike will postpone the contest if the problem is not solved.
 » 8 months ago, # |   0 to MikeMirzayanov I think we need to make one unrated round and then run the rated round. Because it might turn out unrated like round #655. it is unfortunate that round #655 has become unrated but I believe the next rounds won't turn out unrated and I think many other competitors have the same thought as mine. please announce before tomorrow's contest about this contest will be rated/unrated. thanks for reading
•  » » 8 months ago, # ^ |   +3 Seems like we need two unrated rounds before a rated round.
 » 8 months ago, # | ← Rev. 3 →   -7 "Hope the contest will not waste efforts of coordinators. Although codeforces is the best platform but sometimes gives problem 'queue'. Thanks for such a wonderful platform mike.
 » 8 months ago, # |   0 There should be Testing round tomorrow instead of Educational round.
•  » » 8 months ago, # ^ |   0 definitely should have... every time we have to cancel a round we should have a testing round to make sure everything's ok
•  » » » 8 months ago, # ^ |   +3 But fewer people will participate in testing round. Because it will not be rated.
 » 8 months ago, # |   0 hope educational round can't unrated:)
 » 8 months ago, # |   +2 It is really sad to know that contest is unrated especially after waiting for a whole week. Let's hope that no such issue occur during educational round.
•  » » 8 months ago, # ^ | ← Rev. 2 →   -22 .
 » 8 months ago, # |   -47 Waiting for vovuh orz comments!!!!
 » 8 months ago, # | ← Rev. 2 →   +13 I am just curious to know why in some of the contests, the queue is so long even the participant is nearly equal or less than other contests. The load on the server should be the same! (by the way, it really hearts when you are giving the contest skipping dinner and then contest will be unrated).But I can understand It happens sometimes, we can't do much!
•  » » 8 months ago, # ^ |   +1 They must have done some upgrading work which turned out to be buggy.
•  » » 8 months ago, # ^ |   0 Mike said in announcement, "Sorry, because of the long queue the round is unrated. Probably, the reason is the simultaneous combination of several facts: a lot of participants, 5 pretests in task B, a slight degradation in performance after some recent changes. In any case, I will do an investigation". I think it's more because of the changes they did, as there were too many participants in some other contests too, but there wasn't any long queue at that time.
 » 8 months ago, # |   +53 A,B,C solvers never get to use algo knowledge anymore, just a bunch of constructive/pattern/observation C problems everytime. somebody save us.
•  » » 8 months ago, # ^ |   +24 The aim is to strengthen your logical and constructive thinking before moving on to advanced Algorithms, that way it would be easier to visualize how algorithms work and build strong concepts in those. Anyway, that's just my opinion and you may be right on your part too.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 I get your point. I'm just tired of facing the same things. Given a permutation.... maybe I should focus on getting gud so I'd be able to solve interesting problems.
•  » » » » 8 months ago, # ^ |   0 If a problem starts with "Given a permutation", I become very excited and happy :P
•  » » » » » 8 months ago, # ^ |   0 Exactly..i also love permutation problems
•  » » 8 months ago, # ^ |   +3 Lots of problems which have famous algorithms now, were nothing but constructive, pattern, math, and lots of observations based problems 50 years ago
 » 8 months ago, # |   0 Make problem A,B,C somewhat harder otherwise there will be same QueueForces tomorrow.
 » 8 months ago, # | ← Rev. 2 →   -17 I solved 3 questions in the last DIV2 round within 1st hour for the first time and the contest becomes unrated. I know I will do better next time but still, it feels bad.
•  » » 8 months ago, # ^ |   -25 You were even able to submit 3??
•  » » » 8 months ago, # ^ |   -20 yup, though it took 5 5 minutes in B and C to pass all the protests but yeah, I was able to submit A , B and C
 » 8 months ago, # | ← Rev. 4 →   -25 Hope it goes well.
 » 8 months ago, # |   -36 Last time when queues caused problems( with 1-gon's round) mike came up with the Div.4 scam.Time to hold another Div.4 round.
 » 8 months ago, # |   +15
•  » » 8 months ago, # ^ |   +3 Both unrated :(
•  » » 8 months ago, # ^ |   +1
 » 8 months ago, # |   -13 Was sad because today's contest got unrated, but Wohoo! we have one more contest tomorrow!
 » 8 months ago, # |   -8 It looks sad to me that problem setters have to go through problems like what happened in previous round (**Submission pending in queue to be judged**). I am sure that setters want to have people competing in contest the way they usually do. But bcz of queue issue their contest is just destroyed. It definitely takes a lot to write a contest. I really do hope that none of setters contest go through it.
 » 8 months ago, # |   -25 i dont know whether this is correct time to say but despite of long queue problem there is another issue of difference of rating of 3rd and 4th question in recent contests was too large...
•  » » 8 months ago, # ^ |   +13 That was because many left the contest after Mike's announcement. If queue wouldn't have been in picture then I guess the rating of 4th would be near to 1700
 » 8 months ago, # |   -18 Hope to get a great contest today
 » 8 months ago, # | ← Rev. 2 →   +2 Is it possible to tackle queueforces we can judge submissions of unofficial contestant strictly after submissions of official contestant. So it's priority_queue where official contestant are prioritised
 » 8 months ago, # |   -12 after the experience yesterday, it should be re-scheduled.
 » 8 months ago, # |   +4 It would be great if all the educational round problems were Algorithm based, take no offense, just my personal opinion. :)
 » 8 months ago, # |   -20 Queueforces xD
 » 8 months ago, # |   0 i think standing should be freeze for sometime to reduce loading time..
 » 8 months ago, # |   -10 Guys, I have an idea, some of the experienced software developers active on Codeforces should come along and try to volunteer to improve the servers of Codeforces using some means.
 » 8 months ago, # |   -36 Let me tell you a trick to reduce the load. Just midway through the contest make an announcement that the contest is unrated. Then when the contest has ended make it rated. Profit
•  » » 8 months ago, # ^ |   0 And like this you will become red and others won't ! :P
 » 8 months ago, # |   +61 I think this time mike will definitely win <3
•  » » 8 months ago, # ^ | ← Rev. 2 →   -14 [Deleted].
•  » » » 8 months ago, # ^ |   0 Really?......does it make any sense.Do not post shitty memes bro.
 » 8 months ago, # |   +95 I don't understand why people feel this upset about the situation of the long queue. Like what makes people feel that they are entitled to a perfect round when the system is running for the community. You are able to give rounds and practice nice problems without paying a cent. Isn't that enough?
•  » » 8 months ago, # ^ |   +15 Exactly! and the problems which are there in the contest are all new and original with a very basic and tricky idea behind it for atleast A's, B's and C's and even if some round is unrated (which is rare) and people think that their rating would have been increased a lot, they can do it in future contests as well, as they were able to do it now.
•  » » 8 months ago, # ^ |   +4 Lezendary_sandwich I completely agree with you. After all this is the best platform someone can get which can handle 20k users at a time. But times like yesterday come very often here. So people should keep patience. Hope today's round will be a good one.
•  » » 8 months ago, # ^ |   0 Honestly, it'd be pretty cool if we could pay like an annual subscription to CF that gives access to a judge with a smaller queue. Obviously it doesn't work out, since you get a competitive advantage, but still cool.
•  » » » 8 months ago, # ^ |   +11 sounds like leetcode
•  » » » » 8 months ago, # ^ |   0 Does it work well/badly there? I've never competed on leetcode, but it seems like the competition aspect on leetcode not as prominent as CF's is.
•  » » » 8 months ago, # ^ |   +1 I think that could be nice for when upsolving problems or doing virtuals, but I don't usually have problems with the queue at those times. Otherwise yea the pay2win aspect would be pretty lame.
•  » » 8 months ago, # ^ |   +1 I feel really bad for problem setters and problem testers!! :(
 » 8 months ago, # |   0 i hope to face nice ideas and problems as usual
 » 8 months ago, # |   +34 Another contest, another opportunity to my son to win!
•  » » 8 months ago, # ^ |   0 bless me father!!
•  » » 8 months ago, # ^ |   0 that user name tho :)
•  » » 8 months ago, # ^ |   +1 Nice username and profile picture. man, this comment was good lmao.
 » 8 months ago, # |   +7 Make Codeforces Great Again
•  » » 8 months ago, # ^ |   -9 It always great!!
 » 8 months ago, # |   +7 Hoping for no long queues in this contest and I feel unlike the last Div2 ,this contest's B and C will be comparatively on tougher side.
 » 8 months ago, # |   +74 When everybody is talking about queue but no one is talking about stack
 » 8 months ago, # |   +10 Why educational rounds have comparatively very less upvotes than a normal div2 or div1+div2 round.
 » 8 months ago, # |   +36
 » 8 months ago, # |   +12 Delayed :(
•  » » 8 months ago, # ^ |   0 delayed by 10 min (:
•  » » 8 months ago, # ^ |   0 And once again history has been repeated. Mike must be trying to fix the queue problem.
•  » » 8 months ago, # ^ |   +1 Delayed again, by 10 minutes. :(
 » 8 months ago, # |   0 Codeforces needed to run an unrated round before starting educational round
•  » » 8 months ago, # ^ |   0 I think 10 minutes delay is better that that.
•  » » » 8 months ago, # ^ |   +1 If 10 minutes delay solve the problem then sure, but how can they know?
•  » » 8 months ago, # ^ |   +24 An unrated round before this Educational round ran last day xD Codeforces Round #655 (Div. 2)
•  » » 8 months ago, # ^ |   -6 not unrated but div 4 maybe,many people won't give an unrated round.
 » 8 months ago, # |   -50 Delayforces into action again! Fucking irritating it is :)
•  » » 8 months ago, # ^ |   -6 You don't have to use slang to express yourself
 » 8 months ago, # |   +67
•  » » 8 months ago, # ^ |   0 Oh man! Waiting is so annoying
 » 8 months ago, # |   +11 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 8 months ago, # |   +24 Seems like codeforces is in trouble.
 » 8 months ago, # |   +29 I can already see where its going.
 » 8 months ago, # | ← Rev. 2 →   +24 Each time a contest is delayed by 10 minutes, adrenaline of thousands of participants goes straight to the flush. edit: GG codeforces lol.
 » 8 months ago, # |   -22 It's too late in my country now and my mom started annoying cause my "bedding" :v
 » 8 months ago, # |   +38 anyone else facing bad gateway?
•  » » 8 months ago, # ^ |   0 yeah me too, so annoying
•  » » 8 months ago, # ^ |   +1 Yeah. I am getting. No point of giving contest and taking risk.
•  » » 8 months ago, # ^ |   0 Me too
•  » » 8 months ago, # ^ |   0 Yes, I guess mike has blocked other pages like profile, etc.
•  » » 8 months ago, # ^ |   0 i am getting the same thing too
 » 8 months ago, # |   +60 502 Bad Gateway is coming
 » 8 months ago, # |   0 make codeforces not queueforces
 » 8 months ago, # |   0 why am I getting "502 Bad Gateway" error before the contest
 » 8 months ago, # |   +35 Please delay the contest. Make the server prepared. Don't screw author's efforts
•  » » 8 months ago, # ^ |   +22 why didn't they delay it if it's clear there's a problem now the round is probably not rated again
•  » » » 8 months ago, # ^ |   0 Ask Mike
 » 8 months ago, # |   0 Switch to m1.codeforces.com
•  » » 8 months ago, # ^ |   +8 Also giving 500 error code
 » 8 months ago, # |   +3 500 Internal Server Error...
 » 8 months ago, # |   +46 quite sad to see it happening again , the problemsetters' hardwork is kinda gone to waste again.
•  » » 8 months ago, # ^ |   0 yes , another problemset wasted
•  » » 8 months ago, # ^ |   +3 If all problem statements (except A) were locked/hidden at the start of the contest, then the problemsetters' work wouldn't necessarily have to go to waste. Even if some technical difficulties were to arise during the round, some problems could still be used in the future, since no contestant would've seen them. We could make it so, that each successive problem becomes visible/unlocked, once at least one of the participants has solved the preceding one.What do you think of my stupid proposal?
•  » » » 8 months ago, # ^ |   0 I was able to see first three problems on m2.codeforces . So ,there are definitely more people who did. Btw ,It will be better ,if they publish editorials now .
•  » » » » 8 months ago, # ^ |   0 I wasn't talking about what happened in this specific contest, but rather suggesting a way to change the rules, so that problems only gradually become "unlocked". I was able to see A, B, and C, on m3.codeforces.com too, but there is no way to guarantee, that there wasn't some lucky person who could read all problem statements. Therefore, if a situation like this were to repeat itself in the future, there would be no way of knowing, which problems could still be used in future rounds, unless my proposal was implemented.
 » 8 months ago, # |   +1 Is it still rated?
•  » » 8 months ago, # ^ |   0 I don't think so. :(
 » 8 months ago, # |   0 What's going on?
 » 8 months ago, # |   +33 Codeforces!
 » 8 months ago, # |   +49 My son is crying...
•  » » 8 months ago, # ^ |   +11 I am so sorry for him :(
 » 8 months ago, # |   0 Did they not realise that everyone was facing bad gateway ?
 » 8 months ago, # |   +6 Classic Codeforces
 » 8 months ago, # |   0 UnratedForces!
 » 8 months ago, # |   +7 I think contest could have delayed bit more or held tomorrow after fixed bug. All the efforts of setter go in vain.
•  » » 8 months ago, # ^ |   0 yes,they should have seen this coming and postponed the round,would have saved everybody's time and effort
 » 8 months ago, # |   0 "Unfortunately, the round is unrated."Ah shit! Here we go again!
 » 8 months ago, # |   +9 That's why we need daily contests XD
 » 8 months ago, # |   0 Unrated, right?
 » 8 months ago, # |   0 Unfortunately, the round is unrated.*Fortunately
•  » » 8 months ago, # ^ |   +8 Unfortunately for setters and management, fortunately for us
 » 8 months ago, # |   +3 UNRATED
 » 8 months ago, # |   0 Not Again :(
 » 8 months ago, # |   +114 ...
•  » » 8 months ago, # ^ |   0 ???
•  » » » 8 months ago, # ^ |   +22 having PTSD..
•  » » 8 months ago, # ^ |   +1 Monogon be like- First time ?
•  » » 8 months ago, # ^ |   0 Next is your's contest.
•  » » 8 months ago, # ^ |   0 Lol atleast yours will get postponed.Let's hope history shall not repeat itself.. Looking forward to your contest!
 » 8 months ago, # |   +8 It's almost like people predicted the round would have been unrated if not postponed. There was no way these issues could have been fixed overnight...
 » 8 months ago, # |   +27 It makes sense to ask "Is is rated?" before contests..
 » 8 months ago, # |   0 WTF, back to back to unrated contest!
 » 8 months ago, # |   +8 I feel bad for awoo and his efforts :(
 » 8 months ago, # |   +44
 » 8 months ago, # |   0 People were right there should have been an unrated contest before the actual contest.Feeling bad for the problem setters.
 » 8 months ago, # |   -19 I think this is done by rival competitive coding sites like leetcode, atcoder, codechef, they are attacking website.... just opinion.
 » 8 months ago, # |   +1 This even worse than yesterday's round
•  » » 8 months ago, # ^ |   0 I disagree with you :-)Atleast we were able to submit today and get the instant result.what happened yesterday was worst because u just submitted the code and you dont know weather it is AC or not even after waiting more than 10 min!!
 » 8 months ago, # |   0 Is it the first time there were two back to back unrated contests? If so, we need to reconsider the direction we are heading to.
 » 8 months ago, # |   +3 A. Yet another wasted problemset
•  » » 8 months ago, # ^ |   0 Not for you, just go and submit now :-)
•  » » » 8 months ago, # ^ |   0 Of course I will do that but solving problems during rated contest gives more fun and it's a chance to change rating
 » 8 months ago, # |   +31 Before July 2020: This contest is unusual to have an unusual starting time.July 2020: This contest is unusual to be rated.
•  » » 8 months ago, # ^ |   0 Sad :(Wish headquarters can fix it ASAP :)
 » 8 months ago, # |   -6 Unrated again!! :(
 » 8 months ago, # |   +44
 » 8 months ago, # | ← Rev. 5 →   +3
 » 8 months ago, # | ← Rev. 2 →   -42 No excuse this time, MikeMirzayanov. You knew since yesterday this could've happened and you chose to do nothing about it.UPD: I did a poor choice of words with this comment, I know it's not true that Mike did nothing about the issues on the platform. I do believe there were a lot of alternatives which could've prevented the round from being ruined, and none of them was taken. I stand by that. But I didn't want to offend Mike, or diminish the efforts he constantly does for the community.
•  » » 8 months ago, # ^ |   +18 What makes you think he wasn't trying to fix this the whole time? Never assume, and be grateful of their hard work.
•  » » » 8 months ago, # ^ |   +16 Facts: The platform failed yesterday. This round could've been postponed. A testing round could've been held to avoid this. Setters and testers' weeks of hard work were ruined. Something very similar happened in Round 639. One would expect the CF team learned something about it, but here it is again. I've always been grateful to CF, I've even donated so they could keep up and improve, which apparently you haven't done. And I didn't say Mike didn't try to fix this. But he couldn't fix it, and I think there's no excuse this time, considering all the options he had.
•  » » » » 8 months ago, # ^ |   0 The part that stood out to me in your first message was "you chose to do nothing about it". I don't think either of us knows the exact specifics of why cf failed today, but i'm pretty sure Mike thought this round would run successfully, or he would have postponed it.I'm not saying he made the right decision, and I'm not arguing that you did not donate money. I agree with you on many points. I just don't think it's fair to say he chose to do nothing about it. Just wanted to make that clear.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 I didn't say Mike didn't try to fix this You literally said "you chose to do nothing about it".All your "facts" only make sense with the assumption that yesterday's issue reoccurred and precisely that issue was the cause for today's outage. You also have to assume that it was the same issue as in round 639, then, for some reason it went away, and then reappeared yesterday.How does this even make any sense? Have you really thought this through before commenting?What makes you think it was the same issue? You realize that there are multiple things that can go wrong on the website, right? It doesn't even make sense as the first guess: the failures were different — yesterday there were queues, today the website didn't load itself you've been on this website since at least 2017 — do you really not have any trust in CF's team that they did their best to prevent yesterday's the issue? After 2+ years on the platform, the first thing that comes to your mind is "chose to do nothing about it"? Really? Is this consistent with your experience so far?
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   +8 Facts: Long queue and inability to enter the site are different problems.
 » 8 months ago, # |   +18 we can somehow make the entire codeforce infrastructure as open source and ask more participant to contribute, optimize, improve its overall quality and performance.While enjoying the high quality contest, it is also important to maintain the infrastructure itself together.
 » 8 months ago, # |   -9 DeadForces :-)
 » 8 months ago, # |   0 I feel sad for setters.
 » 8 months ago, # |   0 i don’t know whats wrong,site was facing problem before the start of contest yet they allowed contest to happen they should have postponed for 20 more minutes and if it didn’t improve the situation then contest should have been held tomorrow surely waste of efforts of setters.
 » 8 months ago, # | ← Rev. 2 →   -10 I Hope, Everything will be ok from next round!!
•  » » 8 months ago, # ^ |   0 Ha ha ha
 » 8 months ago, # |   0 All we need is Hope
•  » » 8 months ago, # ^ |   0 True
 » 8 months ago, # |   0 Ahh, test 7 killed me.
 » 8 months ago, # |   0 Any hint regarding test 7 in D ?
•  » » 8 months ago, # ^ |   0 Same, can't find anything wrong for 1 hour.
•  » » 8 months ago, # ^ |   0 It is sometimes optimal for you to take one Fireball, and all others Berserk
•  » » » 8 months ago, # ^ |   0 I took care of that, can you give any test-case ?
•  » » » » 8 months ago, # ^ | ← Rev. 5 →   0 No I don't have any test case but I have 3 cases which needed you need to solve:If left or right element from subarray is greater than maximum in subarray: Take all Berserk If length of subbaray is greater or equal than k: Take as much Fireball as you can Take one Fireball, and all others Berserk Take minimum of those 3, if those 3 cannot be achieved, than it's -1
•  » » » » » 8 months ago, # ^ |   0 Silliset mistake I have made, didn't took care of the garbage values.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 13 3 4 3 1 2 9 3 5 8 10 7 4 1 6 10 11 12 2 6 12 Maybe check this TC, ans = 11, to my knowledge
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 Edit: Ok, sorry my mistake, 11 is the correct answer!
 » 8 months ago, # |   0 What's the test 7 for D
 » 8 months ago, # |   +19 The problems were good!!!
 » 8 months ago, # |   0 How to solve D?
•  » » 8 months ago, # ^ | ← Rev. 12 →   +8 In order to reduce array A to B, B first needs do be a subsequence of A. Then, when this condition is checked there is always a solution, and here is how to achieve it with minimal cost. For every consecutive B[i] and B[i+1], we need to delete elements from A in the range [pos[i]+1 , pos[i+1]-1] where pos[i] represents the position of element B[i] in the array A.It is clear that if pos[i]+1 = pos[i+1] then the cost for this part is 0 otherwise let m be max value of array A over the range [pos[i]+1 , pos[i+1]-1] and nb = pos[i+1]-pos[i]-1 (number of elements in the range). If nbmax(B[i],B[i+1]) then we can not use only Bersek we need to use one Fireball at the end so the cost will be (nb-k)*y+x - else we can use only Bersek and the cost is nb*y In order to deal with elements before pos[1] and after pos[m], I've added 0 at the beginning and the end of both array A and B. Here is my submission 86697447.
•  » » » 8 months ago, # ^ |   0 For the case nb>=k clearly we need to reduce nb elements to the biggest multiple of k and destroy the rest using Fireballs Can you please explain it in detail , I couldnt thought of how to optimally pick elements as there could be lot of ways. Thanks
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 yeah, ofc. Well we know that it is more optimal to use one Fireball then to use k Bersek which means k*y < x holds. However, we can't only use Fireballs because nb is not guaranteed to be a multiple of k and we will have some elements left in the end. So instead of directly using Fireballs we will reduce nb to biggest multiple of k smaller than nb using Berseks and then we will employ Fireballs. More formally, the cost will be $(nb\mod k)*y + \lfloor{\frac{nb}{k}}\rfloor*x$.
•  » » » 8 months ago, # ^ |   0 Isn't it possible that when you reduce nb to the biggest multiple of k, that you could not use Bersek to destroy the remaining warriors? Namely, you end up with m greater than B[i] and B[i + 1]
•  » » » » 8 months ago, # ^ |   +1 when reducing nb to the biggest multiple of k we are only using Berseks to achieve that. Keep in mind that we can always do it by picking an element in the range which has a smaller element adjacent to it. Then, we will use $\lfloor{\frac{nb}{k}}\rfloor$ fireballs to destroy the remaining warriors.
•  » » » » » 8 months ago, # ^ |   0 Oh, that's correct. During the contest, I thought of using Fireball before Berseks; that's why it got complicated for me.
 » 8 months ago, # |   +3 Problems were really good, infact the difficulty of question B was greater than C until u get the trick. Also D was little tricky if u don't consider all the cases carefully. Lets hope we see a rated round soon.
•  » » 8 months ago, # ^ |   0 Pls explain your idea of D.
•  » » » 8 months ago, # ^ |   0 First check if B is a subsequence of A, if not then we can't produce an answer.For converting A to B we need(provided B is a subsequence of A) to delete some of the segments/fragments in A which are not there in B, for that you can see the my below comments:
•  » » » » 8 months ago, # ^ |   0 Didn't read your explanation(I want to first try on my own) but I got stuck on the test case: what if array_a = [1,3,4,2], array_b = [1,2], k = 3? I'm stuck there. We can't delete [3,4](since k is 3) and if we delete 3 using 4 then it becomes [1,4,2]. Am I missing something?
•  » » » » » 8 months ago, # ^ |   0 For the above test case we won't be able to convert A to B because:-> size of segment to delete < k so we can't use x mana i.e first type of operation.-> We can use second operation for completely deleting the fragment only when either of adjacent element > maximum element in fragment, but in ur case max(3,4) > 1 and 2 so we can't completely delete all the elements in the fragment using second operation.
 » 8 months ago, # |   0 How to solve E?
•  » » 8 months ago, # ^ |   0 There must be some way to implement the simulation efficient. Note that the ans foreach move is the number of segments of consecutive rings.Then, whenever two towers get merged, some of the consecutive segments get merged to one segment, ans is decreased by one for each such merge.But my solution TLEed.
•  » » » 8 months ago, # ^ |   +3 We can do this by keeping track of the current number of differences between consecutive elements. Every time we merge, some differences will get eliminated. We just need to keep track of how many get eliminated per merge. To do this, keep track for each tower, at what indexes it occurs in the array. For instance in the sample, the array is 1 2 3 3 1 4 3. Then the sets would be: Tower 1: 0, 4 Tower 2: 1 Tower 3: 2, 3, 6 Tower 4: 5 Now when you merge two towers, this is equivalent to merging the two sets corresponding to those indices. This can be done in O(log n) amortized by using the small to large merging method. For example, after we merge towers 1 and 3, the sets will become: Tower 1: Tower 2: 1 Tower 3: 0, 2, 3, 4, 6 Tower 4: 5 You also need to know how many changes between consecutive elements in the original array are eliminated. This can be computed by iterating through the smaller set, and adding 1 for each element in the larger set that is 1 away from this element in the smaller set. In this case the 4 from Tower 1 and the 3 from Tower 3 are the only ones next to each other. This means we must subtract 1 from the current count of differences.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +1 In my first submit I tried to use vectors, and made a new vector out of a and b every time. Then I tried to use sets, but it seems I did buildin some bugs, all TLE.However, of the solutions I studied so far I like most the one from icecuber, 86686544 which does what you explain above in nice code.
 » 8 months ago, # |   +1 My video editorial for B . I have tried to explain my thought process and why the algorithm worked hope you like it .
 » 8 months ago, # |   0 What is wrong with this approach for D?I first checked if B was a subsequence of A. After this, I fragmented A into parts (each fragment was between two such positions, such that the corresponding numbers were the same for A and B, that is to say, where A and B matched. After this, I greedily calculated mana required for each fragment.
•  » » 8 months ago, # ^ |   +1 To greedily calculate mana required there will be two case:-> If the maximum element there in the fragment to be deleted is larger than the adjacent elements to that fragment then we must use x mana to delete the k elements in the fragment containing that maximum element also, for the remaining element in the fragment you can than greedily compute the cost. Note: In this case if size of fragment < k then there won't be any possible answer. -> If the maximum element there in the fragment is smaller than either of the adjacent element then you can greedily compute the cost to delete all the elements in fragment(there won't be restriction like we had above)
 » 8 months ago, # | ← Rev. 2 →   0 I don't understand why my solution for D gives TLE on test 6. 86694208
•  » » 8 months ago, # ^ |   0 Never mind, I got AC. It was a stupid variable placement.
 » 8 months ago, # |   +5 Thanks for the contest anyway, I liked the problems.Now, what about the tutorial? I see no reason to hold it back any longer.
 » 8 months ago, # |   0 The problemset was really good! kuddos to the problemsetters !!
 » 8 months ago, # |   0 How to solve Problem E?I even don't understand the sample: [[5,1],[2],[7,4,3],[6]] ---> [[2],[7,5,4,3,1],[6]][[5,1],[2],[7,4,3],[6]] ---> [[5],[2],[7,4,3,1],[6]] ---> [[5,4,3,1],[2],[7],[6]] ---> [[],[2],[7,5,4,3,1],[6]] 3 steps is ok! why the answer is 5 ?
•  » » 8 months ago, # ^ |   0 Whenever two consecutive rings lay onto each other they never get separated again. And in the end, it must be one consecutive segment.So ans is always the number of consecutive segments of rings, minus one.When towers get merged, some of those segments get merged, too, ans decreases by that number of merges.
 » 8 months ago, # |   +44 It was hard for me to understand that you can reorder the chests in G.
 » 8 months ago, # |   0 the problems were very nice specially E.In E we can use dsu.But sad that contest is unrated
 » 8 months ago, # |   -8 My video editorial for problem C . I have tried to explain my thought process and the algorithm . Hope you like it .
 » 8 months ago, # |   0 I have doubt of max and min function. Here is my code for A 86697535. I used one while loop with max function and it gives TLE. As I understand testcases loop is 10**2 while loop is of 10**3 and max function takes 10**3. And 10**8 is valid for 1sec, then why I got TLE. please help, Thank you
•  » » 8 months ago, # ^ |   +1 You see that such a triple is available at every local maxima, it is in your code.  c = g[i-1] d = g[i] e = g[i+1] So just iterate the array once checking every position it if is such a triple. If yes print it and break/return.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 Hey spooky, I read your submission after getting WA on D still could not figure out where I am making a mistake. 1. I check if v2 is a subsequence of v1, if not then answer is not possible. 2. I am destroying all segments between the elements. If there is a segment where we have an element which is greater than the starting and ending point of that segment, at least once we should use Power X, else we can use cheaper of Power X or Y. If we are unable to use Power X (segment length is less than K) then answer is not possible. 3. I am destroying all segments from starting to first element in v2, and from ending to last element in v2. Here is a link to my submission: https://codeforces.com/contest/1380/submission/86702514 Any help is much appreciated as always!
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +3 Again, as soon as I made this comment I found out my mistake like the last time. Anyway, your solutions are very helpful! Thank you.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +4 Note that p1 is out of bound here, but that seems not to be the reason for WA.  while(p1
 » 8 months ago, # |   +4 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 3 →   +10 On problem G, for the second sample case, can someone explain what configuration of mimic chests gives 7/8 as the expected value for having 6 mimics? I must be misunderstanding some part of the problem but I've read this several times now and I can't see how you can achieve a better EV than 8/8 for 6 chests (by making the chest 3 and either chest 5 or 8 real, and the rest mimic, giving us 1/8*(3+5)). I have a feeling that I could be misunderstanding, and perhaps the optimal strategy is to make chests 2 and 3 real, but from what I understand, this would give an EV of 1/8*((4+3)+3)=10/8.I don't want to read the editorial or other people's code since I actually want to try solving the problem, but I've been bashing my head about this for quite a while.EDIT: Oh, I now understand cookiedoth's comment above about reordering the chests. The order that they are given in the problem is NOT the order they have to appear in the circle. That's pretty confusing. I think what makes it particularly confusing is that you refer to rooms using i and then in the next sentence still refer to the chests using i, almost implying that they correspond to the same thing.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 You can reorder chests. I also was having problems with understanding the sample tests. But after 20 minutes I finally understood it.
 » 8 months ago, # |   -8
 » 8 months ago, # |   0 I am not being able to optimize my O(n^2) idea in E. Help?My idea. For each query, the answer is the number of change of towers from 1 to n. In every query, we can just merge the two sets by iterating the set elements and find out answer by looking through the array.
•  » » 8 months ago, # ^ |   0 if yo u merge small set to large set then solution is o(nlog(n))...proof
•  » » » 8 months ago, # ^ |   0 Wow, didn't know this technique before. Do have any other sources to learn this and practice problems.
•  » » » » 8 months ago, # ^ |   0 you may go to this blog practise ..dsu on tree
•  » » » » » 8 months ago, # ^ |   0 Thanks.
 » 8 months ago, # |   +10 Is D based on magic the gathering? If so what inspired what berserk and fireball do as in the problem statement (they both do something quite different in mtg)?
•  » » 8 months ago, # ^ |   +18 No, initially there were Lightning Bolt (killing exactly one target) and Berserk (I don't know why Roms chose those spells, probably based on HoMM III). But that problem was considered to be too easy, so we changed the Lightning Bolt to kill several targets at the same moment and chose a random AoE spell to name it
•  » » » 8 months ago, # ^ |   +10 Oh, that's cool.I have an idea for a problem now that also uses a fireball and berserk spell, but that do something different xD
 » 7 months ago, # |   0 I am unable to find mistake in my code of div 2 problem D ( code )