### SleepyShashwat's blog

By SleepyShashwat, history, 8 months ago,

Henlo Codeforces! ^_^

I invite you to participate in Codeforces Round #663 (Div.2) taking place on Aug/09/2020 17:35 (Moscow time). The round is rated for users rated less than 2100, while other users can participate non-competitively.

The round features five problems, and you have 2 hours to solve them. There may, or may not, be an interactive problem; regardless, you should know how to deal with them.

I would, now, like to thank–

Please do not mind the long list of testers (I had to write code to tag everyone here) since the problem set changed significantly after the first round of testing.

We will announce the scoring distribution shortly. The scoring distribution is 500–750–1250–2000–2750.

Good luck, and stay safe!

UPD: Editorial

Here are video editorials by BRCode:

UPD2: Finally, congratulations to the winners!

Div. 1:

Div. 2:

• +1305

 » 8 months ago, # |   +148 As a tester I think people will like this round because of interesting problems,diverse topics and short statements
•  » » 8 months ago, # ^ |   +70 Also (as a tester) wants contribution :)
•  » » » 8 months ago, # ^ |   -52 So that was a f***ing lie (about "as a tester")
•  » » » » 8 months ago, # ^ |   +66 I meant kshitij_sodani, not me. I guess people got confused and downvoted me.
•  » » » » » 8 months ago, # ^ |   0 Understand, have a great day!
•  » » » 8 months ago, # ^ |   +128 Sir on CodeForces never make the mistake of arguing with a person who has higher rating. I've been burnt before.
•  » » » » 8 months ago, # ^ |   -12 Ratism...
•  » » » » » 8 months ago, # ^ |   +99 I literally just told you not to do this smh
•  » » » » » » 8 months ago, # ^ |   -68 I didn't argue with you smh
•  » » » » 8 months ago, # ^ |   -11 I've heard myths like If you are div 1 , than the number of div 2 guys you've roasted is (your contribution)*(1000000000 +7) , is that true
•  » » » » » 8 months ago, # ^ |   -6 It's actually 998244353
•  » » » » » » 8 months ago, # ^ |   -12 I guess its bad news for stEV then
•  » » » » » » » 8 months ago, # ^ |   -17 Time to lose contrib :)
•  » » 8 months ago, # ^ |   0 thanks, I see a lot of orange here in the group.BTW what's polygon, I read it in every announcement MikeMirzayanov for Codeforces and Polygon platforms– Polygon is truly remarkable!
•  » » » 8 months ago, # ^ |   +7 Polygon in basically the platform for creation of programming contest problems. It also supports problem statement writing, test data preparing, model solutions, judging and automatic validation.
•  » » 8 months ago, # ^ |   -17 Hope there are strong test cases this time. :P
•  » » 8 months ago, # ^ | ← Rev. 2 →   -16 how can i increase my rating
•  » » 8 months ago, # ^ |   0 Just after reading SleepyShashwat I am feeling sleepy
 » 8 months ago, # |   +162 As a tester... Damn there's so many of us!
 » 8 months ago, # | ← Rev. 2 →   0 OMG!!! another "as a tester" comments "/
•  » » 8 months ago, # ^ |   -21 But we can't disagree many of them gives us some useful information about the round.
•  » » » 8 months ago, # ^ |   +97 Lemonade255 , I understand the first part of your username butt why do you like 1373
 » 8 months ago, # |   +217 Which ponies are we helping this time?
•  » » 8 months ago, # ^ |   +14 I wish none of them :(
•  » » 8 months ago, # ^ |   +366 Sorry to disappoint you, but I've tried my best to keep the statements short and purely formal.
•  » » » 8 months ago, # ^ |   0 Thanks a lot for short and formal statements :)
•  » » » 8 months ago, # ^ |   +42 That's disgusting
•  » » 8 months ago, # ^ |   0 Definitely not the ones named Augustus.
 » 8 months ago, # |   +522 Omg Indian round! So excited
•  » » 8 months ago, # ^ |   -56 Ah shit here we go again. Oh, wait...
•  » » » 8 months ago, # ^ |   0 You think this line will work everytime :D
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 Am I the only one, seeing the similarity between the names of SleepyShashwat,RestingRajarshi, AsleepAdhyyan , AwakeAnay.. UPD:one of them is odd one out
•  » » » 8 months ago, # ^ |   0 and...?
•  » » » 8 months ago, # ^ |   +3
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 I am not sure about other three, but[user:SleepyShashwat] is an IOI Silver medalist from India.
•  » » 8 months ago, # ^ |   -18 it will be Mathforses because you are coordinator no writing) look like stupid and interesting)
 » 8 months ago, # |   +47 *insert cringe proud indian comment here *
 » 8 months ago, # | ← Rev. 3 →   -28 0
 » 8 months ago, # |   -32 I hope, we don't have to help Ponies, in this contest, unlike Previous Contest! :|
 » 8 months ago, # |   +109 Hope the problem statements are made while you are not sleepy.
•  » » 8 months ago, # ^ |   +193 Well he was, but I made sure they are alright ;)
 » 8 months ago, # | ← Rev. 2 →   +174 Memes/images should be posted in spoiler! Indians on CF" As a tester..." How to feign consumer satisfaction to investors Anton roundsDisclaimer: The memes aren't specifically for this round, that's for you to decide :) I liked it a lot as a tester.
 » 8 months ago, # |   +28 So we'll have video editorials too this time?
•  » » 8 months ago, # ^ |   +69 Yes and afaik in 3b1b style.
•  » » » 8 months ago, # ^ |   +13 Looking forward to it!
•  » » 8 months ago, # ^ |   +15 :)
•  » » 8 months ago, # ^ |   0 This will be the first official video editorials for me in CF. Looking forward to it.
 » 8 months ago, # |   +11 orz
 » 8 months ago, # |   0 As a participant, all we want is short and clear statement. Hope we won't get disappointed :)
 » 8 months ago, # |   +32
•  » » 8 months ago, # ^ |   +11 Not.Enough.Memes.
•  » » 8 months ago, # ^ |   0 Is it just me or the meme image disappeared after 12 hours?
 » 8 months ago, # | ← Rev. 2 →   +6 Props for the 3b1b style video editorials! Sounds really cool, will definitely watch.
 » 8 months ago, # | ← Rev. 2 →   0
 » 8 months ago, # |   +30 As a pony , I hope I'll not find any problem about ponies :(
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Lol
 » 8 months ago, # | ← Rev. 2 →   -50 Don't downvote sir
 » 8 months ago, # |   +39 SleepyShashwat, AwakeAnay, AsleepAdhyyan, and RestingRajarshi. Coincidence!? I think not. ;)
•  » » 8 months ago, # ^ |   +52 How so insightful sir
•  » » 8 months ago, # ^ |   +21 Not a coincidence indeed, check this
•  » » » 8 months ago, # ^ |   +4 Wow cubefreak you are a brilliant archaeologist!
•  » » » » 8 months ago, # ^ |   0 Thanks NewAccelWorld XD
•  » » 8 months ago, # ^ |   0 LMAO
 » 8 months ago, # |   +80 BRCode for making 3b1b-style video editorials of the problems! YouTubers who make video editorials after the contest...![ ]()
 » 8 months ago, # |   +17 I'm wondering why almost half of the recent contests, including this one, contain $5$ problems, but not $6$.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +22 As a tester you will know why 5 is enough :)
•  » » » 8 months ago, # ^ |   +6 I won't be wondering any more if I can have a chance to be a tester
•  » » 8 months ago, # ^ |   +38 Because , by excluding 1 problem from 5 contests ,they can create a new one.
 » 8 months ago, # |   +21 Is this the quartet of last year's IOI from India?
 » 8 months ago, # |   0 Curious to know, how many problems/ideas got rejected in this round.
 » 8 months ago, # |   0 "Henlo" ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +5
 » 8 months ago, # |   +14 Hopefully the ponies are grazing grass instead of playing chess coloring games with each other.
 » 8 months ago, # |   0 I hope we are not going to have weak pretests like the previous one
 » 8 months ago, # |   +2 Happy to see an Indian round Again. :D
 » 8 months ago, # | ← Rev. 3 →   +1 Not as a tester I hope you good luck!
 » 8 months ago, # |   0 Wait did I read it right that there are vedio editorials ? Cool.
 » 8 months ago, # |   0 Hope that this round has short statements and strong pretests. I am still trying to get back from the trauma of previous round.
 » 8 months ago, # | ← Rev. 2 →   -6 An Indian round with so many testers (and no more ponies and their stories) !!So excited.
 » 8 months ago, # |   +8 How many testers do you need?-YES!How many pony stories do you need?-NO!
 » 8 months ago, # |   +6 I hope this round will not test our English comprehension skills.
•  » » 8 months ago, # ^ |   +3 lol, last one did! XD
•  » » » 8 months ago, # ^ |   0 Yes the problems were very confusing.
•  » » » » 8 months ago, # ^ |   0 I second that.
 » 8 months ago, # |   -18 Why is every div2 round having 5 problems now? Is making 6 problems too hard or are you sleepy while writing problems as well?
•  » » 8 months ago, # ^ |   +14 I prefer 5 problem rounds. They have better problems.
 » 8 months ago, # |   0 (I had to write code to tag everyone here) : How does one write code to tag people? O.o
•  » » 8 months ago, # ^ |   +6 Oh, I meant to sort the handles, and then wrap them around [user: ] o_o.
•  » » » 8 months ago, # ^ |   +15 I just realize that the names are sorted.
•  » » » 8 months ago, # ^ |   0 Did you use an if to add the and before the last handle? :P
 » 8 months ago, # |   0 Hope the statements are not sleepy.
 » 8 months ago, # | ← Rev. 2 →   +3 As a tester i want to say that the contest is shit!!!! Thankfully i am not participating in this officially!! sighs: All the specialists brace yourself!!
•  » » 8 months ago, # ^ |   -19 Thats not really surprising if you look at the tag of the blog.
•  » » 8 months ago, # ^ | ← Rev. 3 →   -19 Deleted:(
•  » » 8 months ago, # ^ |   0 Do you mean advanced algorithms as you mention specialists are going to have a hard time? or are you referring to math tricky questions? or ADHOCs? 0_0
•  » » » 8 months ago, # ^ |   +5 Its just because i am a specialist
 » 8 months ago, # |   0 Typo in spelling of Hello Codeforces Please change Henlo --> Hello
•  » » 8 months ago, # ^ | ← Rev. 2 →   +9 Actually not, see this.Just have learned that few comments above.
 » 8 months ago, # | ← Rev. 2 →   0 With this amount of testersHope for stronk pretest and programming test, not English test.Thx.(and 3b1b editorial seems nice!)
 » 8 months ago, # |   -17 Although your Indian English is kinda weird, but the 3B1B-style video is so fantastic!
 » 8 months ago, # |   +4 Why am I getting a feeling that this is going to be a MathForces round? I hope it is not though! :PAlso antontrygubO_o as a coordinator (Yay! :D)
•  » » 8 months ago, # ^ |   +104 I think your 2 statements contradict each other
•  » » » 8 months ago, # ^ |   0 Anton as co-ordinator and Contest full of Adhoc problemsDo these two statements contract as well ?
•  » » » 8 months ago, # ^ |   -11 Oh fuck! :/
 » 8 months ago, # |   +68
•  » » 8 months ago, # ^ |   0 Prove 1 : link1 link2prove 2 : sorry Not available (may be your id created last of 2018 )
 » 8 months ago, # |   -15 Henlo Codeforces! ^_^ I think here must be "Hello" ^_^
•  » » 8 months ago, # ^ |   +4 No, they didn't misspell Henlo is a cute puppy language style for saying Hello.
 » 8 months ago, # |   0 Another contest!! As a regular contestant, I need a break :'(
 » 8 months ago, # |   +31 As a contestant, I want rounds with aryanc403 as the author
•  » » 8 months ago, # ^ |   +21 Round preparation as an author very hard. :(
 » 8 months ago, # |   +1 I really starts enjoying memes here...
 » 8 months ago, # |   +6 Thanks , Codeforces!!!
 » 8 months ago, # |   -15 author, how could you misspell the word ,,Hello''? i want to cry((
•  » » 8 months ago, # ^ |   0 Henlo is an internet term used for greeting others. It is not misspelt :')
•  » » » 8 months ago, # ^ |   0 ok but my eyes can't understand it((
•  » » 8 months ago, # ^ |   +4 They didn't misspell it. It is a cute puppy language style for saying Hello.
 » 8 months ago, # | ← Rev. 2 →   0 Did any tester test anything with Python? Did someone spend the 10 minutes checking if the standrad solution in Python doesn't get TLE or too much memory?
•  » » 8 months ago, # ^ |   +33 Advise as a community member, You should never worry about TL issues in an Anton coordinated round.
•  » » » 8 months ago, # ^ |   0 ^_^
 » 8 months ago, # |   +7 Hope the statements are clear. I don't want to walk around the maze :)))
 » 8 months ago, # |   0 soo, if i utterly fail to do the questions then what will happen? (my rank is 0 , will to in minus or increase if yes then how?!
•  » » 8 months ago, # ^ |   0 If you don't have a submission then rating will be unchanged.If you make at least one submission but solve 0 then rating may increase for new users. Check Here for details.
•  » » » 8 months ago, # ^ |   0 Thanks man, for helping me out
 » 8 months ago, # |   0 Thanks , Codeforces!!!
 » 8 months ago, # |   -21 As a tester I think people will like this round because of interesting problems,diverse topics and short statements. Thanks, Codeforces!!!
•  » » 8 months ago, # ^ |   0 Yeah.there will also be thought-provoking questions
 » 8 months ago, # |   0 SleepyShashwat please don't sleep during the going contest
•  » » 8 months ago, # ^ |   +32 Relax, there's AwakeAnay
•  » » 8 months ago, # ^ |   -13 It's a joke if you get it..
 » 8 months ago, # |   -16 Looking forward to a good round after a not-so-good round.
 » 8 months ago, # |   +15 Happy to see Indian School Students doing great on Codeforces and other CP Platforms! I wish, I also knew about CP while I was in School. Indian Students need to learn that "Apart from IIT JEE, there is also a world called CP". All the best SleepyShashwat for your future endeavours!
•  » » 8 months ago, # ^ |   -30 Awwwwwwwww, Were you not able to clear JEE, you poor soul
•  » » » 8 months ago, # ^ | ← Rev. 23 →   +24 Poor Soul thinking that only a JEE Failure would write that statement. I think you are in the First Year of an IIT or you are not an IITian. Only some First Yearites(Fachas) at IITs have this attitude that they have cleared JEE and won the world OR this attitude is shown by Butt Hurts who couldn't clear JEE Advanced!
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   -40 What if i say i am in third year in an IIT ? What shitty explanation will you give then ?In my college "fachas" or first years, whom you are saying shit for no reason, are better than you in CP.
•  » » » » » 8 months ago, # ^ |   +4 I have seen people mention IITJEE many times before . So , does this university conduct some kind of computer science competition like I.O.I. , because I have seen it quite a few times like on this blog , Indian contest blog , cheater blogs and some ICPC blogs . Its a rare thing for universities getting mentioned so it kind of made me curious
•  » » » » » » 8 months ago, # ^ |   -16 IITJEE is engineering entrance exam of physics, chemistry and maths which is considered to be one of the most difficult entrance exams in the world.Top rankers in this exam pursue computer science in IITs not because they have interest in IOI or ICPC only because their parents saw headlines in newspapers telling some CSE grad from IIT secured this much package at google or is now CEO of this company blah blah which is big deal for middle class indian society as most other jobs in india are very low-paid.Also indian pupils are dumbass as there was no need of mentioning IITJEE in this blog in the first place
•  » » » » 8 months ago, # ^ |   0 LOL you are from IIT and still a pupil after one year. You must belong to one of the "special" communities.
•  » » » » 8 months ago, # ^ |   0 The only reason i am offending you is you tried to offend those students who busted their ass in getting a f***** IIT after like 2 years of rigorous studying ( maybe 4 years for some ) and you are into CP for like one year and still nowhere with CP ( to be honest ).
•  » » » » » 8 months ago, # ^ | ← Rev. 3 →   +7 I am also in the third year. And to be honest, you can check my submissions, I only gave contests till December last year. Many first years are better than me in my college also. They are Masters and it happens in all IITs I guess. I know I am nowhere in CP and it doesn't even matter to me. And what I have tried to say is there is a world apart from JEE also- for those who couldn't clear that! We also do CP only to get Jobs in MNCs and they also! I also spent 2 years in rigorous studies and I know that situation. And for your kind info, you are wrong even at judging my "Special and Reserved Community" LOL!!! It is just that some need more time doing CP some don't need that. Some do CP continuously and daily while some don't practice that much and I belong to the second one. I don't practice that much because everyone has different priorities. CP is a backup for some to enter the software/IT sector. They may want to do something else like Management, Civil Services, etc. And there are many such IDs on Codeforces- belonging to IITians, a general category and Pupil/Specialist. So, keeping all factors in mind stop judging people! And for your kind information, study for Internships rather than trying to offend me! And I didn't call first years SHIT. It was you who misinterpreted it! I just said they have that kind of feeling in mind in first years. But second-year onwards they know the situation :P.
•  » » » » » » 8 months ago, # ^ |   -34 Ok Mister Pupil
•  » » » 8 months ago, # ^ | ← Rev. 3 →   +12 or he might have cleared JEE
•  » » » 8 months ago, # ^ |   +4 I cleared JEE but wish I'd rather got to know about CP back in school. I have been good at programming since I was in high school but thanks to the JEE culture in India I never got to know about cp.Whats worse, I got to know about cp only in my third year and I have only 1 year in my college life left now. Honestly if i could go back in time, I would tell my earlier self to do CP rather than jee.
•  » » 8 months ago, # ^ |   0 What is IIT JEE ? Is it something on the lines of web development or something like that
•  » » » 8 months ago, # ^ |   0 it is the exam conducted to select students for studying in the most prestigious colleges of india (IIT). and no, u need to learn physics, chemistry and maths to crack the exam and secure the highest ranks possible to take up computer science(which is one of the many streams taught in an IIT).
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 So are students not aware about cp or they choose not to pursue it
•  » » » » » 8 months ago, # ^ |   0 I feel very sorry to say that but the education system in India is totally weird. I hear the word "CP" just some months before(after going to college). When we were in standard till 10. We have absolutely zero knowledge about programming(and we taught in school is totally theoretically especially in CBSE Board(I am from CBSE). In countries like Russia, people start programming in a very early age. They have much more knowledge than us. (Prooving my above statement, Currently there are only 7 red coders from India despite having the largest number of active members in Codeforces(almost double than any country).I am from India, and I really feel for it!!!
•  » » » » » » 8 months ago, # ^ |   0 you mean that we have not started cp early, so we are not talented as other country's people?
•  » » » » » » » 8 months ago, # ^ |   +3 Yes, this is the only reason I can think of!
•  » » » » » » 8 months ago, # ^ |   -8 Don't feel such. "CP" is not everything. CP just make your approach analytical and logical. Just like a brain exercise. But JEE is where you can do it with extra knowledge. CP makes you better at problem-solving but JEE is really good make strong your fundamentals. Especially I love physics. I love CP too. But I think Physics is always good to explore :)
 » 8 months ago, # |   0 Hope that statements are simpler this time
 » 8 months ago, # | ← Rev. 2 →   0 I hope I will not sleep during the contest!!!
 » 8 months ago, # |   0 Thank you.
 » 8 months ago, # |   0 Score Distribution?
 » 8 months ago, # |   +28 where is editorial for this round?
•  » » 8 months ago, # ^ |   -10 What do you mean? The round hasn't even started yet...
•  » » » 8 months ago, # ^ | ← Rev. 2 →   -7 UPD: lol. 7 people got rickrolled :))
•  » » 8 months ago, # ^ |   0 sorry I mean for previous round actually.
 » 8 months ago, # |   0 codeforces helping a lot to many students
 » 8 months ago, # |   0 Auto comment: topic has been updated by SleepyShashwat (previous revision, new revision, compare).
 » 8 months ago, # |   0 I hope the problems will be interesting.
 » 8 months ago, # |   +3 very excited for round.
 » 8 months ago, # |   +2 Very excited for the indian round :)
 » 8 months ago, # |   0 woweeeeeeeeee! 3Blue1Brown style editorials.
 » 8 months ago, # |   -6 Half of the coders are giving Goldman Sachs aptitude test now lol
•  » » 8 months ago, # ^ |   +9 Is it necessary to post it here ?
•  » » » 8 months ago, # ^ |   +3 Just felt like posting man. Everyone posts irrelevant memes, so why not this. Anyways, I apologise I said something wrong.
•  » » » » 8 months ago, # ^ |   +3 That's true about irrelevant meme. But what I am saying here is we should try to avoid posting irrelevant stuff here. Is someone is committing some mistake, it doesn't mean that we should also right ?
•  » » » » » 8 months ago, # ^ |   0 I think you misunderstood. I said, many are busy giving the test so, may not appear in this round. Thats what I meant :}
•  » » 8 months ago, # ^ |   0 What's the lol for ? I genuinely can't find a reason to laugh at that ...
 » 8 months ago, # |   0 This feels quite opposite of previous round...
 » 8 months ago, # |   0 I can't understand what 'even length square sub-matrix' means in problem D.Does it mean a sub-matrix with even width and even height?Thanks@SleepyShashwat
•  » » 8 months ago, # ^ |   0 A binary matrix is called good if every even length square sub-matrix has an odd number of ones.
•  » » 8 months ago, # ^ |   0 It is described in the sample explanation below the testcases
 » 8 months ago, # |   +5 Problem B was too easy , should have been a little harder...
 » 8 months ago, # |   0 After solving A and B what should be the best thing to do?
•  » » 8 months ago, # ^ |   +1 Rest, I guess.
•  » » 8 months ago, # ^ |   +7 Looking at the scoreboard hahaha
•  » » 8 months ago, # ^ |   0 leaving
•  » » 8 months ago, # ^ |   0 Solve C.
•  » » » 8 months ago, # ^ |   -8 such an unbalanced round.
•  » » 8 months ago, # ^ |   0 Solve Problem C. XD
 » 8 months ago, # |   +18
 » 8 months ago, # |   +11 Me after solving A and B :-)
 » 8 months ago, # |   +18 Permutation lover SleepyShashwat
 » 8 months ago, # |   +19 From today, I started loving permutations because no one knows how you can play with permutations except the master SleepyShashwat. Truly a good and well implementation based round. Only DS can help :)
•  » » 8 months ago, # ^ |   +1 That's right! Only DS007 can help make future contests better!
 » 8 months ago, # |   +8 The problem statements were really nice :) But the difficulty could have been a bit higher for C.
•  » » 8 months ago, # ^ |   0 I havent studied graph theory till now sad.
•  » » » 8 months ago, # ^ |   +8 there is nothing to do with graph theory for c
•  » » 8 months ago, # ^ |   +2 C is perfect. Intuitional.
 » 8 months ago, # |   +17 Determine if the contest is good?
•  » » 8 months ago, # ^ |   +20 If Tx is the number of people solved task x, then the contest is good if Tj < Ti for any j > i
•  » » » 8 months ago, # ^ |   +13 For now, 13045 — 12108 — 5115 — 1169 — 61. Accepted!
 » 8 months ago, # |   +13 My JEE notes help me in solving question C
•  » » 8 months ago, # ^ |   0 JEE?
•  » » » 8 months ago, # ^ |   +2 In india this exam is to get into engineering colleges.
 » 8 months ago, # | ← Rev. 2 →   +5 Now this is what I call a Contest. loved it. Kudos to the author.
 » 8 months ago, # |   +4 Nice problem set! A good round after a long time :)
 » 8 months ago, # |   +11 Waiting for the end of the contest to start discussing the task E
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 PATH: if diameter of graph >= (n+1)/2 ^)   PAIRING: if otherwise, but how to construct?
•  » » » 8 months ago, # ^ |   0 Do dfs. In dfs tree if there is a path from root to any leaf with length >= (n+1)/2 we have solution PATH. Otherwise we pair nodes at same depth/level in dfs tree(because in worst case we won't pair only one node at some depth and from first check depth of the tree < (n+1)/2 so we will lose at most n/2 nodes during pairing which is valid).
•  » » 8 months ago, # ^ |   0 Root at any node. Find a dfs Tree.If the height is >=N/2 you have a path. Otherwise pair nodes on the same height.
 » 8 months ago, # |   +6 Nice contest, too bad I wasn't concentrated enough :(
 » 8 months ago, # |   0
 » 8 months ago, # | ← Rev. 2 →   +33 2 minutes of silence for these people.
•  » » 8 months ago, # ^ |   0 Do you mean problem C? D didn't have issues with mods
•  » » » 8 months ago, # ^ |   0 Changed.
•  » » 8 months ago, # ^ |   +1 or print((fact(n) - p(2, n - 1) + MOD) % MOD) Thanks to Errichto
•  » » » 8 months ago, # ^ |   0 In case someone wants the link, https://www.youtube.com/watch?v=-OPohCQqi_E
•  » » 8 months ago, # ^ |   0 I got -150 in C because of this issue :( .
 » 8 months ago, # |   +13 Solution of C:https://oeis.org/A059204
•  » » 8 months ago, # ^ |   0 I was so close T-T
•  » » 8 months ago, # ^ |   +1 :( I recognized how to solve it that permutation must have at least one dip but was not able to generalize the series. Thanks for OEIS link.
 » 8 months ago, # |   0 Pretest 6 For Problem C ????
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 negative number modulo
•  » » 8 months ago, # ^ |   0 print answer modulo (ans%mod+mod)%mod ;)
•  » » 8 months ago, # ^ |   0 My solution got negative answer for n=100
•  » » 8 months ago, # ^ |   0 You getting WA because sometimes (n!)%mod < (2^(n-1))%mod. You need to add do (ans+mod)%mod
•  » » » 8 months ago, # ^ |   0 i m sad :(
 » 8 months ago, # |   +3 Such a nice D!
 » 8 months ago, # |   0 What's the pretest 3 for problem D
•  » » 8 months ago, # ^ |   0 I think some n=3 and m=300000.
•  » » » 8 months ago, # ^ |   +3 Hmm, but I am not getting what I am doing wrong
 » 8 months ago, # |   0 I liked the problemset.How to solve D? (I had understood that for n>=4 and m>=4 the answer is -1, but I don't understand what to do next).
•  » » 8 months ago, # ^ | ← Rev. 4 →   +9 Since $n \leq 4$ you can do dp[i][mask] in O($m * (2^{n})^2$)
•  » » » 8 months ago, # ^ |   0 "mask" means the type of the square?
•  » » » 8 months ago, # ^ |   0 oh, I should have thought about dp :( nice problem but.
•  » » » 8 months ago, # ^ |   0 n<=m so you don't need the min and max functions.
•  » » » » 8 months ago, # ^ |   0 Thanks, I guess I need to read problem statements more carefully.
•  » » » » 8 months ago, # ^ |   +3 Oof, wasted 10 mins altering it to work in the case where m < 4 and n >= 4 without seeing this.
•  » » 8 months ago, # ^ |   0 everybody got that part but man how should we place greedily anyone ??
•  » » » 8 months ago, # ^ |   0 I don't think that it's possible to do it greedily.
•  » » » » 8 months ago, # ^ |   0 that's why I wasted a lot of time next time I will make sure when dp is possible just apply it.
•  » » 8 months ago, # ^ |   0 n!-2^(n-1) is the answer.
•  » » » 8 months ago, # ^ |   0 why?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +4 number of permutations is n!. And you have to count how many permutation of the form (2,1,3) do you have because that gives you a cycle between 1,2,3. (and 3,1,2 too). The permutations which are not from this type is 1,2,..n (increases) and after n decreases. And that number is 2^(n-1). (with 2,1,3 i mean some v[i-1] > v[i] < v[i+1] not just 2,1,3)
•  » » » » » 8 months ago, # ^ |   0 Didn't the question asked to find the total permutations of length given n? For n=4, is [4, 2, 3, 1] having length cycle of length 4? As per the definition given, vi and vi+1 share an edge for all i (1≤i
•  » » » » » » 8 months ago, # ^ |   0 I agree but i cant see your point. 4,2,3,1 has a cycle of length 3 so i don't care if has a cycle of length 4.
•  » » » » » » » 8 months ago, # ^ |   0 Sorry I misinterpreted the question.From the statement, "Given n, find the number of cyclic permutations of length n. Since the number may be very large, output it modulo 109+7.". I thought, we need to find permutations whose cycle length is n.
•  » » » » 8 months ago, # ^ |   0 Total permutations = n! Permutations without cycles = 2^(n-1) I'll explain how I got 2^(n-1): For any permutation, if there is no cycle in it then it should follow this logic: 1)For any i,(1<=i
•  » » 8 months ago, # ^ |   +2 Use simple permutations and combinations and the principle of inclusion and exclusion :)
 » 8 months ago, # |   0 A very nice contest!! Problem statements were short and to the point.
 » 8 months ago, # | ← Rev. 2 →   0 oeis solution of C but I found it at the last minute after my original solution kept failing for large numbers -_-
 » 8 months ago, # |   +11 People with WA/RTE/TLE on A. Care to explain your soln?Congrats Beta_R for getting hacked on A twice.
•  » » 8 months ago, # ^ |   +2 maybe Levon2004 can shed some light on this
•  » » » 8 months ago, # ^ | ← Rev. 3 →   -11 iches uzum aber?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   -8 1 77
•  » » » 8 months ago, # ^ |   -8 1 6 4 RRRR RRRR RRRR RRRR RRRR RRRC
•  » » » 8 months ago, # ^ |   -8 1 57
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0
•  » » 8 months ago, # ^ |   +3 I have a feeling that it was done on purpose to gain hacking points.
•  » » » 8 months ago, # ^ |   0 Yeah, they have an if statement to get hacked lmao: if(TN==1 && n==57){
•  » » » » 8 months ago, # ^ |   0 Yeah It was done on purpose. Levon2004 has hacked both A(twice) and B with the same technique.
•  » » » » » 8 months ago, # ^ |   -8 asgardianadhi я просто смотрел решения и увидел что решения Beta_R неправилный и взломал специально нечего не сделал
 » 8 months ago, # |   +3 how to solve D? I found it really hard to find answer for min(n, m) = 3 because there were too many states
•  » » 8 months ago, # ^ |   0 Yeah I also got stuck in that case. Waiting for the editorial!!
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 there are only 4 states. 1)from {(000), (111)}(consider which of these two require min change) to {(010), (101)} and visa-versa. 2)from {(100), (011)} to {(001), (110)} and visa-versa. check this
 » 8 months ago, # | ← Rev. 2 →   0 Has the core idea behind C appeared in a contest in the last year or so? I remember solving a problem which had the same idea (sequence must increase then decrease, find number of ways) not too long ago.
 » 8 months ago, # |   +76 3blue1brown styled Video Editorials:Problem A+B: https://www.youtube.com/watch?v=KJVigs8w-gg
•  » » 8 months ago, # ^ |   0 Not all heroes wear capes
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Nice one! Here's my 3b1b syled GIF simulation for Problem B's editorial: Thumbnail![ ]()Link to animated GIF: https://gifyu.com/image/cpDmFor people preferring video format: Link
 » 8 months ago, # |   0 problem D:if the matrix is 4 by 4 or greater size answer is -1. and for smaller matrixes, we need to get the answer?where I went wrong please help me?
•  » » 8 months ago, # ^ |   0 so far so correct but real question starts after that if you don't want to brute force every case.
 » 8 months ago, # |   0 can we solve D without brute-forcing every case separately?
•  » » 8 months ago, # ^ |   0 I think we can XOR the bits (0s and 1s) and come up with a simple approach for dp. I couldn't do it in time though.
•  » » 8 months ago, # ^ |   +1 if(n>=4) must -1 so we care of n<=3
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 What should be the states for n==3 ?I couldn't figure it out.
•  » » » » 8 months ago, # ^ |   0 all 1 <= e <=m , arr[0][e] * 4 + arr[1][e] * 2 + arr[2][e] can make the bits. then we can use dp to solve the problem. build the array dp[length][8]
•  » » 8 months ago, # ^ |   +9 I brute forced for n = 6 and m = 3 and my pc crashed.
 » 8 months ago, # |   0 Problem D: Am I right in thinking that if the no. of 1s in every 2X2 matrix is odd then no. of 1s in every 4X4 matrix will be even hence answer is -1 for all the matrices with n and m >=4? OR am I missing something. If I'm right, then how to go further?
•  » » 8 months ago, # ^ |   0 No that's correct, but the hard part is doing the dp for the min(n,m)=2/3 cases
 » 8 months ago, # | ← Rev. 2 →   +16 Shame on me for not reading the problem properly. I didn't read that only 'R' and 'D' were valid directions for problem B, so I implemented something way more complicated to deal with all 4 directions cardinal directions XD.
•  » » 8 months ago, # ^ |   0 Maybe this will help you fell better but you are not the only one :D I started implementing the solution with all directions, after about 10 minutes I saw that there was more than 2K Accepted solutions so I knew something was wrong, read the full statement again and solved it in 2 minutes :(
 » 8 months ago, # | ← Rev. 2 →   +3 the intresting fact about this contest was that nobody knew the proof for problem C but everyone solved it :))))
•  » » 8 months ago, # ^ |   +3 I saw that you can have a cycle iff you have a "dip" in the sequence. 95% sure that that's correct, so then I tried to count every permutation without a dip and saw that for every n, it was double the previous one. You're right, no actual proof though!
•  » » » 8 months ago, # ^ |   +11 The permutations that don't work are ascending and then descending. The number of them is the sum of (n-1) choose k from k=0 to n-1, and it's well known that it's equal to 2^(n-1). So the answer is n!-2^(n-1).
•  » » » » 8 months ago, # ^ |   0 Interesting. I'll think about it. I was counting it in a more obscure way where I was summing over every possible leftmost element in the permutation so the answer wasn't obvious to me. Thanks!
•  » » » » 8 months ago, # ^ |   0 One way you can see why it's the sum of n-1 choose k from k=0 to n-1 is that you have a 1-1 correspondence between subsets of {1,...,n-1} and a not good permutation because you place all the numbers in your chosen subset to the left of n and then the remaining to the right of n (there is only one way to arrange these two subsets). Or you can just think of it as there being two choices for each number, being on the left of n or the right of n.
•  » » 8 months ago, # ^ | ← Rev. 4 →   0 i dont think so.. like when you would see, you will find that when the case is highest number is not at the ends then all such cases will result in cycle and when largest number is at ends there are some cases which will lead to cycle.That some cases are the cases from previous number so it's a recurrence relation. tn = (n-2)(n-1)!+2*tn-1How it needs proof!
•  » » 8 months ago, # ^ |   0 Non-valid permutations are the one which first increases then decreases, rest all are valid, and number of such permutaions are $2 ^$ $(n - 1)$. So ans is $n!$ $-$ $2 ^$ $(n - 1)$
 » 8 months ago, # |   0 Problem C was really fun. I saw a pattern and yolod it, and hopefully it passes all the tests LOL.
•  » » 8 months ago, # ^ |   0 plz share your solution if it possible... now system testing is running so I can't see...
•  » » » 8 months ago, # ^ |   0 https://gist.github.com/bananabrick/b1e7172b2656a86d71c7f2ff2a169b15I was in a hurry so the code is messed up LOL
 » 8 months ago, # |   0 proc C, to me, some kind of math proc isn't it?fact(n) — (fact(n/2)*fact(n/2+n%2)*fact(n-2))but large number factorial is neededjust my guess....
•  » » 8 months ago, # ^ |   0 you just have to apply mod anyway so while finding factorial apply mod.
 » 8 months ago, # |   +1 Problem C was really awesome and the statements were also quite perfect...
 » 8 months ago, # |   +2 Isn't the answer to C is fact(n) - 2^(n-1) ???
•  » » 8 months ago, # ^ |   0 Yes, it is!
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 Can someone please see why my solution to C failed on pretest 6 ? My answer is also fact(n) - 2^(n-1)?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +3 when fact[n] < 2^(n-1) you give a negative number. you have to add MOD and then apply %MOD again.
•  » » 8 months ago, # ^ |   +3 Yes...But there is modular arithmetic..
 » 8 months ago, # |   0 Apparently i misread the question for problem C where i was trying to solve for smallest and largest $j$ on right side of $i$ ,where as in question it was to consider both sides and by time i realised i misread the question,i had no mood to solve it,but it involved quicksort .How to solve question $C$ when edges for $i$ are considered only from elements of and involving same conditions right side of the array?
 » 8 months ago, # |   0 Nice problemset. I think D can be done by bitmask dp, correct me if I am wrong.
 » 8 months ago, # |   +8 How to determine if a round is good
 » 8 months ago, # | ← Rev. 2 →   +3 Really nice contest! D was the first dp problem I've done in contest in a while.Solution for D: If n>=4, the answer is -1. To see this, note that each 4x4 matrix is broken up into 4 2x2 submatrices that are disjoint. If the sum in each of these is odd, then the sum in the 4x4 matrix should be even, which is a contradiction.Now, we do cases on n=1 to n=3.For n=1, there are no even sub squares, so the answer is 0.For n=2, each column alternates between a sum of 1 or 0 mod 2, so theres only two cases to check here (whether the first row has sum 0 mod 2 or 1 mod 2), and that can be done in O(m).For n=3, you can use dp. Let dp[i][j] be minimum number of moves needed to get the first i columns to satisfy the problem constraints, with the ith row equal to j in binary (so, for example, if j=5, then the ith row would be 101). Then, dp[i][j] = min(dp[i][j],dp[i-1][k]+add), where k ranges from 0 to 8 and is the state of the previous row, and add is the number of moves to change the grid ith row to j in binary (so it would be 2 if the ith row was 000 and j=5 = 101 in binary). Answer is min(dp[m-1][j]) from j=0 to 7, and time complexity is O(m*4^n), but n=3, so it passes. There might be a more efficient solution.
•  » » 8 months ago, # ^ |   0 I think we can construct 4*3 matrix. I have constructed a 4*3 matrix in my copy?
•  » » » 8 months ago, # ^ |   0 N <= M`
 » 8 months ago, # |   +5 Thanks for such a nice contest! Short and concise, formal statements Good problems Good video Editorials Balanced Contest We want more such contests :)
 » 8 months ago, # |   0 E is a nice problem
 » 8 months ago, # |   0 Idk if I'm dumb, was anybody else confused with the "Cycle of length n", for n = 4 there weren't 16 cycle of length 4. Although there were 16 perms. which have cycle.
 » 8 months ago, # |   0 My solution for problem C failed on pretest 6 using C++. Later, I changed it to python and it worked. Can someone explain why?(Did n!-2^(n-1))
•  » » 8 months ago, # ^ |   0 because (fac-ans) can become negative
•  » » 8 months ago, # ^ |   +1 (a — b) % m = (a%m — b%m + m)%m
 » 8 months ago, # |   +9 Nice contest, math lovers for the win. I go back to Div4.
•  » » 8 months ago, # ^ |   +2 LolMost of em just AK'd problem C with OEIS!
•  » » » 8 months ago, # ^ |   0 But it still felt like more or less fair math, at least.
•  » » 8 months ago, # ^ |   +18 I am so used to seeing your name in blue that it feels weird when it is cyan.
•  » » » 8 months ago, # ^ |   +7 Thanks for your support ;)
•  » » 8 months ago, # ^ |   +1 no problem i believe that u can get whatever you lost within one contest..
•  » » 8 months ago, # ^ | ← Rev. 3 →   +2 YepA — trollforcesB — observation?C — math
 » 8 months ago, # |   0