### Devil's blog

By Devil, 3 years ago,

Hello, Codeforces!

I'm very glad to invite you to the first Cuban round Codeforces Round #659 (Div. 1) and Codeforces Round #659 (Div. 2) which will take place on Jul/24/2020 17:35 (Moscow time).

All problems in this round were created and prepared by mnaeraxr, gilcu3, dcordb, jcg and me. We tried to make them interesting and diverse and hope that you will enjoy them!

You will be given 2 hours to solve 6 problems in both divisions, and we highly encourage you to read all of them :)

We would like to thank:

The score distribution will be announced shortly before the round (or earlier).

UPD: Here is the score distribution:

Div2: 500 — (500 + 750) — 1750 — 1750 — 2500 — 2500

Div1: 1000 — 1000 — 1750 — 1750 — 2000 — 2250

Good luck and have fun!

UPD: The editorial is ready Editorial

UPD: Congratulations to the winners!

Especially for tourist, Benq and Radewoosh who solved all the problems!!!

Div. 1:

Div. 2:

• +732

| Write comment?
 » 3 years ago, # |   0 I hope for an interesting first cuban round :)
•  » » 3 years ago, # ^ |   +43 This round was not at all interesting.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +150 It looks like someone forgot to mention that the contest was for Russian 5th to 8th graders. (No offence intended). Anyways, this just makes it more exciting. Thanks for this round.
•  » » 3 years ago, # ^ |   +86 New round to avoid : Cuban Round
•  » » 3 years ago, # ^ |   0 It became really interesting when I tried submitting the first problem and not to mention, when I started reading Problem B.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 I became depressed after reading problem A & B also C
•  » » » » 3 years ago, # ^ |   +41 C was the real saviour
•  » » » » 3 years ago, # ^ |   +6 I was like A will never left me but today A left me.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +98 Who is this Koa the Koala and why does she want to cross the shore?
•  » » » 3 years ago, # ^ |   +76 Google's first result for "can koala swim?" "Koalas drown in swimming pools when they are looking for water to drink. Although koalas can swim, if there are no assisted ways for a koala to climb out they will eventually drown."
•  » » 3 years ago, # ^ |   +41 did someone forget this was a coding round and not a reading round?
•  » » 3 years ago, # ^ |   0 why is everyone downvoting because of the contest... :(
•  » » 3 years ago, # ^ |   +14 I started reading the first problem , and before i could even see the test cases , the round was over...
•  » » » 3 years ago, # ^ |   +6 I suggest improving your reading comprehension before trying a competition. Good Luck!
•  » » 3 years ago, # ^ |   +1 I would rather do Eva than doing these problems
•  » » 3 years ago, # ^ |   +9 Score for B1 should be more than C. Currently B1 score is significantly low than that of C. And every one knows the level of these 2 questions.
•  » » 3 years ago, # ^ |   +21
•  » » 3 years ago, # ^ |   0 After seeing too many Red coders as testers, we should prepare ourself for such a lengthy, disordered(e.g. problem B and C order) round.
 » 3 years ago, # |   -82 Shitty memes incoming!!!!!!
 » 3 years ago, # |   -44 Lol you are from Havana University
•  » » 3 years ago, # ^ |   -12 What's lol about that?
 » 3 years ago, # |   -16 what is cuban round ?
•  » » 3 years ago, # ^ |   +32 The authors are from Cuba.
•  » » » 3 years ago, # ^ |   -22 oh.
•  » » » 3 years ago, # ^ |   0 This comment is downvoted. So i can assume my answer is wrong. People who are downvoting can you please tell me what is the correct answer? I really want to know.
•  » » 3 years ago, # ^ |   -34 The authors are from Kuban
•  » » » 3 years ago, # ^ |   -59 No, the authors are from Cuba
•  » » » » 3 years ago, # ^ |   -94 No. the authors are from Kuba.
•  » » 3 years ago, # ^ |   +51 a bad round
 » 3 years ago, # |   +302 As a tester, I finally get to make one of these posts.
•  » » 3 years ago, # ^ |   +101 [gets contribution]
•  » » » 3 years ago, # ^ |   +68 [gets contribution]
•  » » » » 3 years ago, # ^ |   +23 xD
•  » » » » » 3 years ago, # ^ |   0 exit(0);
•  » » » 3 years ago, # ^ |   -45 [gets contribution
•  » » 3 years ago, # ^ |   0 as a participant, your tester post sucks
 » 3 years ago, # | ← Rev. 4 →   -55 This comment was downvoted by trolls
•  » » 3 years ago, # ^ |   +78 Come with me sir, we're gonna find out who tf asked.
 » 3 years ago, # |   +73 Last time with this much red coders, we saw something dangerous.
•  » » 3 years ago, # ^ |   +12 we should have seen it coming
 » 3 years ago, # | ← Rev. 2 →   -92 When last contest is rated and you want another contest to participate in and you are happy and confused at the same time!!!:
•  » » 3 years ago, # ^ |   0 What is the story behind this image btw?
•  » » » 3 years ago, # ^ |   0 I put this image, cause there is a happinnes and confusion at the same time, like my feelings
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   -48 okay
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +46 Everyone using this platform should know about him. :P He is MikeMirzayanov
 » 3 years ago, # |   +56 Will it be IQ test round? I like IQ tests.
•  » » 3 years ago, # ^ |   +424 As a tester, I can confirm you need a brain to solve these problems.
•  » » » 3 years ago, # ^ |   +56 Writing 'As a tester' was really important for that confirmation :p
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +56 MagentaCobra How much problems did he reject this time xD :)
•  » » » » 3 years ago, # ^ |   +112 I'm pretty sure he rejected ~15 problems
•  » » » » » 3 years ago, # ^ |   +19 After the contest can we have the rejected problems for practice?
•  » » » » » » 3 years ago, # ^ |   +436 No, they are recycled to be rejected in next contest again.
•  » » » 3 years ago, # ^ |   +29 After the contest, I was convinced that I have no brain :(
•  » » » 3 years ago, # ^ |   +5 Man...I should have read this before the contest:(
•  » » » 3 years ago, # ^ |   +3 As a human being, I can confirm that everyone has a brain smh.
 » 3 years ago, # |   +103 As a tester, I’m glad I tested.
•  » » 3 years ago, # ^ |   +15 Seems like we are again going to have round 657 with less than few hundreds people solving C
•  » » 3 years ago, # ^ |   -8 [Enjoy your contribution] .
•  » » 3 years ago, # ^ |   0 As a participant, I should've known what you were saying.
•  » » 3 years ago, # ^ |   +62 Now we know what happens when DEVIL himself wishes Good luck)
 » 3 years ago, # |   +30 There is an amazing team behind this contest. I'm looking forward to participate. Good rating everyone
 » 3 years ago, # |   +74 As a non-tester, I'm glad that I'll be able to participate in it <(")
•  » » 3 years ago, # ^ |   +1 So, how did the contest go for you ? XD
•  » » » 3 years ago, # ^ |   0 My ratings didn't go down, so it was good I guess :\
 » 3 years ago, # |   0 So happy
•  » » 3 years ago, # ^ |   +1 Still holding to this opinion after the contest? ¯_(ツ)_/¯
•  » » » 2 years ago, # ^ |   0 It's irony, the contest is so happy, it's like yesterday's contest.
 » 3 years ago, # |   +11 Imagine getting back from retirement for a Cuban round, writers are all amazing. Looking forward to it, see you in the standings, altho I prolly don't pass a,b :). Удачи
•  » » 3 years ago, # ^ |   +4 This round makes me want to retire.
 » 3 years ago, # | ← Rev. 2 →   +13 The Div1 part of the contest is shown in Calendar on saturday, too. I think this is not intentionally.
 » 3 years ago, # |   +6 We still remember the last red round
 » 3 years ago, # |   +9 After a long time Um_nik became as a tester. I hope this round will be great.
•  » » 3 years ago, # ^ |   +7 Fake news
 » 3 years ago, # |   +13 It's a good opportunity for me to become PUPIL again :)
•  » » 3 years ago, # ^ |   +8 Or maybe become Expert B)
•  » » 3 years ago, # ^ |   0 well, you don't bacame pupil :)
 » 3 years ago, # |   +37 Congratulations! :)
 » 3 years ago, # |   +44 Yes, i have heard of Cuban. Krasnodar is the best city.
•  » » 3 years ago, # ^ |   +55 No no no, not that Cuban. This Cuba
•  » » » 3 years ago, # ^ |   +29 Why do you downvoting me? That was just a joke. Of course i know what cuban means. Why do you upvoting some captain obviousness who didn't get the joke and tried to "explain" me what Cuban is?
•  » » » » 3 years ago, # ^ |   +16 Some people just don't get sarcasm, man. I upvoted you and am glad that your comment is now receiving upvotes too.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -26 .
 » 3 years ago, # |   +53 Div2 ACount the number of peaks in the rating graph of dcordb
•  » » 3 years ago, # ^ |   +4 WA on pretest 2
•  » » 3 years ago, # ^ |   +137 Div1 FCount the number of peaks in the rating graph of ruban
•  » » » 3 years ago, # ^ |   +51 Time Limit Exceeded on pretest 6
•  » » 3 years ago, # ^ |   +7 I wish this was div2A instead of the real one.
 » 3 years ago, # |   -23 As a participant, I am all scared looking at so many Reds
•  » » 3 years ago, # ^ |   +4 You were right.
 » 3 years ago, # | ← Rev. 2 →   +3 You can do it! who want to become green, blue, ...
•  » » 3 years ago, # ^ |   +14 Who can do what?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 you can become red
 » 3 years ago, # | ← Rev. 2 →   -69 Ok
•  » » 3 years ago, # ^ |   +14 shut up!!
•  » » » 3 years ago, # ^ |   -18 Your DP says that you stopped caring a long time ago then why is it bothering you. Everything gonna be alright!
 » 3 years ago, # |   +3 Very excited for my first contest! I have covered all the basic data structures in past 1 month . Now I am looking to take part more frequently . Any suggestions on how to be consistent and any further resources ??
•  » » 3 years ago, # ^ |   +8 Bad Luck ! You chose the wrong contest.
 » 3 years ago, # | ← Rev. 2 →   +5 In codeforces round When I submit the problem and it gets pretests passed in very first submission. Ooh that feelings can't explain in words. When I am writing this I am crying with smiling face
•  » » 3 years ago, # ^ |   +4 I think you haven't experience that feeling when you submitted it WA 10 times and the 11th time is got Pretest passed. Literally crying with smiling face.
 » 3 years ago, # |   +26 As a tester, I wish every participant good luck and high rating on this (very nice) round!
 » 3 years ago, # |   +8 I Hope Cuban round will be as good as Cuban Cigar. :)
 » 3 years ago, # |   +47 A very interesting score distribution!
•  » » 3 years ago, # ^ |   +16 score and difficulty level no match at all !
 » 3 years ago, # | ← Rev. 2 →   +116 Perfectly balanced, as all things should be
•  » » 3 years ago, # ^ |   +10 Hmmmmmmmmmmmmm.
•  » » 3 years ago, # ^ |   0 Now again
 » 3 years ago, # | ← Rev. 2 →   +60 ( ° ͜ʖ °)
•  » » 3 years ago, # ^ |   +168 He should have waited for CF round #666.
•  » » » 3 years ago, # ^ |   +57 How about we reserve CF Round #666 to be held on 13th November, 2020 (Friday the 13th) and ask Devil to hold it?
•  » » » » 3 years ago, # ^ |   +28 Only 7 contest in 4 month? I will lose my sanity
•  » » » » » 3 years ago, # ^ |   +3 Maybe we can try "some" educational rounds!
•  » » » 2 years ago, # ^ |   0 Round 666 is coming up :)
•  » » 3 years ago, # ^ |   +22 lets make it 666 again
•  » » 3 years ago, # ^ |   +5 The cursed contest.
 » 3 years ago, # |   +9 Wait, do we have subtasks in div2(asking because of the score distribution/and that it isn't mentioned)
•  » » 3 years ago, # ^ |   0 I suppose because in the format given like (750 + 750 ) suggests so
•  » » 3 years ago, # ^ |   0 It is written there will be 6 problems, so I think (500+750) => B1 and B2, B1 being subtask:)
 » 3 years ago, # |   +1 I think that you should also author the seventh round following this one.
 » 3 years ago, # |   +14 hello darkness, my old friend
 » 3 years ago, # | ← Rev. 2 →   +6 Will Tourist top the tables today??
•  » » 3 years ago, # ^ |   +4 Yeah.
 » 3 years ago, # |   +16 Hope,this first cuban round will be very interesting :D
 » 3 years ago, # | ← Rev. 2 →   +2 Interesting score distribution! GL & HF!
 » 3 years ago, # | ← Rev. 5 →   -12 ups
 » 3 years ago, # |   +11 A sub-task for B? This is going to be wild.
 » 3 years ago, # |   +66 My schedule this summer,EAT -> PARTICIPATE IN CF CONTEST -> READ EDITORIAL -> SLEEPREPEAT
•  » » 3 years ago, # ^ |   +6 ohh...which country are you living here it is rainy !!
•  » » 3 years ago, # ^ |   0 Same!
•  » » 3 years ago, # ^ |   0 CF has keeping me sane for the summer
•  » » 3 years ago, # ^ |   +4 you forget one part: LOSE RATING
 » 3 years ago, # |   +3 good luck to you ！！！
 » 3 years ago, # |   +5 MikeMirzayanov Just curious to ask when running 2 contests (Div1 and Div2) you use the same server fot both the contests or 2 different servers (with Div1 having less specification server because of load)
 » 3 years ago, # |   +2 Another Anton Round!
 » 3 years ago, # |   -6 tourist registered for the contest, I think he'll take his position today!
 » 3 years ago, # | ← Rev. 2 →   -7 i am having 1940 rating. and I don't want it to decrease for next 2 month so just wondering if someone can tell me how much maximum rank can ensure me 0 decrease? like any idea? is around 1000 fine
•  » » 3 years ago, # ^ |   +15 There is a way:copy code and get "skipped".But your account might be blocked
 » 3 years ago, # |   +33 .
•  » » 3 years ago, # ^ |   +64 The meme is as hard to understand as solving Div.1F
•  » » » 3 years ago, # ^ |   +42 You mean div2A?
•  » » 3 years ago, # ^ |   +9 incase anyone didn't get the meme carefully read the second line of the announcement! See HereI'm very glad to invite you to the first Cuban round Codeforces Round #659 (Div. 1) and Codeforces Round #659 (Div. 2) which will take place on Friday, July 24, 2020 at 20:35UTC+6.
 » 3 years ago, # |   +99 The new strategy to decrease server load is working!
 » 3 years ago, # | ← Rev. 2 →   +21 Seems Red Coders doesn't think of beginner coders !!
 » 3 years ago, # |   +19 Again a Div1 type contest :(
 » 3 years ago, # |   +10
•  » » 3 years ago, # ^ |   +41 Applicable to Div1 participants after solving A and B as well
 » 3 years ago, # |   +32 Glad I didn't submit even a single code!
 » 3 years ago, # |   +1 div2 feels like div1 :(
 » 3 years ago, # |   +144 Last contest was such a class. Back to unnecessary complicated questions. All problem setters should learn something from Monogon and Ashishgup.I know I am going to get downvoted to hell, but needed to get the truth out.
•  » » 3 years ago, # ^ |   +26 +1,I love Monogon's problem and this contest is quite bad.Some of Ehab's math problem are also good.
•  » » » 3 years ago, # ^ |   +1 Second that! mohammedehab2002 is my favourite setter, and Monogon is close second!
•  » » 3 years ago, # ^ |   +5 Since ^ comment is getting some attention, I want to add if we can come up with a way to voice our opinion about the round? Maybe upvote/downvote a contest or individual problems? I am not against harder problems but there's a difference between good kind of hard and bad kind of hard.
 » 3 years ago, # | ← Rev. 2 →   +4 UPD: Figured what was wrong on pretest 3. Sorry for spreading hate.
 » 3 years ago, # |   0 I'm a newbie. I didn't even understand the questions.
•  » » 3 years ago, # ^ |   +6 It's Okay. Nobody did.
 » 3 years ago, # |   +8 my confidence is indirectly proportional to length of questions
•  » » 3 years ago, # ^ |   +11 My confidence is directly proportional to length of questions. I cannot solve and more people cannot solve.
 » 3 years ago, # |   +37 Reading div2 B1-B2 problems is more difficult than doing a plank.
 » 3 years ago, # |   +48 Worst score distribution i have ever seen in Codeforces!!!
 » 3 years ago, # |   +6 Div-2 contest doesnt seem to a div-2 type.No balance in problems at all.
•  » » 3 years ago, # ^ |   +3 Seems like that was the case for Div1 as well
 » 3 years ago, # |   +13 Looks like Devil's plan at work here.
•  » » 3 years ago, # ^ |   +1 Plan of unexpected statements!
 » 3 years ago, # |   +18 If the frequencies of these types of contest increases, it will inculcate the feeling of fear in beginners' mind towards competitive coding. No offense to anyone.
 » 3 years ago, # |   -10 you asked for harder questions, so there you go :P
•  » » 3 years ago, # ^ |   +2 who the hell asked for it? <(")
 » 3 years ago, # |   +60
 » 3 years ago, # |   +27 Me after reading Div2 A, B1, B2:
 » 3 years ago, # | ← Rev. 3 →   +18 Not worth complaining about the difficulty of the problems. Just improve next time and learn from your mistakes.
 » 3 years ago, # |   +19 Do not trust someone whose account name is Devil
 » 3 years ago, # |   +30 Kudos to all problem setters and team. What a contest. I realized that need to learn more practice more.
•  » » 3 years ago, # ^ |   +11 There are better ways to learn that fact.
 » 3 years ago, # |   0 i was able to solve the first one phewwww!
•  » » 3 years ago, # ^ |   0 That's an achievement. Not kidding at all. You should be proud of yourself. I am unable to figure out where my code is failing for past one hour.
•  » » » 3 years ago, # ^ |   -9 Ok, so here it is: link
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 However the contest is. It is rated or unrated you must not share any solution during contest.
 » 3 years ago, # | ← Rev. 2 →   -31 [Deleted]
•  » » 3 years ago, # ^ |   +17 politics
 » 3 years ago, # |   +53
 » 3 years ago, # |   +123
 » 3 years ago, # |   +135 Another difficulty staircases
•  » » 3 years ago, # ^ |   -37 Yeah, and I bet most of users solved problem B by guessing solution, not even having proof...
•  » » » 3 years ago, # ^ |   0 You'd bet that but you'd be wrong. If you actually could guess the solution, then it wasn't too hard to prove three or four cases.
•  » » 3 years ago, # ^ |   +10 In my opinion
 » 3 years ago, # | ← Rev. 2 →   +5 I thought WA on pretest 2 sucks the most, but today I learnt, WA on pretest 3 sucks the most. Getting WA on pretest 3 in C :(Nvm I removed an if case and it worked. :)
 » 3 years ago, # |   +27 tourist returns to #1 !!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 (Oh, now it won't be broken.)
•  » » » 3 years ago, # ^ |   +9 Except tourist himself.
 » 3 years ago, # |   +4 Wait... Has Codeforces increased the difficulty of Div.2???
 » 3 years ago, # |   +63
 » 3 years ago, # |   +120 <
 » 3 years ago, # |   +26 The language of Div.2 B1 was very bad. :(
 » 3 years ago, # |   +52
 » 3 years ago, # | ← Rev. 2 →   0 I happy for tourist, he will return to it's normal position :) tourist
•  » » 3 years ago, # ^ |   +12 You should not add someone's handle unnecessarily
 » 3 years ago, # |   -44 Monogon's Div.1 contest was MUCH better than today's contest. problems were unbalanced and Div.1 B was terrible problem...
•  » » 3 years ago, # ^ |   +20 Why do you think div 1 B was a terrible problem?
•  » » 3 years ago, # ^ |   +35 wtf? Div1B was a really nice problem imo.
•  » » 3 years ago, # ^ |   +10 Div 1B was pretty interesting in my opinion.
•  » » 3 years ago, # ^ |   0 If Div1B was terrible, then please come and read Div2B1 (and B2).
 » 3 years ago, # |   +28 TFW you not only fail to solve div1A, but can't understand why your solution to div1A is wrong.
•  » » 3 years ago, # ^ |   +3 Same! But I suppose I'm somewhat relieved/surprised to see a grandmaster say this! No offense ofc.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +34 aabb xyxy I still have no idea how to solve that problem, although something did pass pretests eventually. Had to move to more trivial problems like E instead :)
•  » » » 3 years ago, # ^ |   0 Go through all letters in increasing order. For each letter, get the minimum of letters that this letter needs to be converted to (lets aabb — xyxy: a converts to x and y, take the smaller one), then convert all the letters (a) to the lexicographically smaller one (x or y) (note you need to skip letters that are already ok).
•  » » » 3 years ago, # ^ |   0 What do you mean?For that one it's  aabb bbbb xbxb xyxy (according to my code + my manual attempt)
•  » » » 3 years ago, # ^ |   +5 So the transitive reduction of a DAG isn't a subgraph?
•  » » » » 3 years ago, # ^ |   +8 Transitive reduction requires that there is a path from a to b if and only if there was a path from a to b in the original graph. This problem doesn't have the "only if" requirement.
•  » » » » » 3 years ago, # ^ |   0 24 (Dadgum.)I thought that adding more edges can't hurt the number of operations...
•  » » » 3 years ago, # ^ |   0 Acc. to my code, aabb->xxbb->xxxx->xyxy
•  » » 3 years ago, # ^ |   0 Yes! Me too. WA on pretest 3...
•  » » 3 years ago, # ^ |   0 I also had a wrong pretest 3 at first and then I implemented a (in my mind) equal solution in a different and it worked lol (solution is back down). What I did it first was: go through letters in increasing order, if a letter is not good then convert it to a letter that also exists and needs to be converted to the same letter (ignore if it's already good, convert directly only if there are no such cases). Idk why this approach is any different than my other, could be just a program error since it's a bit more complex.
•  » » 3 years ago, # ^ |   +3 I spent two whole hours battling pretest 3, only to no avail.
 » 3 years ago, # |   +46 It feels like the contest is based on some olympiad for students of 5-8 grades
•  » » 3 years ago, # ^ |   -7 at least there were interesting problems
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 PTSD intensifies
•  » » 3 years ago, # ^ |   0 what do u mean. is there similar tasks or what?
•  » » » 3 years ago, # ^ |   +7 That round was extremely tough for a Div2, people were joking about how skilled Russian 5-8 grade students must be to solve it. Now this round has somehow managed to be even tougher.
•  » » 3 years ago, # ^ |   +3 Normal Div2 round: Kalm
 » 3 years ago, # |   +11 I have a strange question. Who is Koa the Koala?
•  » » 3 years ago, # ^ |   +33 And why is it ruining my div2?
•  » » 3 years ago, # ^ |   +9 the devil himself.
 » 3 years ago, # |   +27 Kind request to stop such bullshit Div2
 » 3 years ago, # |   0 lol, there was a duplicate test case in problem B. ~~~~~ 5 2 3 1 2 3 2 2 ~~~~~
•  » » 3 years ago, # ^ |   +4 I was unable to reach sample test case left the problem after reading the problem statement only.
 » 3 years ago, # |   +47
•  » » 3 years ago, # ^ |   +1 Then how about the REAL CF Round #659 div1? Say, div0?
•  » » » 3 years ago, # ^ |   0 No, In div1, we are crowd in div1 standing!
 » 3 years ago, # |   +17 bad problems , bad statements . didn't enjoyed this contest .
 » 3 years ago, # |   -9 This contest is not worth 2 hours of 20k Div-2 participants.
 » 3 years ago, # |   +30 thanks antontrygubO_o for amazing coordination of this round.
•  » » 3 years ago, # ^ |   +6 Now I am wondering about him antontrygubO_o. He didn't even realize about the problem statement of $Div2B$. F.
 » 3 years ago, # |   0 Anybody else having had problems opening the page of their room?
 » 3 years ago, # |   +3 Devil $2B$, Devil $1C$.Devil Statement, Devil difficulty.
 » 3 years ago, # |   +16 Can someone explain why this idea gives WA3 in Div2-C / Div1-A?If any letter needs to be changed to an alphabetically smaller one, output -1.Otherwise, build a directed graph (e.g. a matrix) where graph[a][b] = 1 iff we need to change a to b at least one index, ab is unnecessary iff there is another path with more nodes that connects a and b. Note that the path will contain strictly shorter (in the alphabetic sense) edges, so we can start with an empty graph and add edges of alphabetic difference 1, 2, 3, ... 19, at each point checking that the letters are not already connected.The answer is the number of edges in the final graph. I have no idea what I'm missing.
•  » » 3 years ago, # ^ |   0 i did the same thing, WA on tc 3.
•  » » 3 years ago, # ^ |   0 So on the test AB, DC you will print 3, because A->B->C->D, right?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +1 My answer is 2. The original graph does not contain a->b or c->d, and I only ever remove edges.Edit: Okay, I see it. The entire problem is that I only remove edges. For example, in aabb -> cdcd the optimal solution is to turn aabb -> bbbb and then two more operations. My solution prints 4 because it cannot add the edge a->b.
•  » » » » 3 years ago, # ^ |   +12 Ah ok, AABB CDCD, the answer is 3, because AABB->CCBB->CCCC->CDCD
•  » » » 3 years ago, # ^ |   0 shouldn't it be 2? coz A -> C and B -> D ?
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 Got it
•  » » 3 years ago, # ^ |   0 aabb cdcd
•  » » 3 years ago, # ^ |   0 I did something weird, but it passed pretests somehow... basically ignore the fact that the graph is directed, answer = 20 — number of connected components.
•  » » 3 years ago, # ^ |   0 this problem can be solved by a simple dfs finding number of vertices in every component.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 infxx Can you please elucidate? I tried something similar but it didn't work. 87922305The major difference I see is that you are making the graph undirected(right?). Why so?
•  » » 3 years ago, # ^ |   0 Norrius What is the fix for this approach?
•  » » » 3 years ago, # ^ |   0 It's really easy: just find the sizes of (undirected) connected components with DFS/BFS, let's say they are $c_1, ..., c_k$. Then the answer is $\sum_i (c_i - 1)$, because there is some spanning tree in each of the components, and you know how many edges a tree has.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 I don't quite get the intuition behind this fix? Like, how did you get to this? And why does that work? I get this idea that we need to find the minimum spanning tree(taking all edges' weight as 1) for our original directed graph(but there's an issue in it). But I do not get it that how making the graph undirected solves our issue?
 » 3 years ago, # |   +374
 » 3 years ago, # |   0 wellThat was different
•  » » 3 years ago, # ^ |   +1 each participant's state during contest was exactly like your profile pic ...
 » 3 years ago, # | ← Rev. 2 →   +5 For Problem D in div 2., can we solve the problem for each bit independently?Edit: NVM I just proved it to my selfProof: if you have an odd number of bits, set at a particular position for all numbers in the array, the winner will be decided in this round Other wise you have an even number of bits, and your opponent will get the same result as you for that bit position.
 » 3 years ago, # |   +48 1384B1 - Koa and the Beach (Easy Version) is my new favorit of shittiest problem statement ever.
•  » » 3 years ago, # ^ |   +3 Pictures would have helped.
•  » » » 3 years ago, # ^ |   0 And some other story, mayby one which makes some sense or none at all... I needed to ask twice before understanding that the girl cannot swim if the water is to deep. How can somebody come up with such wired picture? This is simply the opposite of logic. I mean, why?
•  » » 3 years ago, # ^ |   0 Yeah, adding "More formally, " just made it harder to understand.
 » 3 years ago, # |   +67
 » 3 years ago, # |   +3 Too time-consuming when reading Div2B problem :))
 » 3 years ago, # |   +91 So laughy to hear, when problems are nice in easy contest, and bad in hard contets. LOL. bad != hard.Problems were cute && hard, div2 guys just cant solve them and find it is bad && want unrated — it is so stupid && two-faces
•  » » 3 years ago, # ^ |   0 The problems were pretty good, it's just the fact that C was a lot easier than B in div2 (You can look by yourself). I find B as a very nice problem, but it took me more than 15 minutes to understand the statement.
•  » » » 3 years ago, # ^ |   +17 Yeah, you are right. I am just angry about people who wrote that problems were bad and shitty
•  » » » » 3 years ago, # ^ |   +9 I understood you. I'm also finding this annoying. If you understand the statements of the problems, they are enjoyable (in my opinion). I just hope that in the future, the authors will write the statements more concisely and the problems will go in increasing difficulty.
•  » » 3 years ago, # ^ |   0 Finally a really accurated opinion. I left this community two years ago, when i retired from regionals. Now two years without basically coding at all, i return for the first cuban round, and i managed to solve A, B1, C and get a positive score given by the fact that when i retired there were approx 4000-6000 participants per round in Div2. I found out that now there are nearly 20k, but 16k of them at least, only know to cry about problems that a retired person can solve with 0 warn up, thanks so much codeforces, for leaving me this bad memory as about the first round written by my country.To the person who i'm replying, really my most sincere congratulation, for not being one of those crying babies. Thanks!
 » 3 years ago, # |   0 Anyone else with wrong answer on pretest 3 in C? What was it??? :/
•  » » 3 years ago, # ^ |   +1 me :(
•  » » 3 years ago, # ^ |   +1 I guess that was the first real test with many test cases. Test 2 contained some corner cases I think
•  » » 3 years ago, # ^ |   0 Same here. Not sure what it was, but I know I did not handle a case like: aabb cdcd (Answer should be 3: converting a->b, then b->c and b->d)
 » 3 years ago, # |   0 C was DSU or DFS/BFS/ Spanning Tree loved solving it <3;
•  » » 3 years ago, # ^ |   0 It was easy greedy. You overkilled it. Can you briefly say about dsu solution?
•  » » » 3 years ago, # ^ |   +3 I converted all conversions into the form of A to B in a directed graph if at the end of all conversions character A was required to be converted into B . Now if A>B then always answer is "-1" , this is self explanatory. Now I added all the edges to the graph , if A-->B , Now any successful completion or conversion can can be done efficiently if for every pair A to B to which conversion is required we follow exactly one path and no more than that , this conversion can be seen as path from node A to node B in the graph. Now for a connected components if we want minimum paths to follow and connect all characters which are need to be converted into one path, we need to find just a spanning tree of the obtained graph. Thus we can obtain it easily using any technique like BFS/DFS/DSU . Thus it was a good problem of Spanning tree, I think. May be I over-killed it. Consider the small case graph where aab-->bcc A->B , B->C, A->C. since the spanning tree of above graph will be A->B->C , which is minimum possible answer for this conversion process.
•  » » » » 3 years ago, # ^ |   +1 Wow, that's an elegant approach. Thank you :)
•  » » » » » 3 years ago, # ^ |   0 Yours Welcome , What is the greedy approach by the way.
•  » » » » » » 3 years ago, # ^ |   +1 Created a directed graph.Then I traversed from the character 'a'. Assuming our current character is 'C'th.Using one operation, I changed all character 'C' to the minimal character over all his sons, and now add the new childs to the minimal character.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 AM_I_Learning What is wrong with my solution 87922305?
•  » » » » 2 years ago, # ^ |   +1 Very interesting approach, thanks for sharing.
•  » » 3 years ago, # ^ |   0 Can you please share your approach
•  » » » 3 years ago, # ^ |   0 replied above you may check it!
 » 3 years ago, # |   -101 Time for antontrygubO_o to resign. What a disaster.
 » 3 years ago, # |   +6 In my opinion Div 2 C (Div 1 A) was waaaaaaaay easier than Div 2 B.
 » 3 years ago, # |   +8 New type of contest to avoid : Cuban Round
•  » » 3 years ago, # ^ | ← Rev. 2 →   -6 derji v kurse, zachem ty napisal ob etom 100 kommentov lol?
 » 3 years ago, # | ← Rev. 2 →   +62 Div2D/Div1B solution is really nice:Notice that for a given bit, if it occurs in an even number of elements, then the players will either both have this bit in their sums or both not have the bit (either both have an odd number or both have an even number of the bit) regardless of the actions taken in the game. Thus, we can look for the highest bit that occurs with odd frequency. If there is no such bit, then it must be a draw. Someone will have this bit in their sum, and someone else will not, and the other bits do not matter since this is greater than the sum of all the lower bits.So, if we call this bit b, then we can replace all of our numbers with either 1 or 0 depending on whether or not they have bit b. Now we simply need to solve the case where there are only 0's and 1's in our array, which is left as an exercise to the reader.
•  » » 3 years ago, # ^ |   0 It wouldn't help me, unfortunately. I got almost all the conditions. I've checked if the number of 1's equals 1 instead of count % 4 == 1. I just considered 1 and 3 and did not notice that for 5, the first person also gets the odd number of elements...
•  » » 3 years ago, # ^ |   0 But I just stuck in how to solve 0-1 array!!!Please tell me!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +6 First, think about the case with no 0's. Who wins if there is just one 1? Three 1's? Five 1's?Now, add a single 0. How does that change things? How about a second? A third?
 » 3 years ago, # |   -14 bad contest with long statments
 » 3 years ago, # |   +10 Nice way of reducing the load of the server and taking care of the long queues :P
 » 3 years ago, # |   +23 I feel lucky for div.1 participants for not having to solve such B.
 » 3 years ago, # |   +164 Awesome problems! From which AtCoder round did you steal E?
•  » » 3 years ago, # ^ |   0 Jajaj thanks. It is nice to hear some good feedback. We (setters) are really glad you like the problems.
 » 3 years ago, # |   +100 I think I finally kinda understand people who whine about terse (few details) editorials. Yesterday I tried to solve AGC 027 E. I found an easy classification about what intervals we can compress into a single element and what the result of that compression is. But I failed to come up with the DP that would count the subsequences.Today I see 1383E - Strange Operation which is obviously very similar (basically, rules about collapsing intervals are simpler). I decide to read the editorial of 027E in the hopes that the DP might be similar. And what do I find from the editorial? "We can count such $t$ by a simple DP. This solution works in $O(\left|s\right|)$ time." (end of editorial) In other words "lol that's trivial" :/
•  » » 3 years ago, # ^ |   0 That's one sure way to make us solve the exercises "left to the reader", just put them in another contest, right? Can you give a hint to the idea for problem E? I've observed that no zeros from different contiguous components can be in the final string, but I couldn't find a way to count all possible final strings beyond the multiplication when we don't delete any 1's.
•  » » » 3 years ago, # ^ |   +5 In the end I'm not sure how much a more detailed editorial would have actually helped.Yeah it's basically "count # of distinct subsequences" with that restriction (and some additional fiddling with initial and final zeroes, which is too tedious to think about). For each subsequence let's count only the "leftmost".Suppose you have just ended a block of 1-s and would like to add a block of $k$ 0-s to your subsequence. Then you move find the first block of 0-s that's at least $k$ long and jump to the end of that.Suppose you have just ended a block of 0-s and would like to add a block of $k$ 1-s to your subsequence. Then you simply take the next $k$ 1-s in the original string and jump to that position.If you build a DP based on that you get $O(n^2)$ complexity, but it's relatively easy to optimize from there.
 » 3 years ago, # |   -8 Were pretests strong ?
•  » » 3 years ago, # ^ |   -14 Noooo...A had weak pretests...got WA on test 15 in system testing...this has to be one of the worst contests in recent times...
•  » » » 3 years ago, # ^ |   0 Owie :(
•  » » » 3 years ago, # ^ |   0 yeah same here wrong answer on test 22 xD
 » 3 years ago, # |   0 Now I am eagerly waiting for someone to upload a video editorial of B and C and comment here !!!
 » 3 years ago, # | ← Rev. 3 →   +13 Don't know why but I thought 5 1 1 1 1 1 is "LOSE" in div1B for the whole contest :)
 » 3 years ago, # |   +2 what the hell was test case 3 for Div2 C ?
•  » » 3 years ago, # ^ |   0 Not certain (I didn't get C, but know one reason mine probably failed on it), but I bet it was something like: aabb cdcd Optimal is to convert a to b, then b to c and b to d, for 3 moves. I know I was still converting a-c,a-d,b-c,b-d.
 » 3 years ago, # |   +19 Don't you think the Div.1 difficulty gap is terrible?
 » 3 years ago, # | ← Rev. 3 →   +3 in Problem D I added the following if statement 1.5 minutes before the end and it worked and i was ecstatic XD Spoilerif (cnt - 1) % 4 == 0: return 'WIN' I really hope my Python won't TLE because there was a point I thought the pretests didn't pass because I didn't have enough bits so I went all the way up to 50 (even though 30 is enough). So I spend 20*n work for no reason what so ever and it just might cause TLE (on python it's super sensitive).EDIT: It didn't TLE! But it was sure close. one pretest was 936ms XDDD
 » 3 years ago, # | ← Rev. 2 →   -13 DIV 2 A before: You have to come up with somethingDIV 2 A now: You have to write a long implementation
•  » » 3 years ago, # ^ |   +1
•  » » 3 years ago, # ^ |   +14 What are you talking about? it was like 11 lines of code and I was wasteful. I only used the letters 'a' and 'z'. You just have to use the last string, copy it until the prefix length, and add 'a'/'z' depending on situation.Python solution: Spoilerdef solution(a,n): res = ['a'*50] for i in range(n): x = a[i] if x== 50: res.append(res[-1]) continue temp = res[-1] char = res[-1][x] char = 'a' if char == 'z' else 'z' res.append(temp[:x]+char+temp[x+1:]) return '\n'.join(res) 
•  » » 3 years ago, # ^ |   0 Usually there was nothing to come up for in past rounds.
 » 3 years ago, # |   +7 Another Russian olympiad for students of 5-8 grades :D.
 » 3 years ago, # | ← Rev. 2 →   +17 Highly Undistributed Difficulty Level (Div2)The Ranks of Participants who solved only A lie from 2745->infinite.It was FastSolveProblemA Forces. And was someone like me who made a wrong submission on A and faced -50 penalty,it was like like Facing the Real Devil.Ranking dropped down Dead.We need better adjusted ProblemSets.Ciao Rating !
•  » » 3 years ago, # ^ |   0 don't worry bro you are not alone.
 » 3 years ago, # |   +7 I wanted to drown myself trying to solve div2B
•  » » 3 years ago, # ^ |   0 LOL you killed xD
 » 3 years ago, # |   +7 Damn! this round was soo tough than normal div 2 rounds
 » 3 years ago, # |   +3 Bring back the good old days when DIV-2 was actually DIV-2.
 » 3 years ago, # |   0 How is B1 easier than C, also why is points for B1 not even one third of C ?Such a long statement for B1. B1 should atleast be of 1000 points.
 » 3 years ago, # |   -16 tourist comback Top rated
 » 3 years ago, # | ← Rev. 2 →   +10 My idea for div1CLet's make a directed graph G with 20 vertices (= letters) and edges from v1 to v2 if v1 needs to be changed to v2. Then we need to get a topological sorting S for G. Since it contains loops, pick the smallest possible set of vertices which are parts of any loop (so that if we remove these vertices, all the loops will be broken), put them in front of S, delete their inbound edges and sort the rest of the graph.The answer will be size(S) — 1.I don't know how to find loops in a directed graph and how to find that set of vertices :/
•  » » 3 years ago, # ^ | ← Rev. 4 →   +10 Hm, I'm not sure I totally understand your solution, but maybe something similar would work with condensation SCC graph? I tried to think of something like that but couldn't make it work.EDIT: Actually, I read your idea more closely. Wouldn't this imply that on the complete graph the answer is 19 when it should be 39 (I think)?I had a feeling there might have been some solution involving bitmasks since $|\alpha| = 20$ rather than 26.