### arsijo's blog

By arsijo, 4 months ago, translation, ,

Hi everyone!

The rated Codeforces Round #571 (Div. 2) will take place on Jun/28/2019 11:20 (Moscow time). This round is based on the Kremenchuk Summer Programming Cup 2019.

The contest is prepared by Dalgerok, Karasick, StasyaCat, antontrygubO_o, danya.smelskiy, and me.

You will have 2 hours and 15 minutes to solve 6 problems.

Good luck!

We apologize for the issue that happened with the problem B. The round is unrated. If you want to read my emotional reply about it, please read this.

• -802

 » 4 months ago, # |   +53 shortest blog for CodeForces round XD
•  » » 4 months ago, # ^ |   +4 I mean, you know the saying: Quality over quantity. xDAnyways, good luck to all participants!
•  » » » 4 months ago, # ^ |   +44 Lol, Quality!
 » 4 months ago, # | ← Rev. 2 →   -20 there is one more thing you wanna say
•  » » 4 months ago, # ^ |   0 That it will be unrated
 » 4 months ago, # |   +51 I hope the statement as short as the blog :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +15 Why hope? You won't even participate as far as I know.UPD: He is my friend, and I asked him about that, he said he won't participate in the whole contest.
•  » » » 4 months ago, # ^ |   -69 I'm sorry but his name is Black_Ghost, not "my friend".
•  » » » 4 months ago, # ^ |   +11 I guess he knew about problem B all along. He's happy now.
 » 4 months ago, # | ← Rev. 2 →   0 I got it all wrong, it was not you
 » 4 months ago, # |   -17 It was wonderful to set the contest for 2 hours and 15 minutes instead of 2 hours.
•  » » 4 months ago, # ^ |   -22 It will not affect much!
•  » » » 4 months ago, # ^ |   +92 It will not affect you and the people like me Who just solve 1 or 2 questions . :DAnd then they are done because they don't try to solve further .For others it matters a lot .
•  » » » » 4 months ago, # ^ |   0 Me either: I think it may cause lots of influence on somebody who can fix E or F But not for me. I'm a rookie player with only, only nothing.
 » 4 months ago, # |   +42
 » 4 months ago, # |   +105 You forgot to thank MikeMirzayanov for codeforces and polygon platform.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +55 It is always understood that we owe MikeMirzayanov for this awesome platform of programming.
•  » » » 4 months ago, # ^ |   +47 Somethings are called rituals!
•  » » 4 months ago, # ^ |   +41 ..and the round becomes unrated. LoL
 » 4 months ago, # |   0 What do they mean when it is said that the round is based on a certain competition? In this case the "Kremenchuk Summer Programming Cup 2019".
•  » » 4 months ago, # ^ |   +3 it means there was hosted (or there will be hosted) a local competition and they decided to use its problems at cf round
•  » » » 4 months ago, # ^ |   0 But wouldn't that mean that some coders might have already solved these problems?
•  » » » » 4 months ago, # ^ |   +1 They are asked not to participate
•  » » » » 4 months ago, # ^ |   +59 This round is during the official competition. Participants have no way to take part in this CF round.
 » 4 months ago, # |   +122 This day is my birthday, I hope I will become yellow
•  » » 4 months ago, # ^ |   +31 I think you will become Red instead of Yellow because it is your birthday #GPL
•  » » » 4 months ago, # ^ |   -7 lol
•  » » » » 4 months ago, # ^ |   +18 Do you mean — map lol; ?
•  » » » 4 months ago, # ^ |   +49 General Public License?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +9 farmersrice By GPL, he means Birthday Bumps. That's why he thinks nomapunk will get red instead of yellow. Happy Birthday nomapunk.
•  » » » » 4 months ago, # ^ |   -7 Its an Indian Acronym for G**** pe laat, literally meaning kicks on the ass
•  » » 4 months ago, # ^ |   0 Happy birthday in advance!
•  » » 4 months ago, # ^ |   -87 I hope you wont.
•  » » 4 months ago, # ^ | ← Rev. 3 →   -41 Btw, MikeMirzayanov, ban him. This guy is clearly using multiple accounts:https://codeforces.com/profile/nomapunkhttps://codeforces.com/profile/47th-Draganovhttps://codeforces.com/profile/ProgrammerSasha
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -11 It doesn't matter.
•  » » » » 4 months ago, # ^ |   -16 "It doesn't any matter,OK?" is grammatically incorrect. This is an example of a fact that actually does not matter, because there are few native English speakers on Codforces and almost none English is perfect here (including mine).On the contrary, if a person has two fakes from which he writes contests, he indeed shows disrespect for the competitive programming community. You may say, that i am writing from a fake account and show disrespect for the community too. This is a valid point, but i do not plan to write contests from this account and, therefore, wont affect the rating distribution and anything related with contests themselves. Secondly, i just wanted to write this using that exact handle.
•  » » » » » 4 months ago, # ^ |   +3 Disrespect
•  » » » » » » 4 months ago, # ^ |   +41
•  » » » » » » » 4 months ago, # ^ |   +12 Hmm, someone's alarm is set for 4:20...
•  » » » » » 4 months ago, # ^ |   +32 你好像将Codeforces拼错了because there are few native English speakers on Codforces
•  » » » » » » 4 months ago, # ^ |   -15 Another misprint)), just like yours. You see, i did not blame you for your minor mistake). It was just (probably not very good) example of what does matter, and what does not))
•  » » » 4 months ago, # ^ |   +8 Im curious over how you deducted that this person has multiple accounts.
•  » » » » 4 months ago, # ^ |   0 Firstly, each account contains his name somewhere. Secondly, code styles are exactly the same. Maybe i do not understand something in this world, but Alexandr Draganov is not such a prominent guy that someone will name himself after him and copy his code-style by purpose. At least this is highly unlikely.
•  » » » » » 4 months ago, # ^ |   0 Great deductive reasoning; I too arrived at the same conclusion.
•  » » 4 months ago, # ^ |   0 Anyway, i do not think that such "experienced" participant as you (Almost yellow!! Wow!! Greetings!!) should litter comments section with such junk. Leave this for some greens and grays (well, i do not want to discriminate people by their rating. Most low rated participants do not do this junk, but almost everyone who does it has low rating. Sorry, if you got insulted).
•  » » 4 months ago, # ^ | ← Rev. 2 →   +4 By the way, how do we know you are not a contribution s**t? Anyone can write this and gets tons of upvotes, and, therefore, contribution. This comment does not provide no useful information, no joke or funny meme, it is not a question. It does not provide anything! Although i realized that i can not understand cf community properly, i still have no idea why this got so many upvotes. So, lets conduct an experiment. I will write a similar comment and will see, whether it will get upvoted or not (i bet it wont).
•  » » » 4 months ago, # ^ |   +1 Shitposting is a perfectly valid mode of expression online
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Nowhere did he question the "validity" of shitposting; he's only referring to its benefits (or lack thereof). This is something I've noticed with Codeforces community lately as well. I hate to be the dry influx of what otherwise seems to be a mostly humorous thread, but I see this as an oppurtunity to engage in some discussion around the current faults of Codeforces.Many posts are obviously serious, and I believe there can be a variety of serious discussion instigated concerning these questions. A current challenge our community faces is that responses that do indeed offer some amuse, often from a more well-known (or higher rated!) user, but without creating practical benefit tend to get disproportionately upvoted. This encourages a system which ultimately deflects from the very core purpose of these forums: to present useful responses from knowledgeable individuals, and to help out beginners.Don't get me wrong — I enjoy reading these comments as much as the next one. But there is an undeniable shift in the community towards top accounts getting exposure based on responses that aren't necessarily as contributing to debate as others.
•  » » 4 months ago, # ^ |   +5 ohho, many many happy returns of the day, Happy Birthday in advance. :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +29 I hope to become yellow as well because it's nomapunk's birthday
•  » » 4 months ago, # ^ |   +1 Good luck.Happy birthday!
•  » » 4 months ago, # ^ |   +6 Happy Birthday!!! I wish you that each problem you solve would be as interesting as this rounds B!All the best!
 » 4 months ago, # |   -38 Again judges proved that div3 = div2 + div1
 » 4 months ago, # |   +63 The time is unusual.And it is friendly to Chinese！
•  » » 4 months ago, # ^ |   0 so strange I feel. Although I think in here, the words Rabbit said seems emotional and rude. But, both sides’ words are really harmful to this fair community and very disrespectful. I don’t know how everybody who looked at these comments, also upvote or downvote to both them thinks. At least I regards these behaviors are unreasonable.Ok, I’m just using my right to express how my feel, and also, take my downvote. Mmaybe a downvote can’t represent or change anything, there may be a lot of people on the other side. So what, that’s my right¯_(ツ)_/¯
 » 4 months ago, # |   -10 Do i need to register or can i directly participate..I don't see register button..
•  » » 4 months ago, # ^ |   +2 contest has ended. before contest you will see a register button
 » 4 months ago, # |   -12 May I become an orange color after this round?
•  » » 4 months ago, # ^ |   -45 No, you shouldn't :)
•  » » 4 months ago, # ^ | ← Rev. 4 →   -31 Unless you somehow get lucky and solve all of the problems, I'm sorry, but no.
•  » » 4 months ago, # ^ |   +22 I curse you with 2098 upper limit until a nutella comes and kisses you.
•  » » » 4 months ago, # ^ |   +4 Yeet! My curse is real :3
•  » » » » 4 months ago, # ^ |   +8 If this round rated I will get my dream come true.
•  » » 4 months ago, # ^ |   +16 I have solved ABCDF and rank40, you told me UNRATED?orange next time:)
 » 4 months ago, # |   0 New to codeforces and been reading this a lot "based on......". What does thos actually mean? Are the questions same, similar or based on something taught there??
•  » » 4 months ago, # ^ |   0 I'm pretty sure it means they are the same problems.
 » 4 months ago, # |   +5 Hi i'm very new to CP. I'm not sure if this is the right place to ask my question but sorry :-) I've joined CF recently. In my profile it is showing unrated. What should do to get rated.Please help me I want to improve. Thanks to all in advance
•  » » 4 months ago, # ^ |   +3 You must participate in atleast 1 contest to get a rating
•  » » » 4 months ago, # ^ |   +3 Hi Thank you But I've participated in code forces round 570 (DIV-3).
•  » » » » 4 months ago, # ^ |   +6 Rating takes some time to update after open hacking phase ends.
•  » » » » » 4 months ago, # ^ |   +3 Thanks a lot for your time Can you also help me how i can improve myself in DS and algorithms,
•  » » » » » » 4 months ago, # ^ |   0 https://codeforces.com/blog/entry/47516 This will help. :)
•  » » » » » » » 4 months ago, # ^ |   +3 :-) Thanks I'll solve
 » 4 months ago, # |   +3 Can someone give more information about the "Kremenchuk Summer Programming Cup 2019"?
 » 4 months ago, # |   +18 It's a nice time for Chinese CFer
•  » » 4 months ago, # ^ |   +9 It's bad time for some other users
•  » » 4 months ago, # ^ |   -40 Yes,it's a good Chinese-round.
•  » » » 4 months ago, # ^ |   +25 Orz xukuan
•  » » » 4 months ago, # ^ |   -13 I say nothing
•  » » » » 4 months ago, # ^ |   +19 Orz xukuan
•  » » » 3 months ago, # ^ |   +22 orz xukuan
•  » » » 3 months ago, # ^ |   +13 Orz xukuan who created $O(n ^ 2 \log n)$ Suffix-Array and $O(\log n)$ Merge-Sort :)
 » 4 months ago, # |   -14 Kek, authors have 3 IMO medals. Why not 3 golds, antontrygubO_o? :trollface:
•  » » 4 months ago, # ^ |   +14 I think much more important are gold IOI medals of arsijo and danya.smelskiy:)
 » 4 months ago, # |   -35 This day is my birthday, I hope I will become cyan.
•  » » 4 months ago, # ^ |   0 How'd your experiment go?
 » 4 months ago, # |   -9 good luck !hope good color for all ♥
 » 4 months ago, # |   +13 As a Chinese I think the time will be good for us.However, I'm in Russia now and thus the time is not that friendly for me to participate lol.
 » 4 months ago, # |   0 I was introduce with programming just 1.5 year ago. I have created my codeforces acount then. But still i don't know about the rating system. Anyone please help me to know about the rating system.
•  » » 4 months ago, # ^ |   +2 The practice is the only way if you want your rating to increase. I too am practicing.
•  » » 4 months ago, # ^ | ← Rev. 2 →   -6 You can read full details here. https://codeforces.com/blog/entry/20762Though in a nutshell, it works like, You perform well(compared to similar rated participants) your rating goes up, you perform bad it goes down.
 » 4 months ago, # |   +1 It feels to be good on Codeforces!
 » 4 months ago, # |   0 Contest time is suitable for Chinese.Good luck for everybody.
 » 4 months ago, # |   0 Hi everyone I want to solve questions on graphs and trees but i don't know basics about tree and graph.Please anyone help me from where i can learn basics and after that i can solve questions on graph and tree. Thanks in advance.
•  » » 4 months ago, # ^ |   +8 CP-algo At end of each article there are some problems to practice with.
•  » » 4 months ago, # ^ |   +2 Try E-maxx.
 » 4 months ago, # |   +59 Why contest delayed by 15 minutes? It's definitely a bad culture of Codeforces!
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 I think the purpose is to gain more participants, but since the start time is different from the usual contest, the fact that there are fewer participants is not strange. Anyway, it's time to read comments. :)
 » 4 months ago, # | ← Rev. 2 →   -6 :)
 » 4 months ago, # |   +4 Delayed by 15 minutes
 » 4 months ago, # |   +28 Sorry about the delay. We have some internet issues onsite.
•  » » 4 months ago, # ^ |   0 Thank you for fast explanation
 » 4 months ago, # |   0 Will there be a 12 hour period of hacks for this round after the contest?
•  » » 4 months ago, # ^ |   0 Nope.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +15 No. 12 hours hacking phase exist in Educational CF Round and Div.3 Round (and few more contests).
 » 4 months ago, # |   0 that internet issue again
 » 4 months ago, # |   +3 Seems that, codeforces is trying to maintain it's dignity(as well as uniqueness) by delaying contests nowadays.
 » 4 months ago, # |   +1 ![ ]() we are still waiting
•  » » 4 months ago, # ^ |   0 i can't see your text !!! :\
•  » » » 4 months ago, # ^ |   0 I can not see your comment's photo, too. (the comment that you wrote it 5 minutes ago. please use preview.)
•  » » 4 months ago, # ^ |   0 nice key-board . :) Would anyone please tell me the brand of it ??
 » 4 months ago, # |   -11 looks like that code forces is testing it's users's patience !!
 » 4 months ago, # |   +3 yes 15m delay ...…. Thx from Bangladesh !!! its Friday …. ( salat time if the contest start before time)
 » 4 months ago, # |   +1 So real!!!
 » 4 months ago, # |   0 Score distribution?
 » 4 months ago, # |   -11 I had registered for the contest . but during contest it showed i didn't register for the contest and thus couldn't submit solution . Please , Codeforces solve these type of problems soon.
•  » » 4 months ago, # ^ |   0 I went to m2.codeforces.com after contest was lagging at the start, maybe this will help others facing problems
 » 4 months ago, # |   +11 I think the sole purpose of this contest is drop my rating, getting easiest A and level goes high up from B.
•  » » 4 months ago, # ^ |   0 it's true about me too ; i'm exactly like you now !
•  » » 4 months ago, # ^ |   0 ur lucky,round became unrated
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Same here :)Had some network issues and couldn't submit 1st problem with good speed.But it's unrated now :DWe are lucky.
•  » » 4 months ago, # ^ |   0 When I noticed missing controls in my first attempt I skipped B and opened D (cause it has numbers in its name), quickly solved. C and E also nice problems. Was planning to get +200 rating today but somehow stopped, someone wants to see me in gray zone xD
 » 4 months ago, # |   +2 the contest is unrated now :(
 » 4 months ago, # |   +176 The problem setter of B should stop creating problems.
•  » » 4 months ago, # ^ |   +4 how to solve c , can u tell me
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +23 let sum(l, r) be the number of "1" appears in range[l, r] in the string a.and the answer is the number of range [l, r] that (sum(l, r) % 2) == (the number of "1" in string b % 2). and of course (r — l + 1) = |b|.you can see the code of my another account Dilute_ :P
•  » » » » 4 months ago, # ^ |   0 (sum(l, r) % 2) == (the number of "1" in string b)Can you clarify the above line please? Because LHS would always be 0 or 1
•  » » » » » 4 months ago, # ^ |   +2 I believe Dilute meant sum(l, r)%2 == (no of "1" in string b)%2because say there are x no of "1" in substring of a and y no of "1" in b and z be the no of "1" that are in same position in that substring and bthen required number of different will be x+y-2zso if x + y is even, that substring is counted in final answer
•  » » » » » » 4 months ago, # ^ |   0 Thank you and How you come up with this?! Do you have some similar problems on cf?
•  » » » » » » 4 months ago, # ^ |   0 how please explain or if u have link of similar problem share it
•  » » » » » » » 4 months ago, # ^ |   +5 Proof for problem C. ContestFuckerLet there be $x$ number of 1s in substring $c$ of given $a$ and $y$ number of 1s in substring $b$.Let $t$ be the number of 1s that match[overlap] in both the strings. So exactly $x-t$ number of 1s do not match in $c$ and exactly $y-t$ number of 1s do not match in $b$.Total mismatches = $x+y-2t$, we need to find whether this is even. $2t$ is even, so it's sufficient to check whether $x+y$ is even.56238050
•  » » » » » » 4 months ago, # ^ |   +9 Well.. It was my fault and I have fixed it now :DI just wrote the comment without checking carefully, but I just meant it modulo 2 QwQ
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 You do know that you are not supposed to have two accounts, right?
•  » » 4 months ago, # ^ |   0 LOL! But why? Is it because it was very difficult in comparison to the points assigned to it or because the judge's solution was wrong.
•  » » 4 months ago, # ^ |   0 Exactly. I didn't like that problem either.
•  » » 4 months ago, # ^ |   +89 I'm really interested in why so much people solved B...and their solution are all the same as the writer's wrong one...
•  » » » 4 months ago, # ^ |   +5 Because a lot of people follow their intuitions blindly :-)
 » 4 months ago, # | ← Rev. 2 →   -11 Honestly I'm really happy when this contest is unrated!
 » 4 months ago, # |   +10 anyway, will there be a tutorial for the B ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 I think the answer is (n+1)*(m+1)/6, but I didn't prove it yet.
•  » » » 4 months ago, # ^ |   0 its wrong
•  » » » » 4 months ago, # ^ |   +2 Can you show me the case my answer gives the wrong answer?
•  » » » » » 4 months ago, # ^ |   -9 Try 6 6 The answer is 7
•  » » » » » » 4 months ago, # ^ | ← Rev. 4 →   +22 NO. The answer is 8. And like this: 1 . 2 . 3 3 1 . 2 . . . . . . . 4 4 5 5 . . . . . . . 6 . 7 8 8 . 6 . 7 
•  » » » » » » » 4 months ago, # ^ |   0 Oh, you are right.
•  » » » 4 months ago, # ^ |   0 Also thought of this during contest, but was given WA on 3, also can't find any counterexample.
•  » » » 4 months ago, # ^ |   0 I think the answer is (n+1)*(m+1)/6, but I didn't prove it yet. Apart from proving, could you please explain your intuition?What is a resoning behing this formula?
•  » » » » 4 months ago, # ^ |   +3 It is now understood. An explanation by Noam527 was helpful.
•  » » » » » 4 months ago, # ^ |   0 I thought it by finding that when input is 13 17, the answer is 42. :)
•  » » » » » » 4 months ago, # ^ |   0 Are you kidding me? How could you find the right answer for this input during the contest? (13x17 seems to be too large for brute force.)
•  » » » » » » » 4 months ago, # ^ |   0 It is like this. A . B . C . D . E . F . G A . B . C . D . E . F . G . . . . . . . . . . . . . H . I . J . K . L . M . N H . I . J . K . L . M . N . . . . . . . . . . . . . O . P . Q . R . S . T . U O . P . Q . R . S . T . U . . . . . . . . . . . . . a . b . c . d . e . f . g a . b . c . d . e . f . g . . . . . . . . . . . . . h . i . j . k . l . m . n h . i . j . k . l . m . n . . . . . . . . . . . . . o . p . q . r . s . t . u o . p . q . r . s . t . u Actually not so hard..
•  » » » » » » » » 4 months ago, # ^ |   0 But how did you know that this tiling is an optimal?
•  » » » » » » » » » 4 months ago, # ^ |   0 In fact it is another intuition. So I checked another case: A A . B B . C C . D D . E . . . . . . . . . . . . E F F . G G . H H . I I . . . . . . . . . . . . . . J K K . L L . M M . N N . J . . . . . . . . . . . . . O O . P P . Q Q . R R . S . . . . . . . . . . . . S T T . U U . a a . b b . . . . . . . . . . . . . . c d d . e e . f f . g g . c . . . . . . . . . . . . . h h . i i . j j . k k . l . . . . . . . . . . . . l m m . n n . o o . p p . . . . . . . . . . . . . . q r r . s s . t t . u u . q But this case gave me same answer.
•  » » » » » » 4 months ago, # ^ |   0 Anyway, I like your choice!I mean, the Answer to the Ultimate Question of Life, the Universe, and Everything :)
 » 4 months ago, # |   +4 When you solve D problem the first time and contest becomes unrated :/
•  » » 4 months ago, # ^ |   +5 Don't worry, there are many who found D easy.
•  » » » 4 months ago, # ^ |   0 Same for F
•  » » 4 months ago, # ^ |   +12 D was easier than B and C (for me)
 » 4 months ago, # |   +1 The contest became unrated. :(
 » 4 months ago, # |   +1 The luckiest and unluckiest day of my life
 » 4 months ago, # |   0 What's the answer of this input for problem B? 4 4 
•  » » 4 months ago, # ^ | ← Rev. 2 →   -18 4
•  » » 4 months ago, # ^ |   +18 According to my code (which will not pass TCs), it should be 4.
•  » » 4 months ago, # ^ |   -8 Four
•  » » 4 months ago, # ^ |   -8 its 4
•  » » 4 months ago, # ^ |   -8 4
•  » » 4 months ago, # ^ |   -8 you can put the blocks in a clockwise(or counter-clockwise) way. The answer is 4.
•  » » 4 months ago, # ^ |   +24 I think answer should be 4. Arrangement can be like: 1 . 2 2 1 . . . . . . 4 3 3 . 4 
•  » » » 4 months ago, # ^ |   0 It looks like the answer is 1488
 » 4 months ago, # | ← Rev. 2 →   +74 It's 4:50 a.m. in my timezone.And the round is unrated.
•  » » 4 months ago, # ^ |   -6 4:50 a.m. lol :)
•  » » 4 months ago, # ^ |   0 where are you ?
 » 4 months ago, # |   +28 How to solve B?
 » 4 months ago, # |   +71
•  » » 4 months ago, # ^ |   +1 timo14z LOOOOOOL literally This is you :D
 » 4 months ago, # | ← Rev. 2 →   +13 arsijo please stop creating problems (с) (2).
 » 4 months ago, # |   +12 Let's solve problems for fun!
 » 4 months ago, # |   +3 Scored well for the first time. Round unrated. Can't laugh anymore at my fate. LOL crying inside
•  » » 4 months ago, # ^ |   +11 Completely reverse situation here XD.
 » 4 months ago, # |   -23 Round became unrated => Let's start down-voting the blog post :D
•  » » 4 months ago, # ^ |   +66 There was some problem in B, it affected a lot of people and hence unrated, doesn't mean we down vote him, it takes a lot of efforts to come up with problem ideas and write problem statements.
•  » » » 4 months ago, # ^ |   +13 I know man I appreciate all the effort, I up-voted him too, but it's some kind of Codeforces tradition.
•  » » » 4 months ago, # ^ |   +5 But it is also true for the problem setters to take responsibility for their mistakes.
 » 4 months ago, # |   +17 calm down...
 » 4 months ago, # |   +11 I wrote down last Div2 contest that from now on I will skip B's and work on C and D, and I managed to solve D while I didn't have even the slightest idea how to solve B (or C). Seriously guys, fix your B's and C's, C's are usually better and easier than B's because you put some stupid string/geometry tasks in B that are unnecessarily hard.
 » 4 months ago, # |   0 When the contest time is so convenient for you, but the round became unrated. SAD LIFE
 » 4 months ago, # |   0 Is this round unrated now?
•  » » 4 months ago, # ^ |   0 sad to say yes :(
•  » » 4 months ago, # ^ |   0 yes
•  » » 4 months ago, # ^ |   0 Can anyone give solution to problem C?
•  » » » 4 months ago, # ^ |   0 In Problem C, Look for every substring of length |b| in string a , Now, for every substring count the number of set bits and if the sum of set bits in a and string b are even then just add 1 to your answer.
•  » » » 4 months ago, # ^ |   +7 If there's an equal amount of 1's and 0's in string b and string(a.substr(i,b)) then their difference must be even.1010 and 1100 is a good example, no matter how you arrange those 1's and 0's, their difference will still be even.
•  » » 4 months ago, # ^ |   0 Ha radiya ;)
 » 4 months ago, # | ← Rev. 6 →   +141 I thought that author of problem B was just unlucky. Even many (it could be over 80%, maybe?) oranges or reds are solving with incorrect solutions. So it is not to surprise that all writers and testers solved in incorrect but same way. So, I can't gaze at the current situation which problem setter said to stop creating problems. And I don't think that it should be heavily downvoted, as same reason as Codeforces Round #373.
•  » » 4 months ago, # ^ |   +50 For such problems, I in general expect rigorous mathematical proofs of the claims made. So, I'd like to know if the proof went wrong somewhere, or did everyone else use some greedy-like technique?
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +13 Both are possible. It is possible that proof of problem B went wrong somewhere, judging by many orange of red coders tend to at least find a way to prove the optimality before coding. But it is also possible that authors "verified" their solution by brute-force check for small H and W, then got that it is same as kind of greedy-algorithm result.
•  » » 4 months ago, # ^ |   +64 I guess, just stresstesting author's solution with O($2^n * m$) will do the trick. But they are to lazy to write dp for 10 minutes or to prove something. So I think it should be heavily downvoted.
•  » » » 4 months ago, # ^ | ← Rev. 5 →   +16 How to calculate the optimal value with DP by $O(2n * m)$? I thought about it for five minutes and couldn't come up with it. I only came up with something like $O(2^{2n+α}×m)$ solution because we also need to think about "non-touching combination" and it will be like similar to $4×3$ tiles.Also, implementation is difficult. It is inevitable that tester thought that brute-force is enough for testing (if did), contrasting to heavy-implementation DP. Since the complexity of brute-force is about $O(2^{nm}×nm)$, it is no wonder they missed the minimal hacking case of $n=6,m=6$.
•  » » » » 4 months ago, # ^ |   0 Ok, all right, O($2^{2n} * m$). Ok, even brute-force is enough to find 6x6 test, isn't it?
•  » » » » » 4 months ago, # ^ | ← Rev. 6 →   +18 I manage to find optimal answer of $n=6,m=6$, but it took more than $45$ seconds with pruning brute-force algorithm written in C++. Here is the results of all possible testcase for $n \leq 6, m \leq 6$. The results are represented as the format H, W, the optimal answer, and the number of states in pruned DFS, in one line. My program took $67.535$ seconds to compute all of them. Solutions1 1 0 2 1 2 1 4 1 3 1 7 1 4 1 13 1 5 2 24 1 6 2 44 2 1 1 4 2 2 1 11 2 3 2 27 2 4 2 76 2 5 3 201 2 6 3 537 3 1 1 7 3 2 2 27 3 3 2 99 3 4 3 413 3 5 4 1601 3 6 4 6349 4 1 1 13 4 2 2 76 4 3 3 413 4 4 4 2638 4 5 5 15460 4 6 5 92817 5 1 2 24 5 2 3 201 5 3 4 1601 5 4 5 15460 5 5 6 133118 5 6 7 1190848 6 1 2 44 6 2 3 537 6 3 4 6349 6 4 5 92817 6 5 7 1190848 6 6 8 15985259My pruning algorithm is that "decide if there's a tile, from increasing order of pair (x,y), and prune if $size \geq 3$ 8-connected components appeared. I think my pruning algorithm is not perfect. But I at least can say that the situation difference between $(H,W)=(6,5)$ and $(6,6)$ is huge. UPD: Seems like $H=6, W=6$ was not even a minimal hacking case. I made a mistake in my calculation, and the intended answer was correct. Seems like E869120 made a more efficient brute-force (refer to this comment). But even he could not find the hacking case. It means that efficient brute-force cannot even find challenge case.
•  » » » » » » 4 months ago, # ^ | ← Rev. 3 →   +29
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 Sorry, I made a mistake in my calculation. $6×6$ is even correct. I thought that $7×7÷6=7.x$. What is the minimal hacking case, though?
•  » » » » » » 4 months ago, # ^ | ← Rev. 3 →   +3 $7∗7/6=8.16666666666667$
•  » » » » » » » 4 months ago, # ^ | ← Rev. 4 →   +32 Finally we managed to prove that the optimal answer will be exactly $⌊\frac{(H+1)(W+1)}{6}⌋$. The proof was rather difficult, but I liked it. It was a good example of IMO-like problem. I even think that the problem can re-appear, because now there exists a correct solution.
•  » » » » » » » » 4 months ago, # ^ |   +30 That's not how IMO problems look like... Though I haven't proved it yet, this problem absolutely requires lots of casework and details, and that's not the spirit of IMO.Also, this is a nice problem, but in my opinion, it is not suitable for CP contest since most people will just guess the answer without really proved it and the difficulty of the problem is mainly its proof.
•  » » » » » » » » 4 months ago, # ^ |   0 I provide it in Chinese. https://codeforces.com/blog/entry/68048
•  » » » » » » » » » 4 months ago, # ^ |   0 And thanks to gryphon who translate it into English like this.
•  » » » » 4 months ago, # ^ |   0 how to solve B using dp?
•  » » » 4 months ago, # ^ |   +347 You are right that this problem is not well-prepared. We could fix it. However, I absolutely do not agree that we were lazy. We spent a lot of time preparing this round. We fucked up, that is true. The main reason of this is me, because as a CF employee, I had to check everything. When we started to prepare the main contest, we did not want to hold a mirror. But in a week before the round, KAN told me that there is a need of a CF round at the end of this month. I recalled that we were organizing a contest at that period of time. Therefore, I decided to let people solve those problems too. Why do you think we do it? Why did we prepare round? Money? Shit no, if I wanted to earn money, I would prepare problem for Codechef, as many of my friends do. If we wanted to earn money from this round, we would give these problems to Codechef and earn much more. Instead of this, we decided to satisfy the need of CF users of a round. If you want to blame us because of it, go ahead, downvote the post (I am sure you did it), say that arsijo fucked up.
•  » » » » 4 months ago, # ^ |   +12 But this round didn't even have testers
•  » » » » » 4 months ago, # ^ |   +22 We had cross-testing. Authors of some problems tested other problems.
•  » » » » » » 4 months ago, # ^ |   +13 Well, then at least 1 tester of 5 should have written stress.
•  » » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 So you didn't prepare very well.
•  » » » » 4 months ago, # ^ |   +27 everyone makes mistakes, it is fine, ignore the haters
•  » » » » » 4 months ago, # ^ |   0 Lol, that is, if you are criticized, then they are wrong?
•  » » » » 4 months ago, # ^ |   +272 Nobody said you're doing it for money so I don't see a point in bringing it up. Especially in a comment that you linked in the announcement blog.
•  » » » » » 4 months ago, # ^ |   +8 So that more greedy coders start writing codechef problems instead of cf rounds :)
•  » » » » 4 months ago, # ^ |   0 I would start with the basic issue: that problem was completely inappropriate as div2 B. Perhaps if it was valued correctly, it would have been tested and proofed better...IMHO this type of problems should be forbidden in contests at all...
•  » » » » 4 months ago, # ^ |   +141 Meanwhile codechef: Why the fuck are you dragging us into this
•  » » » » » 4 months ago, # ^ |   -12 :D
•  » » » » » 4 months ago, # ^ |   +16 Codechef: Okay, okay we know we do fuck up every time, but this time it's not us B-)
•  » » » » 4 months ago, # ^ |   -13 I just want to say you are really a great man, and selfless. Good luck and look forward to your next contest!
•  » » » » 4 months ago, # ^ |   -76 You are absolutely right! But why don't you just stop creating problems? :)
•  » » » » 4 months ago, # ^ |   +5 So, will you publish editorial of this round ?
•  » » » » 4 months ago, # ^ |   +295 So basically you are saying that it is OK to make problems with incorrect authors solution as long as it is some local contest or Codechef round?
•  » » » » » 4 months ago, # ^ |   0 LoL.
•  » » » » 4 months ago, # ^ |   0 When we start system testing ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 arsijo rest are fine but u shouldn't dragged money and codechef in between. No sense of making these points here. you should really improve your problem quality, first your problem c of your previous round and now this.&& last thing codechef doesn't pay money to anyone who just come up with a random bad problem and puts it in contest without testing or juding its difficulty. .
•  » » » » » 4 months ago, # ^ |   +6 codechef problem authors get money bro...
•  » » » » » » 4 months ago, # ^ |   0 hello, I am saying, the way he is saying that if I want money I would have set problems for codechef, i said with these quality of problems and testing codechef will remove you after one contest. I know more than u.
•  » » » » » 4 months ago, # ^ |   0 what was wrong with the C problem in last arsijos contest?
•  » » » » 4 months ago, # ^ |   +6 Can you just run the system test？ I want to try other problems in the problemset.
•  » » » » 4 months ago, # ^ |   +44 Efforts can't win respect without taking responsibility.
•  » » » » 4 months ago, # ^ |   -9 arsijo fucked up.
•  » » » » » 4 months ago, # ^ |   -19 upvoted btw*
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   -10 Who doesn't shoot — will never miss.)P.S. Ok, maybe, someone didn't understand me. I don't think anything bad about authors of the round. It was a proverb and means "Everyone who does something sometimes makes mistakes" and it NOT BAD. It is a part of process.Peace.
•  » » » » 4 months ago, # ^ |   -10 How to prove that the solution of problem B is (n+1)*(m+1)/6?
•  » » » » 4 months ago, # ^ |   -10 Thank you very much! The problems are really interesting
•  » » » » 4 months ago, # ^ |   -6 What is a lot of time by the way? 10 hours?
•  » » » » 4 months ago, # ^ |   0 arsijo fucked up.
•  » » 4 months ago, # ^ |   +204 So it is not to surprise that all writers and testers solved in incorrect but same way. I completely disagree with this statement. A setter shouldn't try to solve a problem in 5 minutes and then call it a day. It isn't the only job of testers to get AC either.That being said, I don't like all the "stop creating problems" comments. To all setters: just make sure you write brute force solutions, you write down proofs, and that somebody will carefully read those proofs.
•  » » » 4 months ago, # ^ |   0 I wholeheartedly agree. I think that with just a little bit of extra testing, the quality of CF rounds in general will increase.
 » 4 months ago, # | ← Rev. 2 →   0 In problem B, the result for "6 6" should be "7" and for "8 8" it should be "13". I guess it's the problem for the solution and the point for my "Wrong answer on pretest 3" * 4 and "unsuccessful hacking attempt" * 2.
•  » » 4 months ago, # ^ |   +52 For 6x6, the answer would be 8 1 . 2 . 3 3 1 . 2 . . . . . . . 4 4 5 5 . . . . . . . 6 . 7 8 8 . 6 . 7 
•  » » » 4 months ago, # ^ |   0 Well, my fault...So can this problem be solved in O(1) time?
•  » » » » 4 months ago, # ^ |   +11 It might be ( n + 1 ) * ( m + 1 ) / 6
•  » » » » » 4 months ago, # ^ |   +113 YesFirst, if we extend 1x2 pieces to 2x3 (by adding a row to the bottom and column to the right), 2x1 to 3x2, and the board to (n+1)x(m+1), then we now only care about actual overlaps. This gives an upperbound of $\frac{(n+1)(m+1)}{6}$.Let's see how it's always possible to achieve the upperbound (from now we consider n and m as increased by 1):If we can always leave less than 6 free cells then we achieved the upperbound. Also notice that now $n, m \ge 2$.First, observe that whenever $6|nm$, we can cover the whole board. It can be seen easily for small $n$ (upto 7), and for larger $n$ we can always break the board into pieces with small $n$ and areas divisible by 6.This means that from a big board we can always remove pieces with height and width bigger than 1, and area divisible by 6. It only remains to leave less than 6 free cells when $n, m \le 7$ (if one of them is at least 8 we can remove 6 and obtain the subproblem). $n = 2, 3$: trivial. $n = 4$: place 2x3 blocks from the left. If you have < 2 columns remaining then it's okay, otherwise place a 3x2 piece. $n = 5$: when $m < 5$ we can use the above cases. $m = 5$ has a construction with a hole in the middle, $m = 6$ is divisible by 3, and $m = 7$ can use the hole from $m = 5$ + a 3x2 piece. $n = 6$: divisible by 6. $n = 7$: when $m < 7$ we can use the above cases, so now $m = 7$; there is a construction very similar to $n, m = 5$, which leaves a hole in the middle.
•  » » » » » » 4 months ago, # ^ |   +3 Looks right, but I could not prove the very first claim myself and then gave up. How to prove that if there is a correct placement of the 1x2 and 2x1 pieces, then the extended 2x3 and 3x2 pieces do not overlap?
•  » » » » » » » 4 months ago, # ^ |   +2 Consider most high right point these usual pieces touch. If it belongs to both pieces, they overlap. Now it belongs to one "hightest" piece. They overlap iff extended highest overlaps other one's highest rightmost point. It cannot overlap other one's extended side (the one we added, imaginary)
•  » » » » » » » » 4 months ago, # ^ |   0 Thanks! Still can't say I completely understood it but I got the idea.
•  » » » » » » » » » 4 months ago, # ^ |   0 if extended higher upper piece touches other usual piece, then both extended pieces collide. If it does not touch other usual piece, it does not touch its extension: (Same as if extended touch, usual pieces touch) If extension covers usual piece, then both usual pieces touch trivial. If both extended areas touch, then: a) Going higher on piece 2 collision (that is lower or right-er) from that point, we get to usual piece from piece 2, that piece also collides with extended 1, trivial case above. It cant go higher because piece 2 is lower. Also, all higher pieces collide and if there are no usual pieces 2 on that path, we can still use that fact. Let's take highest such point b) We get some other extended collision piece. By same argument, we can go left and find usual piece from 2 that collides with extended 1. This time, we know that going left once will get us to usual piece 2 (there is only 1 point with the property for both types of extended pieces). This time, this piece may not even touch extended 1, but be in lower left corner of it. So it touches usual 1 by our rules anyways (this one is extra case, others are trivial).Extended = piece with border. Extension = border (down and right) usual piece = original one, without extension
•  » » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 Thank you for the detailed explanationThis is the 7x7 case: (in case anyone was wondering) 7x71 1 2 2 3 3 3 1 1 2 2 3 3 3 1 1 2 2 4 4 4 8 8 8 * 4 4 4 8 8 8 6 6 5 5 7 7 7 6 6 5 5 7 7 7 6 6 5 5 
•  » » » » » » » 4 months ago, # ^ |   0 What does that state mean? I can't find the purpose of that state because the answer of input 7 7 is 10; like this: A . B . C . D A . B . C . D . . . . . . . E . F . G . H E . F . G . H . . . . . . . I I . J J . . and other solution also exists.
•  » » » » » » » » 4 months ago, # ^ |   0 In fact we say "7 7" means H+1=7 and W+1=7. So you should use "6 6" as input.
•  » » » » » » » » 4 months ago, # ^ |   0 It was in response to Noam527's comment. I think saying n=7 m=7 would be better. It's for a 6x6 gridFrom that convert 2x3 blocks into 1x2 blocks and 3x2 to 2x1 1 * 2 * 3 3 1 * 2 * * * * * * * 4 4 8 8 * * * * * * * 6 * 5 7 7 * 6 * 5 `
•  » » » » » » » » » 4 months ago, # ^ |   0 OK. I see.
•  » » » » 4 months ago, # ^ |   0 This has to be solved in O(1) time.
•  » » 4 months ago, # ^ |   0 me the same. my solution is (m+1)(n+1)/6 but "Wrong answer on pretest 3". I dont know why :((
•  » » » 4 months ago, # ^ |   0 Because the data of the problem was wrong
•  » » » » 4 months ago, # ^ |   0 but there're still many people AC that problem
 » 4 months ago, # |   +15 Delayed 15 min and turned out to be unrated. What a good round!!!
•  » » 4 months ago, # ^ |   +14 Something was fishy about this round from the start.
•  » » » 4 months ago, # ^ |   +30 From the announcement. You could see arsijo as author
•  » » » » 4 months ago, # ^ |   -9 i still remeber his previous round problem c. such worst problems. he says he doesn't do it for money, actually he does everything for money.
•  » » » » 4 months ago, # ^ |   +3 It's ok to complain about the contest, and downvote the blog, because he made a big mistake.But I don't see any reason to make personal attacks. If you can't find a way to give constructive feedback, just shut up.
 » 4 months ago, # |   0 A problem in EGMO contest 2019 is just a special case of Problem B today (they just ask to find the maximum with table of size 2n x 2n):https://artofproblemsolving.com/community/c6t520112f6h1818715_yet_another_domino_problem
•  » » 4 months ago, # ^ |   0 Nope. Those dominoes have to be 2 blocks away not 1. This problem is more similar to Croatian nationals 2019 where I would have won gold if I didn't misread a problem. (The problem is #3 on page 3, use google translate)
 » 4 months ago, # | ← Rev. 3 →   +17 What a shitty contest.Problem A kindergarten problem.Problem B is shit. Problem D is easier than B. Don't know who is testing these rounds.
•  » » 4 months ago, # ^ |   -22 Agree problem B was shit. And A was very tough :(
•  » » 4 months ago, # ^ |   +71 I agree with you, but please respect the authors. Preparing a round is difficult.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 I also agree that B in this game is very bad.
 » 4 months ago, # |   +32 What the f**k?I had a great score in this round and I can be a candidate master then it is unrated?I thank the authers very mucn and I know preparing a round is difficult. But I still think this is a little sad.Hope everyone can have a great score next time ans hope myself can be a candidate master. :(
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Today, somehow I managed to do the problem D and the contest got unrated. karma is a bitch!!
•  » » 4 months ago, # ^ | ← Rev. 2 →   +6 Come on. Keep training. Hope you can get a gratifying score in the next round. (And hope there isn't any grammar mistake in those sentences)
 » 4 months ago, # |   0 A perfect contest becomes bad because of problem. I feel upset.
•  » » 4 months ago, # ^ |   +9 How was the contest perfect in the first place?
 » 4 months ago, # |   +34 I am very very disappointed in codeforces. I woke up at 3:30 AM just to do this contest. I was actually pretty happy when I saw the problems because I knew how to solve them and I was predicted to get quite a bit of positive delta. But all of a sudden announcing that the round is unrated because the problem writers for some reason can't make good problems is quite discouraging. Imagine how many times I would have wanted round to be unrated in order to not lose rating. Maybe this should be a wake up call for all those creating contest: From weak pretests, to weak solutions, to weak language. All this can be avoided by testing thoroughly and thoughtfully.
•  » » 4 months ago, # ^ |   0 boo hoo cry kiddo hahahahah
•  » » » 4 months ago, # ^ |   0 Hey I am not a kid! I am almost 4 years old!
 » 4 months ago, # |   +4 Weird difficulty distribution.For me it is just like A < C < D < F < both B and EWhat thE HeLL???
•  » » 4 months ago, # ^ |   +1 Dude, I had to use SCAN to pass F, wtff ????
•  » » » 4 months ago, # ^ |   +7 My dumbest greedy algo' passed the pretests while I can prove it is neither right nor wrong lmaooooo
•  » » » » 4 months ago, # ^ |   0 And then failed on test 31 XD
 » 4 months ago, # | ← Rev. 2 →   +19 finally passed pretest of F have almost +200 on predictor, excited to become candidate master. And the next second it became unrated.....so upset.
 » 4 months ago, # | ← Rev. 2 →   +17 real shit contest ! hard B(even writer and many unofficial participant don't have solution). fucking implementation D and E with Case handling !please when you are writing problems be in participants shoes and don't write shitty problems !!!
•  » » 4 months ago, # ^ | ← Rev. 2 →   +9 What's wrong with shitty problems? Do you ask for nice problems in your real life too?
 » 4 months ago, # |   +45 How does it feel when 6 authors + testers + coordinators can't properly solve 7th grade math?
•  » » 4 months ago, # ^ |   +37 Moreover, there are 2 gold IOI medalists and 3 IMO medalists among them
•  » » » 4 months ago, # ^ |   0 Why is it so hard to make good problems? I am genuinely curious.
 » 4 months ago, # |   0 By the way, it was because of the problem B that I moved to D and could solve it. So, thanks anyway.
 » 4 months ago, # | ← Rev. 2 →   +215 UNRATEDThat's the result when you forgot to thank MikeMirzayanov for codeforces and polygon platform. :)
•  » » 4 months ago, # ^ |   0 I LMAO at this and I don't know why.
•  » » 4 months ago, # ^ |   0 it is the K A R M A T R I G G E R E D(nope
 » 4 months ago, # |   0 The problem setter of B should stop making questions. At last it became unrated. This was my debut round for becoming specialist XD. Someone wants to see me in green.
 » 4 months ago, # | ← Rev. 2 →   +4 OK,I can solve these problems for fun.But in fact it waste my time.But I won't decrease my rating.It's a lucky and unlucky day.
 » 4 months ago, # |   +3 Can someone give me counterexample to (a+1)*(b+1)/6 in B?
•  » » 4 months ago, # ^ |   0 As someone already pointed out, 6x6 can have upto 8 dominoes placed.
•  » » » 4 months ago, # ^ |   +5 7*7/6=8
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Ah, my bad. Consider 5x5 then — we expect 5*5/6 = 25/6 = 4 as the answer, but you can get 5.Edit: Oops, I'll just let someone else answer this before I make more blunders now :(
•  » » » » » 4 months ago, # ^ |   0 In 5x5 you can even have 6, and 6*6/6=6 .
•  » » » » » 4 months ago,