### djm03178's blog

By djm03178, history, 2 months ago,

오랜만이에요, 코드포스! (Long time no see, Codeforces!)

I'd like to welcome all of you to Codeforces Round #688 (Div. 2)! The contest will start at 04.12.2020 16:05 (Московское время), and it is rated for all participants with ratings under 2100. Note the semi-unusual start time.

You will be given 6 problems and 2 hours and 15 minutes to solve them. The score distribution will be announced soon.

All problems are prepared by me, with a lot of help from the testers making me realize that my solutions are dumb.

Thanks to Green55, JooDdae, cs71107, YeongTree, DreamingLeaf, jh05013, Lemonade255, 39dll, alswhp, Ku_Top, sonjaewon, slah007, jooncco, and rkm62 for testing the round, and especially xiaowuc1 for helping polish English statements as well. I would also like to thank 300iq for round coordination, and MikeMirzayanov for the great Codeforces and Polygon system.

See you in the round!

UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3500.

UPD 2: The round is finished. Thanks for your participation! I'm sorry about underestimating the difficulty of problem B, but I hope you still enjoyed the problems! The editorial will be posted in a minute.

UPD 3: The editorial is out!

UPD 4: Congratulations to the winners!

Div. 2

Unofficial Div. 1

2: jiangly

3: neal

4: saketh

5: Pyqe

• +757

 » 2 months ago, # |   +313 As the problemsetter, I want comments!
•  » » 2 months ago, # ^ |   -96 djm03178 orz....
•  » » 2 months ago, # ^ |   -27 G.O.D
•  » » 2 months ago, # ^ |   +5 Ok I commented as per your wish.
•  » » 2 months ago, # ^ |   -49 So yummy~~
•  » » 2 months ago, # ^ |   -7 comments
•  » » 2 months ago, # ^ | ← Rev. 2 →   +60
•  » » 2 months ago, # ^ |   +31 As a participant, I will give you upvote.
•  » » 2 months ago, # ^ |   0 As a participant, upvoted and commented :)
•  » » 2 months ago, # ^ |   -24 // cout << "Hi" << endl;
•  » » 2 months ago, # ^ |   -27 sir make sure to add some or atleast a dp problem between A-D.
•  » » » 2 months ago, # ^ |   0 the problems have bet set a long time ago. So I think this is not possible.
•  » » 2 months ago, # ^ |   0 I hope it is a good contest :D
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -11 same i also hope it be like the educational 99
•  » » 2 months ago, # ^ |   +30 As a tester, I wish I could participate in this round as this round is very well prepared by djm03178. Good luck to all the participants!!
•  » » » 2 months ago, # ^ |   0 rkm62, I see your name as a tester in many contests. As a CP enthusiast, can you please let me know what can I do to be a tester?
•  » » » » 2 months ago, # ^ |   +12 You need to know the problem setters (to get asked) or take part in many CF contests (to be asked by Mike if the problem setters cannot find enough testers).Hope it helps.
•  » » » » » 2 months ago, # ^ |   0 Thanks a lot! Sadly, I don't really know any of the problem setters. I guess I'll have to wait patiently and hope Mike asks me sometime in the future.
•  » » » » 7 weeks ago, # ^ |   +3 Theirs a pretty big discord server where a lot of people hang around. Imo it's the best place to get to know problem setters and probably ask to be a tester. Just remember to not be so annoying ;)
•  » » » » » 7 weeks ago, # ^ |   +3 Can you pls share the discord group link or the process so that I can join. Thanks
•  » » » » » » 7 weeks ago, # ^ |   +1 I forgot to include the link lol https://discord.gg/algorithms
•  » » 2 months ago, # ^ |   -14 Why is there so many downvoted comments .
•  » » 7 weeks ago, # ^ |   0 hii sir big fan sir!! :")
•  » » 7 weeks ago, # ^ |   0 yes
•  » » 7 weeks ago, # ^ |   0 Dude C was easier than B... at least for me. I litterary wasted 2 hours trying to solve B. Props on C though pretest 1 is very helpful to skip a ton of mistakes.
•  » » 7 weeks ago, # ^ |   0 yes... you got my comment as you are problem setter. thanks a lot. this round was awesome
 » 2 months ago, # |   +64 As a tester, Please enjoy problems!
•  » » 2 months ago, # ^ |   +28 why is this getting downvotes lmao
•  » » » 2 months ago, # ^ |   +32 Even when I saw that comment first time, it already got about 70 downvotes, which made me surprised.
•  » » » 2 months ago, # ^ |   +8 When I first saw this comment it got more than 70 downvotes and I didn't know why... To tell the truth, I haven't seen such kind of comments being downvoted before.
•  » » 2 months ago, # ^ |   +12 As a tester, I think he deserves upvotes. He did a great job as a tester.
 » 2 months ago, # |   +24 Wow.. I'm looking forward to participate in this round!
 » 2 months ago, # |   0 Korean Round!
 » 2 months ago, # |   +47 Is it rated?
•  » » 2 months ago, # ^ |   -11 I think so
•  » » 7 weeks ago, # ^ |   +1 Yes
 » 2 months ago, # |   +11 Amazing writers Amazing testers and Amazing coordinator i wil remember the day 2020 December 4 forever.
•  » » 2 months ago, # ^ |   0 It's my ex-girlfriend's birthday on that day... Should I wish her excitedly, normally or not at all? The only thing I'm excited about is the contest and a little bit about the INDIA-AUSTRALIA cricket match.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +55 Then several cricket match is given and they have distinct costs and happinessUnfortunately, I only participate k match among themWhat is the best strategy I maximize the girlfriend's happiness and then minimize the costs I spendWow amazing problem!
•  » » » » 2 months ago, # ^ |   -17 It's pretty simple, girlfriend's happiness index will always be zero no matter what algorithm you apply in your life :(
•  » » » 7 weeks ago, # ^ |   +12 Everyhing can be "normal" again if you wish her "excitedly".Gd luck buddy go ahead.
 » 2 months ago, # |   +7 Another Korean Round! This round will be amazing!
 » 2 months ago, # | ← Rev. 2 →   0 WOW i cant stand it
 » 2 months ago, # |   -18 This round is sexy.
•  » » 2 months ago, # ^ |   +50 Algosexual?
 » 2 months ago, # |   -34 팬이에요 :fan:
 » 2 months ago, # |   +45 Hope they dont give out a contest full of "interesting observations" problems.
•  » » 2 months ago, # ^ |   +160 I hope they give out a contest full of "interesting observations" problems.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +50 i hope they give out a contest full of "INTERESTING" problems
•  » » » » 2 months ago, # ^ |   +9 I hope they give out a contest full of problems
•  » » » » » 2 months ago, # ^ |   +16 Queue problems, statement problems, editorial problems...
•  » » » » » » 2 months ago, # ^ |   -19 Problem problems..
•  » » » 2 months ago, # ^ |   +1 big fan sir :)
 » 2 months ago, # |   +9 꼭 참가하겠습니다!(I will participate in this competition!) :god: :fan:
•  » » 7 weeks ago, # ^ |   -13 안녕하세요? 한국에 이사이트같은 것 없어요?
 » 2 months ago, # |   0 please don't make it like educational round 99 !
•  » » 2 months ago, # ^ |   +13 Please make it like educational round 99 so that we can see where we falter and keep learning new things!
•  » » » 2 months ago, # ^ |   -7 but i think a contest after 688 should be like round 99 then the real testing of what we learned new will be checked
•  » » » 2 months ago, # ^ |   -7 Agreed.
•  » » 2 months ago, # ^ |   0 Yes
 » 2 months ago, # | ← Rev. 5 →   0 Wait.... A negative rating tester??? Thats something new
•  » » 2 months ago, # ^ |   +54 A negative-rating tester whose atcoder rating is more than 2000 :D
 » 2 months ago, # |   0 Hope contest will bring some new learning
•  » » 2 months ago, # ^ |   +8 Increase in ratings too.
 » 2 months ago, # |   +3 Oh friendly time for Chinese! But we Chinese will have a important contest (NOIP) right after this, hope for good luck after all!
 » 2 months ago, # |   +29 May the pretests be strong!
 » 2 months ago, # |   0 Where the difficulties of problems in Codeforces round 685 and other?
 » 2 months ago, # |   0 unusual start time
 » 2 months ago, # |   +1 Hope to see some interesting problems with short statements and strong pretests :)
•  » » 2 months ago, # ^ |   0 hoping that queue should also be fast not as that of previous two contests !!
 » 2 months ago, # |   0 Looking forward to solving some amazing problems. :) //Hope I can solve more than 2 this time XD
 » 2 months ago, # |   -8 The contest will start at Friday, December 4, 2020 at 18:35UTC+5.5.Most Important Note the unusual start time.
•  » » 7 weeks ago, # ^ |   +12 Learnt a new lesson "Don't remind anything if it is already posted on Contest blog". Thank You.
•  » » » 7 weeks ago, # ^ |   -9 too late now
 » 2 months ago, # |   0 Oh， time is more friendly than others
 » 2 months ago, # |   -14 I will participate in this contest.
 » 2 months ago, # | ← Rev. 2 →   -9 한국 시간 고려해서 semi-unusaul start time으로 맞춰주신 거 감사합니다! Thanks for considering Korean time!
 » 2 months ago, # |   -28 Is it rated?
•  » » 2 months ago, # ^ |   -12 It's already mentioned in bold. Should they just write it in the announcement heading for you?
•  » » » 2 months ago, # ^ |   -18 Yes
 » 2 months ago, # |   -11 Why semi-unusual start time and not unusual? :thonk:
 » 2 months ago, # |   -10 Normal People be like, 'Hey' , 'Hi', 'Hello'.... and @djm03178 be like, "오랜만이에요, 코드포스! (Long time no see, Codeforces!)"...that's pretty cool and badass at the same time. ;)
 » 2 months ago, # |   -22 Can I get contribution without posting a meme
•  » » 2 months ago, # ^ |   +69 I'll take that as a No
•  » » » 7 weeks ago, # ^ |   0 And I'll take your both comments as meme again ..lol
 » 2 months ago, # | ← Rev. 3 →   0 Hope a Great contest
•  » » 2 months ago, # ^ |   +16 Why I am getting downvote. what's wrong
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +19 How do you know that contest is great before it even started ?Upd : This was a reply to his previous comment he edited the comment after that.
 » 2 months ago, # |   0 hope to become green
•  » » 2 months ago, # ^ |   0 I hope to become cyan
 » 2 months ago, # |   +1 t's very sad that on the day of the round there is an RMI and I won't be able to raise the rating :(
 » 2 months ago, # |   +11 i hope this time queue should be fast not as previous two contests !!
 » 2 months ago, # |   0 (Long time no blue, Codeforces!)
 » 2 months ago, # |   0 Plot twist-Early announcement was made just to get more upvotes.
•  » » 2 months ago, # ^ |   +1 How is it a plot twist XD XD
•  » » » 2 months ago, # ^ |   0 Expectation is that early contest announcements would get everyone hyped.
 » 2 months ago, # |   +14 hmmm strange 1-gon hasnt put any comment yet.
•  » » 2 months ago, # ^ |   +13 Yeah it's cause he's a lil caught up with planning his "As a setter..." comment for the next contest.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 1-gon's father knows it all. LOL.
 » 2 months ago, # |   0 Hope this time we don't have to wait too much time for the rating.
 » 2 months ago, # |   -57 코드포스 is the wrong spelling
•  » » 2 months ago, # ^ |   +42 That's how Koreans call Codeforces in Korean communities.
 » 2 months ago, # |   0 I hope the problems will more enjoyable than last round .
 » 2 months ago, # |   -27 Notice the unusual timing.
•  » » 7 weeks ago, # ^ |   -21 My first comment on Codeforces only getting downvotes. Noice :)
 » 2 months ago, # | ← Rev. 5 →   -26 Now my contributions are in negative :D
 » 2 months ago, # |   0 Hope I could solve A and B in time. Thnx for the contest.
 » 7 weeks ago, # |   +11 Good to see u again Lemonade255 !!!
•  » » 7 weeks ago, # ^ |   +8 Geez, sad to know that you like seeing such things
 » 7 weeks ago, # |   0 Only thing giving me hope is the unusual start time .May be something unusual happens for everybody in rating changes.xoxo +delta*2
 » 7 weeks ago, # | ← Rev. 3 →   0 I hope there are more interesting greedy, math, constructive algorithms.It can exercise thinking :D
 » 7 weeks ago, # |   0 Your effort is appreciated! May the CodeFORCES be with you...
 » 7 weeks ago, # |   -39 vaibhav garg
 » 7 weeks ago, # |   +4 my first contest after reaching expert! Super excited :D
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I feel great when I see people like you, as some people after reaching expert, stop giving contests in order to uphold their ratings.
•  » » » 7 weeks ago, # ^ |   +7 It's likely that I might become a specialist after today's contest, but I love this quote from the Batman movie — "Why do we fall? So we can learn to pick ourselves up."
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 bWayne is going to rock now:)
 » 7 weeks ago, # |   0 i wish to be a good contest
 » 7 weeks ago, # |   -33 Здравствуйте всем тот кто сдаёт эту соревнование !!! Удачи вам конечно я желаю !!! После соревнования если вы не смогли решать не которые задачи , тогда заходите по ссылку на Мой Телеграмм канал мы будем разбирать задачи ровно через час после завершения соревнования !!! Успехов вам !!!
 » 7 weeks ago, # |   0 This is my first time to participate in codeForces competition. What is the reward for this competition?Thanks!
•  » » 7 weeks ago, # ^ |   0 Explore the competitive programming, that would increase your problem solving skills. And after participating in this contest, you will definitely get a rating, rank among all the participants. So enjoyed it. Its a coding game.
 » 7 weeks ago, # |   -18 Удачи всем !!!
 » 7 weeks ago, # |   0 I am really really excited for this contest. Participating in Div-2, for my kind of rating people is really beneficial.
 » 7 weeks ago, # |   +1 Hope the problem statements are as short as announcement
 » 7 weeks ago, # | ← Rev. 2 →   0 Wow... From the Round #620, we can see that djm03178 is a very talented problemsetter. I think this round will be great!
 » 7 weeks ago, # |   0 Is there a way to cancel the registration? I can't participate suddenly！！！
•  » » 7 weeks ago, # ^ |   0 Yes, you can cancel it, but remember — no submissions -> contest unrated for you
•  » » » 7 weeks ago, # ^ |   0 thank you，bro
 » 7 weeks ago, # |   0 I should go to sleep before 11:00 tonight so actually this div.2 is the last round before I leave :)
•  » » 7 weeks ago, # ^ |   +13 OK thanks for info
 » 7 weeks ago, # |   -17 Yo Boiz i am sing song... Kaali kaali nain ka pakode kaale shoe leke gaddi kaali kaali teri ghadi wali da bache bache wich hit kudiyo da bradd pitt leke gaadi kaali kaali teri ghadi wali da teri mutt marida tenu pyaar krda....all black
 » 7 weeks ago, # |   0 1 hour left i hope it will be easy. I also hope i increase and u all increase in the rate good luck :D
 » 7 weeks ago, # |   0 As a participant, thanks djm03178 for the contest.In conclusion, good luck to everyone ^_^
 » 7 weeks ago, # |   +2 Hope to perform good in my 100th contest :) Good luck everyone....
•  » » 7 weeks ago, # ^ |   0 Good luck to you
•  » » » 7 weeks ago, # ^ |   0 Thanks ^_^ Same to you...
 » 7 weeks ago, # |   0 As a newbie, starting my 10 mins wim hof breathing session before the contest starts in 12 min to improve my chances :)
 » 7 weeks ago, # | ← Rev. 2 →   -33 this contest is pretty hard
 » 7 weeks ago, # |   -12
 » 7 weeks ago, # |   +8 I think djm03178 has done a typo while writing Div-*2* lol.
 » 7 weeks ago, # |   +7 Is it Codeforces Round #688 (Div. 1.5)?
 » 7 weeks ago, # |   +10 Is this a DIV 1.5 round?
 » 7 weeks ago, # |   +26 I feel that in quest of making unique problems, problem setters are increasing the difficulty of the problem.
 » 7 weeks ago, # | ← Rev. 2 →   0 this is a very hard contest
 » 7 weeks ago, # | ← Rev. 2 →   -26 The comment removed because of Codeforces rules violation
 » 7 weeks ago, # | ← Rev. 2 →   -22 I think there was some other comment related pob B. what's going on? why codeforces deleted comment related pob B?
•  » » 7 weeks ago, # ^ |   +61 It is against rules to discuss problems before a contest ends. Please, wait for the end of the round.
•  » » » 7 weeks ago, # ^ |   -58 Dude, I got banned on 2 days and can't participate on next cf round on FenWick because of writing comments "A < C < D < B for me", It's soo stupid. I think it's not prohibited to write ur opinion about level of problem not statement.
•  » » » » 7 weeks ago, # ^ |   +27 Your opinion on the difficulty of problems is information that can affect other participants. Just never talk about problems until the round is over. It's very simple. By the way, I recommend solving problems during the round. Note that the read-only mode does not limit participation in the rounds.
•  » » 7 weeks ago, # ^ |   -8 The owner's comment makes it seem like the problem in its essence was being discussed. Perhaps that was the plan all along to delete the comments and make it seem like the approaches to the problem were being discussed. On the contrary, statements were made to connote the recent trend in absurd difficulties for Div 2B and there is nothing from the rules here that forbids that. If a specific rule bears that intent, I would humbly suggest that the English version is re-written in a way that the meaning is not lost during translation.
•  » » » 7 weeks ago, # ^ |   +17 Can-do's and Can't-do's 5th"The contestants are forbidden to talk about subjects, related to the problems, with anybody, including other contestants. It is only allowed to ask questions to the jury via the system (see the 'Questions' section)."
•  » » » » 7 weeks ago, # ^ |   -28 Ignoring the terrible punctuation on the first sentence that confuses anyone that properly understands English, one is only left with the second sentence."It is only allowed to ask questions to the jury via the system". This implies that there should be no discussions about the problems in themselves. This does not imply that someone cannot say that Div2B is hard publicly. Like I said if one can't say this, the rule needs to be extended correctly.
 » 7 weeks ago, # |   0 I hope your rate increases :)
 » 7 weeks ago, # | ← Rev. 4 →   -8
 » 7 weeks ago, # |   -68 If individuals cannot speak on how they feel on this platform, why is there even an option to comment? There was a harmless conversation about the ridiculousness of supposed DIV 2B and it was censored. At least reset my contribution to 0 and do it smoothly. Many individuals here are not used to force and imposition as common in many communist countries. In the modern world, there are guidelines for doing things and thus only overstepping comments should be reported and then censored. What was being discussed is that: As there is no benefit to doing CP, there is no point participating in these contests since some problem setters want to act as gatekeepers and keep creating overly difficult Div 2Bs.
•  » » 7 weeks ago, # ^ |   -12 We understand that sometimes problemsetters may make mistakes as we all are humans but why delete comments??
 » 7 weeks ago, # |   0 I think codeforces is trying to avoid beginners. People are expecting a lot even from B. All those confidence of solving A,B,C during contest is going down... day by day...
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 yes and thats making me much sad :.(
•  » » 7 weeks ago, # ^ |   +8 This is a Div2 tho. I agree that the second problem may seem harder than usual but not that much. It was an easy to implement solution which needed a very nice observation. I think that it's better for the second problem to have something tricky in it, instead of being very easy and boring. Trust me, this kind of problems are good for beginners too because it teach them to think outside the box :). Also, there are div3 contests which kind of allows the beginners to solve the first 3 problems quick.
 » 7 weeks ago, # |   +4 Now I understand, contest timing > 2 hours then it is going to be Div 1.5
 » 7 weeks ago, # |   0 Today's Contest was really tough.
 » 7 weeks ago, # |   +16 In my opinion, B felt much harder than C.
•  » » 7 weeks ago, # ^ |   0 I understood B after thinking for some minutes, but couldn't apprehend C at all. What did I miss?
 » 7 weeks ago, # |   -51 Dumb problemsetters, they never learn...
 » 7 weeks ago, # | ← Rev. 2 →   +3 I'm curious how many people just solved D quickly by just simulating to get the expected value of (k 0s) followed by a 1 and observing the answer from that (though it is pretty easy to obtain even without that).
•  » » 7 weeks ago, # ^ |   +3 Transforming the tries to coin flips, it totally sounds like a common probability problem, which of course it is heh: https://math.stackexchange.com/questions/364038/expected-number-of-coin-tosses-to-get-five-consecutive-heads
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Yeah, one of my friends just told me about that, but simulating is really trivial as well (and faster if your math is weak like mine) with a simple code like this, and its pretty intuitive why it should work after you see the result. Simulation Code#include #define int long long using pii=std::pair; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int sum = 0, cnt = 100000, stages = 3; for(int i = 0; i < cnt; i++) { int curstage = 0; while(curstage < stages) { if(uniform_int_distribution(0, 1)(rng)) curstage++; else curstage = 0; sum++; } } cout << (long double)(sum) / cnt << "\n"; return 0; } 
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I derived expected value for covering different size gaps between successive checkpoints. For $g = 1$, ie consecutive checkpoints, expected value is $2$. For $g = 2$, using expected values, we get $6$ and then $g = 3$ we get $E(g) = 14$, using three equation. and then I thought maybe it is $E(g) = 2^{g+1}-2$ but dont know the general proof Edit:Ok link by robinz62 was useful, thank you
•  » » 7 weeks ago, # ^ |   +5 Lol You don't even need to simulate take a look at 1265E - Beautiful Mirrors
 » 7 weeks ago, # |   +3 Got terribly stuck at B. Can anyone please give me a hint now since the contest is over?
•  » » 7 weeks ago, # ^ |   0 first try to find how can you find min value of given array without any changes
•  » » 7 weeks ago, # ^ |   +2 The key observation is that changing a number at begin is like removing it from the array.So we need to find which number, if removed, contributes most.The contribution per number is the sum of differences of the adjacent numbers, and the number itself.
•  » » » 7 weeks ago, # ^ |   0 That's very well put. Thumbs up.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 If you want to see the approach or idea for solution of B: ApproachMy approach is to iterate through all elements and guess that if the current element is not there then what will be the answer to make them all equal w/o changing any element. (It would be the sum of absolute difference of each consecutive element, note: you have removed the current element from the array). This works because you can change the value of the current number to the next/previous number. So, it will reduce the steps to obtain an array with equal value. So, you can do it in o(n). And you have to see the case for ignoring the first/last element. it will be easily calculated !!  SolutionMy Solution
 » 7 weeks ago, # |   +3 how to solve D??i feel dumb for 1 hr after solving c.
•  » » 7 weeks ago, # ^ |   +3 Note that You need expected 2^(k+1)-2 moves to do 10000...0 where there are k digits.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +3 Number of steps to cross 1 is 2 , 1 0 is 6 , 1 0 0 is 14 , 1 0 0 0 0 is 30 . relation is s = 2*s+2 . Odd number of steps is never possible since to crossing any stage must be even . Now find biggest s which is close to n and keep doing that until n reaches 0 . For example for 20 it will be 14 + 6 i.e 1 0 0 1 0
 » 7 weeks ago, # |   0 Damn.. submitted D in the last 10 seconds. I hope it holds.
•  » » 7 weeks ago, # ^ |   0 Congrats dude. It passed.
•  » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 Thanks, but it needs to pass system tests as well. Fingers crossed.Edit: Cool, it passed.(submission)
 » 7 weeks ago, # | ← Rev. 2 →   -44 Spoiler...Why didn't this work for C?I think there is a carazy mistake there.
•  » » 7 weeks ago, # ^ |   0 Please hide your code.
 » 7 weeks ago, # |   0 I think problem D needs more explanation.
 » 7 weeks ago, # |   +9 D, how can we get an integer number of expected tries at all?
•  » » 7 weeks ago, # ^ |   +3 I guess the expected value converges to an integer when total tries is infinity.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 If there is one stage, then1/2 + 2 * 1/4 + 3 * 1/8 + ...I do not see for any number of stages how I could make such sequence ever result in an integer sum, by adding some checkpoints :/
•  » » » » 7 weeks ago, # ^ |   +3 See this
•  » » » » » 7 weeks ago, # ^ |   0 This is helpful link, thanks.So my above formular is kind of right, and simply sums up to 2.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 probability you will cross that level is 1/2 . Now i ask you a question , how many times you will win if you play at that level 2 times ? Answer is 1 . Else probability won't be 1/2. You can similarly generalize that beating that level n times will take 2*n matches .
•  » » 7 weeks ago, # ^ |   0 Beating n consecutive levels without a checkpoint is equivalent to getting heads in a coin flip n times in a row. Having that in mind you can read https://www.codechef.com/wiki/tutorial-expectation.
•  » » 7 weeks ago, # ^ |   0 Probability to cross a level is 1/2 . Thus total number of moves require to cross is 2 . Suppose i crossed a level and fell again to it . Then again expected number of moves required to cross it again will be 2 and thus total 4. Hence not only it will be integer but also even.
•  » » » 7 weeks ago, # ^ |   0 Ah... ok, got it. Thanks. I was simply completly wrong ;)
•  » » » 7 weeks ago, # ^ |   0 Probability to cross a level is 1/2 . Thus total number of moves require to cross is 2 . How? How can you relate probability with number of moves?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I should have used "expected" in place of "total" . But i think most people would have got it.
 » 7 weeks ago, # |   +21 Why guys why?? :(
 » 7 weeks ago, # | ← Rev. 2 →   +6 How to solve D ?It's either too much math or too much pattern finding
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 If you have a range with 1 at the beginning and k-1 0s after, then this range increases the expected value by 2^(k+1)-2. So while remaining length is > 0 you can simply take largest k for remaining length and put 1 and k 0s at the answer.
•  » » » 7 weeks ago, # ^ |   0 What's the proof for that? I tried to prove it during contest but couldn't complete the proof.
•  » » » » 7 weeks ago, # ^ |   0 https://codeforces.com/contest/1265/problem/ESee this problem and its editorial
•  » » » » » 7 weeks ago, # ^ |   0 :( Now I really regret not upsolving that contest.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I found that off google by searching "expected number of coin tosses before getting n in a row", where there's a convenient codechef link with the closed formthe proof does seem kind of messy, so I suspect most people might've done the sameEDIT: I realize it's quite obvious now if you write the recurrence relation $E_k = E_{k - 1} + \frac{1}{2} + \frac{1}{2}(1 + E_k)$
•  » » » » » 7 weeks ago, # ^ |   0 I firstly had a formula like 2^0 * k + 2^1 * (k-1) + 2^2 * (k-2)+...+2^k * 1 + 2^k. And I wrote bruteforce for k to 100 and saw the pattern.
•  » » » 7 weeks ago, # ^ |   0 You mean$${2^{k+1}-2}$$ How do you prove it ?
•  » » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 Let $E_x$ be the expected number of the state where you have beat x stages.It's easy to get $E_k=0$ and $E_x = \frac{1}{2}E_0 + \frac{1}{2}E_{x+1}+1 , x < k$After calculation, you will get $E_0 = \sum_{i=1}^k \frac{1}{2^i} + \sum_{i=1}^{k} \frac{1}{2^{i-1}}$And it means $E_0 = 2^{k+1}-2$That's the answer of k stages like 1 0 0 ... 0 0
•  » » » » 7 weeks ago, # ^ |   0 There is one more beautiful way to proove it. note that when you are at a 1-cell and you have $s - 1$ 0-cells till the next checkpoint you either succeed instantly with the $1/2^s$ probability, or you loose somewhere and return to the 1-cell. This situation is equal to flipping a coin that gives heads with the probability of $p = 1/2^s$. It's a known fact that the expectation of the number of throws is $\frac{1}{p} = 2^s$ now let's realize that the expectation of number of times you visit a cell after a checkpoint halves as you go further. It becomes quite obvious if you think about revisiting the 0-cell as about going back into this cell instantly after loosing a game in a cell after it. Indeed, if you loose a game you return to the last checkpoing and so steps after it you return to the 0-cell we are talking about. hence, the expectation of revisiting the cells of the 10...0 block with k zeros is $2^{k + 1} + 2^{k} + \ldots + 2 = 2^{k + 1} + 2^{k} + \ldots + 2 + 1 + 1 - 2= 2^{k + 2} - 2$ Voila.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 My approach passed 8 preteset . don't know correct or not.If odd ans=-1; else try like this for n=12-> 1010 (2^1+2^2+2^1+2^2) third place is 1 case if it make 0 it value will be 2^3 but if we add 2^3 with before value it exceed n.. 
 » 7 weeks ago, # |   0 was there an easy way to solve c or it was brute force???????
•  » » 7 weeks ago, # ^ |   0 yes brute force but n*n*40 time compexity so it is same as reading input
 » 7 weeks ago, # | ← Rev. 2 →   -8 How to do D...
•  » » 7 weeks ago, # ^ |   0 please hide your code
 » 7 weeks ago, # |   +8 Apart of the long statements and the difficulty of problem B, I think the problems were amazing! Thanks for the authors.
 » 7 weeks ago, # |   +18 I hate you Gildong !!
 » 7 weeks ago, # |   0 Where to see the solution？？？？？？？？？？？
 » 7 weeks ago, # |   0 can someone help me with problem C?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 triangle space is base*height/2 since they want it multiplied by 2 so it's just base*height so you just need to find the longest line for each number and you can calculate the max space I got the idea but sadly could not code it in time
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -24 First insert positions of all d points in a vector of pair. Then fix any 2 points from that and rest is just math. Let 2 points be (a,b) and (c,d). By just math I mean the height of the triangle can be abs(a-c) or abs(b-d). There will be 8 possible combinations and the max out of them will be the answer. You dont need to worry about the 3rd point as we are fixing it in the 8 possible combinations taken.Have a look at htis photo: https://ibb.co/6WppWZLCode : //Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> t; while(t--){ cin >> n; int gr[n][n]; for(i=0;i> s; for(j=0;j av; for(d=0;d<10;++d){ vector v; ll ans=0; for(i=0;i
•  » » » 7 weeks ago, # ^ |   0 i think it will be good to use spoiler.
 » 7 weeks ago, # | ← Rev. 2 →   0 B was way difficult !! i tried around all approaches but was getting none of them correct Thought of sorting and making all elements equal to median of the sorted array that didnt even work , making all elements equal to minimum , maximum That also didnt work , taking absolute difference between the adjacent elements that didnt even work !!I think B was really a difficult question !!
•  » » 7 weeks ago, # ^ |   0 If you want to see my approach for this problem, you can see here.
 » 7 weeks ago, # |   +7 Very strict time complexity for C
•  » » 7 weeks ago, # ^ |   +5 its not strict. You are saving index of each character. NOW, if all 4*10^6 are same character then you complexity will be (4*10^6)^2 (as you are traversing each possible pair of each character) which is definitely not in time limit.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 are u seriously? I think, (4*10^6)^2 = 1.6e+13 is way too much, and also t <= 2000. O(n^2) is not good for this.
•  » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 Continuous maximum value of n could be 2000. Hence the value 4*10^6
•  » » » » 7 weeks ago, # ^ |   0 But then matrix is n*n and u r saving indices of character so your set contains 4*10^6 elements. Moreover u r traversing ur set in two loops making it near 10^13...
•  » » » » » 7 weeks ago, # ^ |   0 Oh I Get it thanks
•  » » 7 weeks ago, # ^ |   0 My O(n*10*4*2)ish 100378697 got AC with 2997ms. I can't even.
 » 7 weeks ago, # |   0 What should I do, if someone asked me to send him the solution of the problem until the end?
•  » » 7 weeks ago, # ^ |   -6 humiliate him, tag that cheater in your comment
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 Sulaimon is a cheater then (It means: "Give me the solution to the second problem in Div. 2 contset, please")
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 After you have uploaded your image on any site(like imgur), open that image on that site,right click -> open image in new tab, then copy the URL(should end with JPG/PNG), use that URL to upload image
•  » » » » » 7 weeks ago, # ^ |   0 Thank you very much!
 » 7 weeks ago, # |   0 Thank you for the round, I really need to work hard.
 » 7 weeks ago, # |   +2 Problem C gave me PTSD
•  » » 7 weeks ago, # ^ |   0 how to solve it!!
 » 7 weeks ago, # |   0 Long and difficulty problem statements !!
 » 7 weeks ago, # |   +7 I hate problem B
•  » » 7 weeks ago, # ^ |   0 I can feel your pain.
•  » » » 7 weeks ago, # ^ |   +1 it was too hard as not usual
 » 7 weeks ago, # |   -7 what the fucking B
 » 7 weeks ago, # |   0 Damn that B problem will nerf my rating by far.. Like you could skip one of the numbers each time so I decided 3 cases skip the 1st one, skip the smallest one and skip the biggest one but I would not get the AC. I would get WA on test 5. Can someone give me a test case where these cases don't work?
•  » » 7 weeks ago, # ^ |   +3 0 25 0 10 20 30 40 50
•  » » 7 weeks ago, # ^ |   0 5 1 2 8 3 9 This can be done in 8 steps.
 » 7 weeks ago, # |   0 Can anyone explain the solution of problem B...?
•  » » 7 weeks ago, # ^ |   0 just erase every element of the array one by one and calculate the result. its just the explanation you have to do it in optimize way
•  » » 7 weeks ago, # ^ |   0 Look at this comment.
 » 7 weeks ago, # |   0 Any Explanation on how to solve B ?
•  » » 7 weeks ago, # ^ |   0 Look at this comment.
 » 7 weeks ago, # |   +15 Struggled on B for almost 2 hours but solved D in less than 10 minutes :( Feeling very terrible
•  » » 7 weeks ago, # ^ |   0 Story of my Codeforces career. And the funny thing is you need guts to skip B and go do D. Because come you did not solve D guys that were persistent on B will get B and you will get less score than them even if you get B later.
 » 7 weeks ago, # |   +2 Div2 B took me 20 minutes to understand the problem, 40 minutes to crack, 20 minutes to get the idea, 10 minute to implement, 20 minute fixing bug. And after that what happened? The contest has been finished!! BTW, problem b was amazing!
•  » » 7 weeks ago, # ^ |   0 Yeah it was good but the level of question was like C.
•  » » 7 weeks ago, # ^ |   0 could you please explain the solution?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Correct me if I am wrong, If u don't change any elements in the array, the minimum operation is the sum of all abs(a[i],a [i+1]) where i is 0 <=i
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Deleted
 » 7 weeks ago, # |   +1 This round was a nightmare and a reminder of how much I need to practice
 » 7 weeks ago, # |   +1 How to not brick on this contest's B?
 » 7 weeks ago, # |   +28 Unpopular opinion: D is easier than B and C.
•  » » 7 weeks ago, # ^ |   +5 I found E easier than C.
•  » » » 7 weeks ago, # ^ |   +5 I found E easier than B and D, XD.
•  » » 7 weeks ago, # ^ |   +5 Agree with that.
 » 7 weeks ago, # |   -8 This was a good set of problem set.I Enjoyed solving them
•  » » 7 weeks ago, # ^ |   +11 My dude you only solved A tho :/
•  » » » 7 weeks ago, # ^ |   +5 Yeah broBut that was funThat's what I said ;)
 » 7 weeks ago, # |   +17 This kind of contest is bad for mental health.
•  » » 7 weeks ago, # ^ |   0 Can't agree more :(
 » 7 weeks ago, # |   +4 Not a good round, the statements wasn't clear enough.
 » 7 weeks ago, # |   -9 :D I used 8 ifs for each for in problem C and get TLE :D
 » 7 weeks ago, # |   +1 Unpopular opinion I liked the contest B was C level but it's a nice problem the solution is not stupidly obvious .. solving C isn't too hard but understanding it may take some time
 » 7 weeks ago, # | ← Rev. 5 →   +10 solution to problem B. herelets say you have an array arr = [a, b, c, d, e, f] we want minimum operation so this is the optimal way to select suffix now without changing any element is .. [a, b, c, d, e, f] [a, b, c, d, e, e] => abs(e - f) [a, b, c, d, d, d] => abs(d - e) [a, b, c, d, d, d] => abs(c - d) [a, b, c, c, c, c] => abs(b - c) [a, b, b, b, b, b] => abs(a - b) [a, a, a, a, a, a] total = abs(e - f) + abs(d - e) + abs(c - d) + abs(b - c) + abs(a - b) now we can change any one element of the array, and we want minimum ans. lets say we want to change d ? (we can change d to c or e // why ?) so our current ans is total - abs(c - d) - abs(d - e) + abs(c - e) changing d means we are removing it from array. minimize answer every time. other 2 cases we can also change arr[0] = arr[1] we can also change arr[n - 1] = arr[n - 2] minimize answer. 
•  » » 7 weeks ago, # ^ |   0 Please where did you get the idea that changing one element of the array implies removing it. If all the elements before the element you changed are not equal, I don't think you have removed it.
•  » » » 7 weeks ago, # ^ |   0 Look at this comment.
•  » » » 7 weeks ago, # ^ |   0 Removing that number means, you can convert that number to its next number which will skip the step to convert the suffix to that number. You can directly covert the suffix to its previous number.
•  » » 7 weeks ago, # ^ |   0 Thanks a lot. It was a good editorial. Easy to understand.
 » 7 weeks ago, # |   +1 While solving problem B , I observed that for given array total operations required would be sum of absolute difference of consecutive elements. How to prove it concretely ?
•  » » 7 weeks ago, # ^ |   0 Start from last element add absolute diff of last and second element... Then last 2 elements becomes equal and equal to 2nd last. Go to third last element then add the abs diff bw third last and second last and go on.... resulting in sum of ablolute diff bw adjacent elements..
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +3 In an array where all elements are equal, the sum of absolute differences of consecutive pairs of elements is $0$. The reverse also applies — if that sum is $0$, all the elements must be equal.When incrementing / decrementing the suffix starting from index $i$, note that all the differences between elements in the suffix and the differences between elements outside the suffix remain the same. The only place where that difference changes is in the pair of elements where one is inside the suffix and the other is outside it — indices $i - 1$ and $i$.Since each operation changes the difference (and, performing optimal operations, decreases the absolute difference) by exactly $1$, number of operations required is greater than or equal to the sum of the absolute differences of consecutive elements. The shown algorithm can do it in that number of operations, thus the sum of the absolute differences of consecutive elements is the minimum number of operations required.
•  » » » 7 weeks ago, # ^ |   +3 Thnx for such clear solution and observation :)
•  » » » 7 weeks ago, # ^ |   +3 interesting proof . Thanks :)
 » 7 weeks ago, # | ← Rev. 2 →   +7 After CF predictor predicts me -50,What my mouth says: Rating is not the matter. The idea u learnt is more.What my mind says: Rating is the matter,dude.
 » 7 weeks ago, # |   +1 Please explain problem B in more detail.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 Let we have numbers $a_1, a_2, a_3... a_n$. Let make them all equal to m. Then to make $a_1$ equal to m we need $|a_1 - m|$ steps, and all other leemtns would increase by $m - a_1$.Then, to make $a_2$ equal to m, we need $|m - (a_2 + (m - a_1))|$ steps since $a_2$ is $a_2 + (m - a_1)$ now. $|m - (a_2 + (m - a_1))| = |a_1 - a_2|$.And total addition to elements is equal to: $m - a_1 + (m - (a_2 + (m - a_1))) = m - a_2$. From here we can see, that total addition to elements after $i$-th step are going to be $m - a_i$. So, the ansewer for number m is equal to $|m - a_1| + |a_1 - a_2| + |a_2 - a_3| + .. + |a_{n-1} - a_n|$.Now we want to minimize that sum. We can always choose $m = a_1$ to make first number 0. After that we just want to minimize the sum we have. To do that let assume we change $a_{j}$. After changing $a_j$ to $a_{j-1}$ (actually we want $a_j$ to be in interval from $a_{j-1}$ to $a_{j+1}$). After that $|a_{j-1} - a_j| + |a_j - a_{j + 1}|$ is going to become $|a_{j + 1} - a_{j - 1}|$. So we want to find such $a_j$ that $(|a_{j-1} - a_j| + |a_j - a_{j + 1}|) - (|a_{j + 1} - a_{j - 1}|)$ is maximum and change it to $a_{j-1}$.That's all.
•  » » » 7 weeks ago, # ^ |   +1 Why should we bring this number to zero: "We can always choose m=a1 to make first number "0"?
•  » » » » 7 weeks ago, # ^ |   0 See, nothing, except $|m - a_1|$ depends on m. As soon as we want to minimize the whole sum, we should make $m = a_1$. Otherwise $|m - a_1|$ is going to be bigger than 0, but making $m = a_1$ will make sum smaller.
•  » » » » » 7 weeks ago, # ^ |   0 And what m should we equate them with, and did I understand correctly that each a[i] = |a[i]-a[i-1]|. That is how to find it m?
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 No, you get it wrong. We just say that m is first number. We've proved that ansewer is $|m-a_1|$ + sum of absolute value of difference between $a_i$ and $a_{i+1}$ elements. Then, we want to find one number $a_j$ and make it equal to $a_{j-1}$ to minimize the whole sum
•  » » » » » » » 7 weeks ago, # ^ |   0 Thank you so much!
 » 7 weeks ago, # |   +14 Benefits of hard contests: 1- No long queues. 2- System testing starts and ends in 30 mins. xD
 » 7 weeks ago, # |   0 C was easy but implementation was bit long i solve in 5 minutes implement in 80 minutes
•  » » 7 weeks ago, # ^ |   0 Same! I also felt it was bit of implementation heavy.
 » 7 weeks ago, # |   +13 why is B being rejudged?
•  » » 7 weeks ago, # ^ |   +1 I think Mike added some more multi-tests and rejudged. Seems that my tests weren't strong enough :(
 » 7 weeks ago, # |   0 Nice problemset! Hope there will be more problems at the same difficulty as this in the future for the middle-ratings like me. Thanks for your contributions =) very much
 » 7 weeks ago, # |   +4 The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3500.REAL scoring distribution is 500 — 2000 — 1500 — 2000 — 2500 — 3500.LOL
 » 7 weeks ago, # | ← Rev. 2 →   +9 It seems that AceKing and I were the only people in the whole contest who passed the pretests for C, but TLEd on the main tests :( that's quite a sweet spot we managed to hit with our execution time!
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 How to find this who all failed systests without exploring the whole ranklist obviously?
•  » » » 7 weeks ago, # ^ |   0 filter the submissions
•  » » » » 7 weeks ago, # ^ |   0 I didn't see any filter for that. Are you sure?
•  » » » 7 weeks ago, # ^ |   0 As Forward. says, I clicked status, filtered on problem C, verdict Time Limit Exceeded. The results are displayed in reverse chronological order, so I looked specifically for entries submitted in the time range of the contest, but which got TLE verdict after the end of the contest. There were only 2 of us.
•  » » » » 7 weeks ago, # ^ |   0 Okay seems fine but I was looking for something which can show me all types of failed sys-tests (WA/TLE/RE etc) on one page. Thanks anyways.
•  » » » » » 7 weeks ago, # ^ |   0 I don't believe that exists.
•  » » » » 7 weeks ago, # ^ |   0 Not 2, there is also me who MLE-ed — you should filter by "rejected" and tests >= 10 (I think this is the number of pretests for C).
•  » » » » » 7 weeks ago, # ^ |   +3 In my comment, I specifically said "TLEd" and referred to execution time. Unlucky that you MLEd, though.
•  » » » » » » 7 weeks ago, # ^ |   0 You are right :(
 » 7 weeks ago, # |   0 Today was the first time I needed to fix an MLE from pretests and fail system tests due to MLE :/https://codeforces.com/contest/1453/submission/100368040
 » 7 weeks ago, # |   -55 Today contest very bad contest. I downvote today contest. Do not make tomorrow contest. I not give contest. djm03178 do not make contest again.
•  » » 7 weeks ago, # ^ |   -11 Full support!
 » 7 weeks ago, # |   +4 B was probably more difficult than usual...
 » 7 weeks ago, # | ← Rev. 2 →   0 I think the 1st standing in div2 did not finish the competition independently for the submission time of his code. If he did, I apologize for this comment.
 » 7 weeks ago, # |   +5 I did a very stupid mistake in B.For n = 2 answer will be 0 but I don't know what came to my mind, I printed their difference.Sadly that case wasn't in the pretests.
•  » » 7 weeks ago, # ^ |   0 Same mistake :-(.
•  » » 7 weeks ago, # ^ |   0 omg RIP :(
 » 7 weeks ago, # | ← Rev. 2 →   +3 The contest was very good and problem A was easy and standard.
•  » » 7 weeks ago, # ^ |   0 What are you waiting from Div 2 A?
 » 7 weeks ago, # |   0 when will the rating changes will be published ???
 » 7 weeks ago, # |   0