### McDic's blog

By McDic, history, 2 years ago,

내가 돌아왔다! (Hello, Codeforces!)

I am thrilled to introduce you to Codeforces Round #633. Followings are basic information:

• This contest will take place on Apr/12/2020 17:05 (Moscow time).
• The round is rated for all participants who can understand this announcement. There will be two divisions.
• There are 5 problems in each division and you will have 2 hours to solve it.
• Score distribution will be announced later.

Followings are contributors:

Followings are some fun things:

• antontrygubO_o is the most intense coordinator I have ever met. He rejected lots of my problems. Some example of rejection comments are below:
• This problem is too standard.
• This problem is appeared in recent ptz camp with higher constraints.
• I don't like it.
• Rock Scissor Paper makes statement messy, because some people don't know about it.
• D2A should be easier than this one.
• I've found generalized version of this problem in POI.
• Isn't this obvious?
• This problem is not very interesting.
• This is too (censored).
• After lots of rejections, I tried my best to make problems to be interesting. I hope you like at least some of my problems.
• This round was originally supposed to be rated for Div.2 only. However, after we completed Phase 1 testing, we found that my round is too hard for Div.2, so we added more problems and made this round to be Div.1.
• In this round, statements will be even shorter than last contest.
• Even for some of problems which my coordinator approved, there were critical issues that made problems to be excluded. I will introduce some of my rejected problems which won't be used anymore in another post, after this contest ends.

I hope everyone can enjoy my third contest. Thanks in advance!

1. Score Distribution:
• Div.1: 500 1000 1500 2000 2750
• Div.2: 500 750 1250 1750 2250
2. I am sorry for such Div2C/Div1A statement issue. We fixed that immediately after few minutes to the round, but we should have announced it.
3. Editorial is posted: https://codeforces.com/blog/entry/75913
4. I opened new mashup for excluded problems. These problems are originally approved by antontrygubO_o but excluded for some reasons.
1. Binomial Determinant is old Div1D. We found this problem on google so we removed this.
2. Divisible Xor is old Div1A. But since we made 3 xor problems, we removed this one.

Followings are winners:

<Div.1>

<Div.2>

• +1622

 » 2 years ago, # |   +94 In this round, statements will be even shorter than last contest.I hope we will enjoy the problems. Thanks.
•  » » 2 years ago, # ^ |   -43 Only contest can keep us busy during this quarantine .:)
•  » » 2 years ago, # ^ |   -21 Another rated round?
 » 2 years ago, # | ← Rev. 2 →   +389 hope the statements will be as short as the announcement
 » 2 years ago, # |   0 WOW! Statements will be short let's see :)
 » 2 years ago, # |   -64 Is It Rated?
•  » » 2 years ago, # ^ |   +28 The round is rated for all participants who can understand this announcement.Don't you see it !!
•  » » » 2 years ago, # ^ |   +25 Can I decide after the contest if I understand the announcement? xD xD
 » 2 years ago, # |   0 so the round is going to be tough a bit , we are ready to face it and enjoy according to question haha.
 » 2 years ago, # |   +94 Are McDic and dick related?
•  » » 2 years ago, # ^ |   +74 No
•  » » 2 years ago, # ^ |   +28 Yes
•  » » 2 years ago, # ^ |   +52 What is a dick???
•  » » » 2 years ago, # ^ |   -34 (CENSORED)
•  » » » 2 years ago, # ^ |   +16 Basically a jerk
•  » » 2 years ago, # ^ |   +3 McDic is an Irish dick based in Korea.
 » 2 years ago, # | ← Rev. 7 →   -49 YES
 » 2 years ago, # |   +68 I've found generalized version of this problem in POI. A full trilogy of horror movie starts with this sentence...
•  » » 2 years ago, # ^ |   +38 Kind of reminds you of this
 » 2 years ago, # | ← Rev. 2 →   +33 who can understand this announcementThe task conditions will only be in English?
•  » » 2 years ago, # ^ |   +25 ah, no, there will be Russian statements available too.
 » 2 years ago, # | ← Rev. 2 →   +60 10 April to 15 April. There are 4 contests where I can participate. (Educational round 85,div2,div3,div2 again). Wow! Thanks to the authors who worked so hard to make our quarantine life happy. Thanks to codeforces too!
•  » » 2 years ago, # ^ |   +25 Unless if you get a rating increment after div 2 rounds such that you are no longer in div 3 :)
 » 2 years ago, # |   +20 Be prepared for the interesting behind story of every problem :)
 » 2 years ago, # | ← Rev. 2 →   +4 Just saw the contests page!! I literally got chills seeing the list of upcoming contests!! Thank you MikeMirzayanov as well as all the other writers for the upcoming contests!!
 » 2 years ago, # |   +111 Looking forward to McDic x Twice round!
 » 2 years ago, # |   +22 This Problem is too (censored) xD.
 » 2 years ago, # |   0 i hope we will enjoy this round
 » 2 years ago, # | ← Rev. 3 →   +34 Everyone, Look out for the unusual start time
 » 2 years ago, # |   +153
 » 2 years ago, # | ← Rev. 2 →   -30 .
 » 2 years ago, # | ← Rev. 2 →   -6 is there a hacking phase after this round?And can Div3 people write it ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 Hacking phase is generally for educational rounds and Div.3 rounds as this a classic Div.1 and Div.2 round there's no hacking phase and if a hacking phase is there it would be mentioned in the announcement and yes anyone who has rating below 1900 can give Div.2 round.EDIT: Since you seem new, people can hack each other's solution, if they're in the same room(all registrants are divided into rooms), during the contest. But after the contest there's no hacking phase.
 » 2 years ago, # | ← Rev. 2 →   +10 In this round, statements will be even shorter than last contest.And I instantly love it!
 » 2 years ago, # |   +2 when the editorials will be published i am curious to see the editorials....Thanks in advance to the problem setters who have setted the problem so good and interesting..
 » 2 years ago, # |   +3 Thanks to the whole team, I don't know what I'd be doing in these quarantine days if you were not there making these amazing problems!!!
 » 2 years ago, # |   +8 Omg it's McDic roundMcDic orz(Pls don't troll me again)
 » 2 years ago, # |   0 I bombed my last round so I hope I can do well on this one.
 » 2 years ago, # |   +9 Please Make strong test case ... And thanks CF for making more contest in our bad time to increase our ability..
 » 2 years ago, # |   0 Hope pretests are strong !!
 » 2 years ago, # |   +266 ..
 » 2 years ago, # |   +24 In this round, statements will be even shorter than last contestHopefully longer than April fools contest.
»
2 years ago, # |
-12

# mcdicorz

 » 2 years ago, # |   +98
•  » » 2 years ago, # ^ |   +32 (censored)
•  » » 2 years ago, # ^ |   +39 Sauce?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +16 was coding but going to washroom now.
 » 2 years ago, # |   +5 "(censored)"
 » 2 years ago, # |   +61 Perhaps you can create a Gym with the rejected problems. :)
 » 2 years ago, # |   +20 McDic orz! Even though you were assigned such a ruthless coordinator you kept on creating problems and came up with this geniosity round. McDic is so good I wish I had 1/x where x>1e9 of McDic's problemsetting skill.
 » 2 years ago, # |   +3 I really liked this blog and I am very excited to participate in your round after reading it!
 » 2 years ago, # |   +80 Is it true that tzuyu_chou is the real Tzuyu Chou from Twice?)
•  » » 2 years ago, # ^ |   -60 no
•  » » 2 years ago, # ^ |   +170 Yes
•  » » » 2 years ago, # ^ |   0 Dude don't know whether you are joking or saying the truth.But I will be honest I have seen this profile and I am awestruck how fast he/she improved from the first code he/she submitted like within 2 months to international grandmaster and I wish I can have that level of motivation and dedication in this time of quarantine. Thanks tzuyu_chou for motivating me...
•  » » » » 2 years ago, # ^ |   +52 Whether tzuyu_chou is the singer from Twice or not, it's pretty clear that they were already highly skilled when "their first code was submitted". So it's not some 2 month newbie->IGM miracle story.
•  » » » » » 2 years ago, # ^ |   +3 You are underestimating Tzuyu's skill. If she can sing as well as she does in Twice music, surely she has the talent to go newbie->IGM that quickly ;).
 » 2 years ago, # |   0 Loved the rejection comments part
 » 2 years ago, # |   0 I hope it will be easy so that I can enjoy the problems.
 » 2 years ago, # |   -33 "statements will be even shorter than last contest", if so than it will be really good for everyone I hope. Cz, long statement is so boring...
•  » » 2 years ago, # ^ |   -27 hmm
 » 2 years ago, # |   -44 isItrated
 » 2 years ago, # |   -17 Wow, interesting "Fun" statistics! We are equally thrilled to take part in the contest :D
 » 2 years ago, # |   -19 Haha, long queue again.
 » 2 years ago, # | ← Rev. 3 →   +33 Very interesting blog! Good coordinators help organize high-quality rounds in Codeforces and I am grateful.
 » 2 years ago, # |   +7 Hope that codeforces won't shut down tomorrow :)
 » 2 years ago, # |   -12 hey no one has yet asked whether this contest is rated or not?? P.S — i know it is ! But some people still ask the question ;)
 » 2 years ago, # |   +31 Well, how about a separate section for memes in code forces?
 » 2 years ago, # | ← Rev. 2 →   +83 Your proof is wrong.Well this doesn't sound like a very unreasonable explanation for rejecting a problem..
 » 2 years ago, # | ← Rev. 2 →   +12 For the first time I am seeing someone coming with score distribution this early.
 » 2 years ago, # |   -24 waiting for formula and theorem forces...
 » 2 years ago, # |   +97 Is tzuyu_chou going to perform a private live concert for the winner of this contest (of course after coronavirus ends)?
•  » » 2 years ago, # ^ |   +64 Unfortunately, she already did it for organizers and testers of the round.
•  » » 2 years ago, # ^ |   +75 That would be the most serious I've ever been in a contest...
 » 2 years ago, # |   +861 As some people strongly requested, I post one of archived funny conversations here:
•  » » 2 years ago, # ^ |   +25 That's just sad :(
•  » » 2 years ago, # ^ |   0 He didn't even give you hope that all your problems are great :(
•  » » 2 years ago, # ^ |   +107 Is antontrygubO_o a weeb?
•  » » » 2 years ago, # ^ |   0 I heard he isn't
•  » » » 2 years ago, # ^ |   +46 Everyone's a weeb deep in their heart.
•  » » » 2 years ago, # ^ |   +42
•  » » » » 2 years ago, # ^ |   -43 honestly, this is trash even for a white coder sorry.
•  » » 2 years ago, # ^ |   +175 If your answer was 1, he would said "I accept 1 of your problems".
•  » » 2 years ago, # ^ |   0 Lmao
 » 2 years ago, # |   +14 Short statements, 5 questions. Quality will be epic! Looking forward to participating.
 » 2 years ago, # |   +29 Is iterated?
•  » » 2 years ago, # ^ |   +10 who is nupur XDXD
•  » » 2 years ago, # ^ |   0 it is pointer!
 » 2 years ago, # |   +5 fan ei ae yo
 » 2 years ago, # | ← Rev. 2 →   0
 » 2 years ago, # |   0 Good Luck everyone
 » 2 years ago, # |   0 Back to back rated contest , I am enjoying it and after knowing questions are going to be shorter as compared to usual ones ,felling more excited.
 » 2 years ago, # |   -17
 » 2 years ago, # | ← Rev. 2 →   -8 5 problems in 2 hours?? "In this round, statements will be even shorter than last contest.", i hope it would make the contest interesting.
 » 2 years ago, # |   0 Just look at the number of upvotes for the announcement of the contest. It is way more than average.
 » 2 years ago, # |   0 Lots of contest in this week ...
 » 2 years ago, # | ← Rev. 2 →   +18 I am registered in Div1 and Div2 bcz of my recent rating change XD. What happens now?
•  » » 2 years ago, # ^ |   +16 I think you will be moved automatically, I'm in a similar situation.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +48 Participate in Div1. If predictor says -ve delta just resubmit them in div2 to compensate.
 » 2 years ago, # |   +9 In this round, statements will be even shorter than last contest. (looks at 1329C - Drazil Likes Heap) That's not so impressive.
•  » » 2 years ago, # ^ |   +7 I'm sure he meant "his last contest".
•  » » » 2 years ago, # ^ |   +8 Fair 'nuff.
 » 2 years ago, # |   0 I'm ready for the contest. Good luck and high rating !
 » 2 years ago, # |   0 how many questions do u need to solve to hit specialist??...in a DIV 2 contest I AM DESPERATE!!!!!!!!!
•  » » 2 years ago, # ^ |   +9 It's an ELO System, so it depends on how the others perform. To be honest, it will probably be enough to solve just one problem (or maybe 0), since the base rating is 1500.
 » 2 years ago, # | ← Rev. 2 →   -19 Gulag: It's time to earn your freedom
 » 2 years ago, # |   +19 A long queue in submissions right now. Server was down yesterday. I hope it doesn't happen in the contest.
 » 2 years ago, # |   0 how many questions would a pupil need to solve in a regular DIV 2 contest to hit specialist???
•  » » 2 years ago, # ^ |   +2 Either 2 problems very fast or 3 problems during contest.
•  » » 2 years ago, # ^ |   +6 2 and quick enough!
•  » » 2 years ago, # ^ |   0 I think it is ok to take 30 minutes to solve two problems.
 » 2 years ago, # |   -36 tourist doesn't register the contest yet ?
 » 2 years ago, # |   +15 Will there be contest today considering the server problem?
 » 2 years ago, # | ← Rev. 3 →   +6 McDic [user:MikeMirzaynov] I do not know if this is happening only with me, the submission takes a lot of time to get checked since past few days. I request you to make sure that the same does not happen when contest is running. Thanks, Kushal Shah.
•  » » 2 years ago, # ^ | ← Rev. 2 →   -35 good
 » 2 years ago, # | ← Rev. 9 →   -141
•  » » 2 years ago, # ^ |   +5 I would be more worried about the opposite thing — in such situations people sometimes want to prove that they can prepare really hard problems and eventually round becomes too difficult.
•  » » 2 years ago, # ^ |   +24 Don't forget he is the author of 3400 rated problem.
 » 2 years ago, # |   0 hope that the round does not turn out to be unbalanced, 5 problem contests are unbalanced more often than not :(
 » 2 years ago, # |   +4 juicy round :)))
 » 2 years ago, # | ← Rev. 3 →   +1 (MikeMirzayanov) Is it just me, or m3.codeforces.com is not working? (403 Forbidden, nginx/1.16.1)m1, m2, and the main site are okay, though.
 » 2 years ago, # |   +39 I predict Div2C will be a math problem and Div2D will be a graph problem.
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   +5 OMG.Can you predict Div1C and Div1D of the next round? It would be very useful to me :D
•  » » » 2 years ago, # ^ |   +46 I will predict for you but first show me da money.
 » 2 years ago, # |   -9 I hope I become specialist in this round. And expert sometime sooner.. :)
 » 2 years ago, # |   -8 i need help. i understand the question but i fail to implement the logic and my code are never optimized.. please any suggestion.
 » 2 years ago, # |   0 All the best guys !!!
 » 2 years ago, # |   0 Hey, for some reason my registration did not work, I cannot submit!!!:/
 » 2 years ago, # |   -39 The comment removed because of Codeforces rules violation
 » 2 years ago, # |   0 Speedforces
 » 2 years ago, # |   -76 Please stop creating problems.
•  » » 2 years ago, # ^ |   +15 I accidentally upvoted this one :(
•  » » » 2 years ago, # ^ |   0 I accidentally downvoted you :)
 » 2 years ago, # | ← Rev. 4 →   -37 Thor is reading F just after D. Fill in the Blank? XOR
 » 2 years ago, # |   -34 The comment removed because of Codeforces rules violation
 » 2 years ago, # |   +9 Statements are short, but damn are my ideas wrong.
•  » » 2 years ago, # ^ |   0 Same feeling. I did the contest badly ;-;
 » 2 years ago, # |   0 ridin ba in contestaye shokhmitoon
 » 2 years ago, # |   0 Your problems are excellent, but please consider the difficulty distribution of the problems. I think "After Solving ABC" might appear in one of the comments after the contest.
•  » » 2 years ago, # ^ |   +30 If that's the case, then there's no solution. Contests are not meant to be solved fully by everyone smh
 » 2 years ago, # |   +322 I hope I won't see soon more "guessing pattern shit" problems like today $C$. Other problems were nice and interesting for solving.
 » 2 years ago, # |   +75
 » 2 years ago, # |   +27 When the first place becomes two
 » 2 years ago, # |   +274 Really disliked problem Div1 C. Somewhat disliked Div1 D but I haven't seen the solution yet so I am giving it the benefit of the doubt. The former was just bad, though.
•  » » 2 years ago, # ^ |   -9 Can you explain why? I think both were fine.
•  » » » 2 years ago, # ^ |   +194 The simplest way to solve Div1 C is to write a bruteforce and find a pattern. This doesn't require any CS-related skills and often feels like a maths competition.Div1 D probably boils down to some DP on a tree, and I don't mind it, but it's just not pleasant to try and figure it out in terms of these loops. It feels like it's a really straightforward solution hidden by a really unpleasant abstraction.
•  » » 2 years ago, # ^ |   +46 I think D is a really nice problem. C is not something spectacular, but I think it is refreshing to see some "code and see pattern" problem from time to time and I don't think they are fundamentally wrong.
 » 2 years ago, # |   +8 Wtf was pretest 3 of C?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Not sure but i think it was like97 6 8 7 6 8 7 6 8
•  » » » 2 years ago, # ^ |   0 What should the result be?
•  » » » » 2 years ago, # ^ |   0 29 is sizeso you can make 8 8 8 8 8 8 8 8 8
•  » » » » » 2 years ago, # ^ |   0 Ah shit! RIP my rating, never deserved it anyways
•  » » » » » 2 years ago, # ^ |   0 Please, can you explain it why is ans= 2?
•  » » » » » » 2 years ago, # ^ |   0 for x=1 you can make 7 6 8 8 6 8 8 6 8 from original array.for x=2 you can make 7 8 8 8 8 8 8 8 8
 » 2 years ago, # |   +1 gg
 » 2 years ago, # |   +24 Tourist is back to the top.
 » 2 years ago, # |   +39 Can someone explain why 1D was not maximal independent set on a tree? :(
•  » » 2 years ago, # ^ |   +8 Look at the sequence of bands $b_1, b_2, \dots, b_k$ that form an answer. For each vertex $v$, if $v$ is adjacent to $b_l$ and $b_r$, it must be adjacent to each $b_i$ for $l \leq i \leq r$
 » 2 years ago, # |   +4 how to do Div2.C/Div1.E?
•  » » 2 years ago, # ^ |   +6 exchange 1 with 2.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Brute force a bunch of values and observe the pattern for all the $a$, $b$, and $c$ values separately, assuming you're talking about Div2E/Div1C.
•  » » » 2 years ago, # ^ |   0 What's the pattern? jef
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 The bits of the middle col go like 00 10 11 01 and the right col like 00 11 01 10 List in binary0000000000000100 0000000000001000 0000000000001100 0000000000000101 0000000000001010 0000000000001111 0000000000000110 0000000000001011 0000000000001101 0000000000000111 0000000000001001 0000000000001110 0000000000010000 0000000000100000 0000000000110000 0000000000010001 0000000000100010 0000000000110011 0000000000010010 0000000000100011 0000000000110001 0000000000010011 0000000000100001 0000000000110010 0000000000010100 0000000000101000 0000000000111100 0000000000010101 0000000000101010 0000000000111111 0000000000010110 0000000000101011 0000000000111101 0000000000010111 0000000000101001 0000000000111110 0000000000011000 0000000000101100 0000000000110100 0000000000011001 0000000000101110 0000000000110111 0000000000011010 0000000000101111 0000000000110101 0000000000011011 0000000000101101 0000000000110110 0000000000011100 0000000000100100 0000000000111000 0000000000011101 0000000000100110 0000000000111011 0000000000011110 0000000000100111 0000000000111001 0000000000011111 0000000000100101 0000000000111010 0000000001000000 0000000010000000 0000000011000000 0000000001000001 0000000010000010 0000000011000011 0000000001000010 0000000010000011 0000000011000001 0000000001000011 0000000010000001 0000000011000010 0000000001000100 0000000010001000 0000000011001100 0000000001000101 0000000010001010 0000000011001111 0000000001000110 0000000010001011 0000000011001101 0000000001000111 0000000010001001 0000000011001110 0000000001001000 0000000010001100 0000000011000100 0000000001001001 0000000010001110 0000000011000111 0000000001001010 0000000010001111 0000000011000101 0000000001001011 0000000010001101 0000000011000110 0000000001001100 0000000010000100 0000000011001000 0000000001001101 0000000010000110 0000000011001011 0000000001001110 0000000010000111 0000000011001001 0000000001001111 0000000010000101 0000000011001010 0000000001010000 0000000010100000 0000000011110000 0000000001010001 0000000010100010 0000000011110011 0000000001010010 0000000010100011 0000000011110001 ... 
•  » » » 2 years ago, # ^ |   +11 And what pattern is?I found that indices 3i forms 1, 4-7, 16-31, 64-127, and so on. But indices 3i + 1 not lies in any pattern I can assume). Indices 3i + 2 is just 3i ^ (3i + 1).
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +3 I didn't have time to figure it out completely, but the $b$ values in binary looks like this: Spoiler00000000000000000000000000000010 0 00000000000000000000000000001000 1 00000000000000000000000000001010 2 00000000000000000000000000001011 3 00000000000000000000000000001001 4 00000000000000000000000000100000 5 00000000000000000000000000100010 6 00000000000000000000000000100011 7 00000000000000000000000000100001 8 00000000000000000000000000101000 9 00000000000000000000000000101010 10 00000000000000000000000000101011 11 00000000000000000000000000101001 12 00000000000000000000000000101100 13 00000000000000000000000000101110 14 00000000000000000000000000101111 15 00000000000000000000000000101101 16 00000000000000000000000000100100 17 00000000000000000000000000100110 18 00000000000000000000000000100111 19 00000000000000000000000000100101 20 00000000000000000000000010000000 21 00000000000000000000000010000010 22 00000000000000000000000010000011 23 00000000000000000000000010000001 24 00000000000000000000000010001000 25 00000000000000000000000010001010 26 00000000000000000000000010001011 27 00000000000000000000000010001001 28 00000000000000000000000010001100 29 00000000000000000000000010001110 30 00000000000000000000000010001111 31 00000000000000000000000010001101 32 00000000000000000000000010000100 33 00000000000000000000000010000110 34 00000000000000000000000010000111 35 00000000000000000000000010000101 36 00000000000000000000000010100000 37 00000000000000000000000010100010 38 00000000000000000000000010100011 39 00000000000000000000000010100001 40 00000000000000000000000010101000 41 00000000000000000000000010101010 42 00000000000000000000000010101011 43 00000000000000000000000010101001 44 00000000000000000000000010101100 45 00000000000000000000000010101110 46 00000000000000000000000010101111 47 00000000000000000000000010101101 48 00000000000000000000000010100100 49 00000000000000000000000010100110 50 00000000000000000000000010100111 51 00000000000000000000000010100101 52 00000000000000000000000010110000 53 00000000000000000000000010110010 54 00000000000000000000000010110011 55 00000000000000000000000010110001 56 00000000000000000000000010111000 57 00000000000000000000000010111010 58 00000000000000000000000010111011 59 00000000000000000000000010111001 60 00000000000000000000000010111100 61 00000000000000000000000010111110 62 00000000000000000000000010111111 63 00000000000000000000000010111101 64 00000000000000000000000010110100 65 00000000000000000000000010110110 66 00000000000000000000000010110111 67 00000000000000000000000010110101 68 00000000000000000000000010010000 69 00000000000000000000000010010010 70 00000000000000000000000010010011 71 00000000000000000000000010010001 72 00000000000000000000000010011000 73 00000000000000000000000010011010 74 00000000000000000000000010011011 75 00000000000000000000000010011001 76 00000000000000000000000010011100 77 00000000000000000000000010011110 78 00000000000000000000000010011111 79 00000000000000000000000010011101 80 00000000000000000000000010010100 81 00000000000000000000000010010110 82 00000000000000000000000010010111 83 00000000000000000000000010010101 84 00000000000000000000001000000000 85 00000000000000000000001000000010 86 00000000000000000000001000000011 87 00000000000000000000001000000001 88 00000000000000000000001000001000 89 00000000000000000000001000001010 90 00000000000000000000001000001011 91 00000000000000000000001000001001 92 00000000000000000000001000001100 93 00000000000000000000001000001110 94 00000000000000000000001000001111 95 00000000000000000000001000001101 96 00000000000000000000001000000100 97 00000000000000000000001000000110 98 00000000000000000000001000000111 99 00000000000000000000001000000101 100 00000000000000000000001000100000 101 00000000000000000000001000100010 102 00000000000000000000001000100011 103 00000000000000000000001000100001 104 00000000000000000000001000101000 105 00000000000000000000001000101010 106 00000000000000000000001000101011 107 00000000000000000000001000101001 108 00000000000000000000001000101100 109 00000000000000000000001000101110 110 00000000000000000000001000101111 111 00000000000000000000001000101101 112 00000000000000000000001000100100 113 00000000000000000000001000100110 114 00000000000000000000001000100111 115 00000000000000000000001000100101 116 00000000000000000000001000110000 117 00000000000000000000001000110010 118 00000000000000000000001000110011 119 00000000000000000000001000110001 120 00000000000000000000001000111000 121 00000000000000000000001000111010 122 00000000000000000000001000111011 123 00000000000000000000001000111001 124 00000000000000000000001000111100 125 00000000000000000000001000111110 126 00000000000000000000001000111111 127 00000000000000000000001000111101 128 00000000000000000000001000110100 129 00000000000000000000001000110110 130 00000000000000000000001000110111 131 00000000000000000000001000110101 132 00000000000000000000001000010000 133 00000000000000000000001000010010 134 00000000000000000000001000010011 135 00000000000000000000001000010001 136 00000000000000000000001000011000 137 00000000000000000000001000011010 138 00000000000000000000001000011011 139 00000000000000000000001000011001 140 00000000000000000000001000011100 141 00000000000000000000001000011110 142 00000000000000000000001000011111 143 00000000000000000000001000011101 144 00000000000000000000001000010100 145 00000000000000000000001000010110 146 00000000000000000000001000010111 147 00000000000000000000001000010101 148 00000000000000000000001010000000 149 00000000000000000000001010000010 150 00000000000000000000001010000011 151 00000000000000000000001010000001 152 00000000000000000000001010001000 153 00000000000000000000001010001010 154 00000000000000000000001010001011 155 00000000000000000000001010001001 156 00000000000000000000001010001100 157 00000000000000000000001010001110 158 00000000000000000000001010001111 159 00000000000000000000001010001101 160 00000000000000000000001010000100 161 00000000000000000000001010000110 162 00000000000000000000001010000111 163 00000000000000000000001010000101 164 00000000000000000000001010100000 165 00000000000000000000001010100010 166 00000000000000000000001010100011 167 00000000000000000000001010100001 168 00000000000000000000001010101000 169 00000000000000000000001010101010 170 00000000000000000000001010101011 171 00000000000000000000001010101001 172 00000000000000000000001010101100 173 00000000000000000000001010101110 174 00000000000000000000001010101111 175 00000000000000000000001010101101 176 00000000000000000000001010100100 177 00000000000000000000001010100110 178 00000000000000000000001010100111 179 00000000000000000000001010100101 180 00000000000000000000001010110000 181 00000000000000000000001010110010 182 00000000000000000000001010110011 183 00000000000000000000001010110001 184 00000000000000000000001010111000 185 00000000000000000000001010111010 186 00000000000000000000001010111011 187 00000000000000000000001010111001 188 00000000000000000000001010111100 189 00000000000000000000001010111110 190 00000000000000000000001010111111 191 00000000000000000000001010111101 192 00000000000000000000001010110100 193 00000000000000000000001010110110 194 00000000000000000000001010110111 195 00000000000000000000001010110101 196 00000000000000000000001010010000 197 00000000000000000000001010010010 198 00000000000000000000001010010011 199 00000000000000000000001010010001 200 00000000000000000000001010011000 201 00000000000000000000001010011010 202 00000000000000000000001010011011 203 00000000000000000000001010011001 204 00000000000000000000001010011100 205 00000000000000000000001010011110 206 00000000000000000000001010011111 207 00000000000000000000001010011101 208 00000000000000000000001010010100 209 00000000000000000000001010010110 210 00000000000000000000001010010111 211 00000000000000000000001010010101 212 00000000000000000000001011000000 213 00000000000000000000001011000010 214 00000000000000000000001011000011 215 00000000000000000000001011000001 216 00000000000000000000001011001000 217 00000000000000000000001011001010 218 00000000000000000000001011001011 219 00000000000000000000001011001001 220 00000000000000000000001011001100 221 00000000000000000000001011001110 222 00000000000000000000001011001111 223 00000000000000000000001011001101 224 00000000000000000000001011000100 225 00000000000000000000001011000110 226 00000000000000000000001011000111 227 00000000000000000000001011000101 228 00000000000000000000001011100000 229 00000000000000000000001011100010 230 00000000000000000000001011100011 231 00000000000000000000001011100001 232 00000000000000000000001011101000 233 00000000000000000000001011101010 234 00000000000000000000001011101011 235 00000000000000000000001011101001 236 00000000000000000000001011101100 237 00000000000000000000001011101110 238 00000000000000000000001011101111 239 00000000000000000000001011101101 240 00000000000000000000001011100100 241 00000000000000000000001011100110 242 00000000000000000000001011100111 243 00000000000000000000001011100101 244 00000000000000000000001011110000 245 00000000000000000000001011110010 246 00000000000000000000001011110011 247 00000000000000000000001011110001 248 00000000000000000000001011111000 249 00000000000000000000001011111010 250 00000000000000000000001011111011 251 00000000000000000000001011111001 252 00000000000000000000001011111100 253 00000000000000000000001011111110 254 00000000000000000000001011111111 255 The bit at index $i$ has a period of $2^{i+2}$ for even $i$ and $2^{i+1}$ for odd $i$, after the first few values.
•  » » » » » 2 years ago, # ^ |   0 Thanks
•  » » » » 2 years ago, # ^ |   +3 If you print $a, 2 a - b$, you get a pattern in blocks of $4^i$.And blocks of $4^i$ can be seen as a repetition of smaller blocks of size $4^{i-1}$.
•  » » » » » 2 years ago, # ^ |   0 Thanks, finally saw it
 » 2 years ago, # |   0 How to solve Div2 B and C?
•  » » 2 years ago, # ^ |   0 B. just sort the array and pick "last-first", "2nd last- 2nd"....done.C. find index 0<=iarr[j]. find Max= (arr[i]-arr[j]) over all such pair using prefix_max and then find least (k+1) s.t. 2^0+2^1+....+2^k>=Max. done!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 Div2 B: Sort the array. alternatively, put the last and first element to the end of resultant array.Div2 C: create a auxiliary lmax[], lmax[i]: max ele upto ith ele from beginning of the array. let cur[i]=lmax[i]-arr[i], res = OR of all cur[i], output the log2(res)
•  » » » 2 years ago, # ^ |   0 Could you elucidate Div2 C, please?
•  » » » » 2 years ago, # ^ |   +1 Notice that any integer can be formed by summations of powers of 2 (e.g. 0b1101 is just sum of 2^0 + 2^2 + 2^3 and so on) so you just have to find the max drop(i.e. max diff a[i] — a[j] where i < j). If max diff <= 0 then you already have a non-decreasing array so your done. If it's greater than zero, than just find the smallest x where 2^x — 1 >= max diff and you are done.
•  » » » » 2 years ago, # ^ |   +1 See Here . I hope it helps
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 For B:  sort the array fill result array like (a[1],a[n], a[2],a[n-1], a[3],a[n-3] ...) reverse result print result For C:  for all values of x in (0,35) check whether you can create non-decreasing seq to check, assume you have (1<<(x+1)-1) available to be added to any element
 » 2 years ago, # |   +33 endless XOR……
 » 2 years ago, # |   +7 How to solve div2 D?
 » 2 years ago, # |   +9
 » 2 years ago, # |   +67
 » 2 years ago, # |   +3 is DIV 2 B tough or what??
•  » » 2 years ago, # ^ |   +3 Nope simple! just sort the array and pick "last-first", "2nd last- 2nd"....similarly...done.
•  » » » 2 years ago, # ^ |   +3 thx man..sometimes the most obvious is the most elusive...:)
 » 2 years ago, # |   +29 I've never seen a better/prettier Problem A. Great Job!!
•  » » 2 years ago, # ^ |   +3 How to solve? Was the answer just n?
•  » » » 2 years ago, # ^ |   +4 Yes
•  » » » 2 years ago, # ^ |   +4 Once you set a vertical diamond, observe that you are forced to use horizontal diamond in other places. Lets say n=3 then we will have VHH. HVH amd HHV where V is vertical and H is horizontal diamond. That's why answer is n.
•  » » » 2 years ago, # ^ |   +7 Yeah and by just checking how to cover the top left triangle, you get the recurrence F(n) = 1 + F(n-1) along with F(1) = 1Which means the answer is simply n
 » 2 years ago, # |   0 For Div2.C76384708 — used log2() to find the most significant set bit. WA on pretest 3.76387989 — Removed log2() and wrote a loop. Pretest Passed. Why?
•  » » 2 years ago, # ^ |   +3 Floating precision errors, maybe? It's good practice to always avoid using floating point operations unless absolutely necessary.
•  » » 2 years ago, # ^ |   +6 log2 is a floating point function, so it's imprecise.
•  » » » 2 years ago, # ^ |   0 Is there any other function which can be used to find the most significant set bit of a number?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +14 31 - __builtin_clz(x)
•  » » » » » 2 years ago, # ^ |   +13 __lg(x)
•  » » » » » » 2 years ago, # ^ |   -11 I prefer __builtin_clz because it's actually documented and meant to be used by programmers.
•  » » » » » » » 2 years ago, # ^ |   +2 I'm sorry but that sounds like a really dumb reason to not use what has been provided.
•  » » » » 2 years ago, # ^ |   +3 I ran a loop from j=0 to j=31 and checked if 2^j>number (where ^ here is power). It's not an O(1) thing but it's log(10^9) and doesn't increase the overall complexity by much.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 You should type cast log2, otherwise, there can be overflow on converting double to long long
•  » » 2 years ago, # ^ |   +3 language precision problem — 4.0000000 can be 3.999999999
•  » » 2 years ago, # ^ |   0 you either took floor of log or ceiling.If floor then floor of log(5) is 2 while the most significant bit is the third.If you took ceiling then ceil of log(8) is 3 while the most significant bit is the fourth.
•  » » 2 years ago, # ^ |   0 same happened to me I just put (int) before log2
•  » » 2 years ago, # ^ |   0 Same problem with me too. Loop is working
 » 2 years ago, # | ← Rev. 3 →   +10 >tfw probably finished coding D minutes after the endMy idea for div1D: for a sequence of vertices on a path, get (sum of their degrees) — (number of adjacent pairs at distance 2) — 2 * (number of pairs at distance 1). The answer is the maximum of this value, simple DP.UPD: Also minus (number of adjacent pairs at distance 3).
•  » » 2 years ago, # ^ |   0 Sorry if I'm missing something simple, but what does it mean to be an adjacent pair at distance 2? Doesn't adjacent imply that they are at distance 1?
•  » » » 2 years ago, # ^ |   +8 Adjacent in the sequence of vertices I mention — such that the vertex between them isn't in the sequence.
 » 2 years ago, # | ← Rev. 2 →   -20 What an amazing contest ! Each of the problems required good thought (except maybe C). This is not the first time McDic held back some problems while setting up a contest. I look forward to hearing the remaining problems which were not published as part of this contest !Also, can someone please share the solution for Div 2 $E$ or Div 1 $C$ ?
•  » » 2 years ago, # ^ |   0 Brute force, print in binary, and find the pattern.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 IT's a greedy solution. you will observer that first element of triplet is all elements of even power of two, 1,-,-,4,-,-,5,-,-,6-,-,7,-,-,16,-,-...after this you can get n lies in which triplet. convert 1st element into binary,subdivide binary string to set of 2 elements and replace {'11':['01', '10'], '10':['11', '01'], '01':['10', '11'], '00':['00', '00']}.you will get what to append at 2nd and 3rd element.and [1st, 2nd, 3rd][n%3] is your answermy sol — 76392709
•  » » » 2 years ago, # ^ |   0 its the first time ever i got the write logic for div 2 E i m literally so fukin happy ...
 » 2 years ago, # | ← Rev. 2 →   0 Can some one suggest me some similar problems with today's div2 a, b? I didn't understand a correctly and couldn't solve b..It will be helpful. Thank you.
•  » » 2 years ago, # ^ | ← Rev. 6 →   0 Never seen a task similar to B. I have first set constraints of what are the possible solutions to the problem and then started juggling with different ways to traverse an array. The first intuition that I got was that probably we need to sort an array (but I wasn't sure about that). Usually, when you set some structure, that simplifies your task (whatever that task is). If you just go through indices from 0 to n or in reversed order from n to 0 in a sorted array that doesn't solve the problem. I started thinking of what is breaking when you simply traverse array in a sorted order. The next thing I tried in my mind is to traverse from some other starting point from a[i] to a[n]. That also failed. Then I thought if I have set first two elements in a sequence a[i], a[i + 1] what should the third element be in order to guarantee an increasing sequence? a[i], a[i + 1], a[x???].After that, somehow my brain had aha moment and came up with a sequence a[i], a[i + 1], a[i — 1], a[i + 2], a[i — 2], ....
•  » » » 2 years ago, # ^ |   +1 What is about? What does the problem even meant by "2 coverings are different if some 2 triangles are covered by the same diamond shape in one of them and by different diamond shapes in the other one."?
•  » » » » 2 years ago, # ^ |   0 What does the problem even meant by Oh, I also didn't understand that description and simply ignored it. I just went straight to example at the bottom and worked through it myself. Then I interpolated the example with n = 2 to n = 3 and started thinking hard about the case when n = 3.
 » 2 years ago, # |   +137 D is another stupid tree dp. It seems antontrygubO_o wasn't harsh enough.
•  » » 2 years ago, # ^ |   +125 I feel like this is a case when novelty of the setting justifies a somewhat standard solution.
•  » » » 2 years ago, # ^ |   +10 For me, "new but has a simple standard solution once you figure out a basic condition" isn't good enough for div1D. It depends on the condition and if it is what I mentioned above, that's at most div1C level.
•  » » » » 2 years ago, # ^ |   +54 aid's concern seems to be not with the difficulty, but the problem itself. Anyway, judging by the standings it doesn't seem that poorly placed after all.
•  » » » » » 2 years ago, # ^ |   0 Well, his comments starts with "D is", so the fact that it's D should be relevant.We can't compare difficulties by number of solutions alone. Most people solve A-E, so the letter and difficulties of previous problems matter. Most people will be intimidated by the fact that it's D with a geometrical statement — I know I almost was. If it was B, it would've definitely had more solutions.
•  » » » » » » 2 years ago, # ^ |   +40 How else does one refer to a problem?If you have in mind some other requirements for a problem to be suitable, say, for a div1D, I'm curious to listen. It seems to me that a lot of people expect something along the lines of "$\geq x$ lines of code/$y$ sheets of formulas", but there are so many more interesting ways to give a good challenge.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -38 How else does one refer to a problem? Would "A is another stupid tree DP" sound exactly the same? If you have in mind some other requirements for a problem to be suitable, say, for a div1D, I'm curious to listen. X lines of code / y sheets of formulas would be just as bad, since it would still be "spot this standard thing and type fast". For me, the requirement for any problem is that the solution is sufficiently unique for people at its level. Some variation in this is okay, but such problems are still disappointing for me.I actually guessed the pattern directly from example case 2, but proved that it makes sense just in case. That's how straightforward solving it was.I would've swapped C and D just because of this. C wasn't that hard either but it would've probably been an interesting D for more high reds.
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +10 Would "A is another stupid tree DP" sound exactly the same? Luckily we're not there yet for such comments to appear. =) Anyway, I didn't mean to say I knew exactly what aid was thinking. the solution is sufficiently unique for people at its level Totally second this, but isn't reducing the setting to familiar terms a crucial part of the solution? AtCoder problems are a great example of this, when it's smooth sailing after one good observation, but it can take ages to make. On a different point, with problems like this perceived difficulty can vary a lot. We can agree that the solution is simple, but there are lots of high-rated people who didn't solve it with an hour to go.My take is that the problems like this are just not commonplace, outside of the current meta. This makes discussions about "good position" and "people with high enough rating" moot since none of these correlate well enough with ability to solve such problems. I, for one, would be happy to see such problems appear more often, but that's a matter of taste, of course.
•  » » » » » » » » » 2 years ago, # ^ |   0 Yeah, Atcoder problems are a good measuring stick here. I can think of two that fit the "spot simple solution" mold, but have their own twists on it: AGC040 E (div1D): The $O(N^2)$ DP is simple enough, but you also need to notice that only $O(N)$ states are meaningful. I actually didn't spot it, but it's not that hard. AGC027 E (div1D-E): A lot of obvious observations (like that each resulting letter corresponds to an initial substring) led me to a simple greedy solution that's also wrong. I needed to fix it, getting a more complicated greedy. A twist like that is what I'm missing in this div1D. It's okay to have such problems, they're just not very interesting to me.As for difficulty, if we're really going by the number of solutions, the previous D had 21 solutions in-contest and it wasn't particularly difficult, just harder to implement if you didn't have the right tools (see my solution where I just pasted my treap). The previous D in a 5-problem div1 round (618) had 28. This one had 92.
•  » » 2 years ago, # ^ |   +56 Huh, I think that understanding the setting and what the answer looks like is the main part of the problem and quite a lot of thinking. Dp is indeed extremely easy, but what's wrong with that?
•  » » » 2 years ago, # ^ |   +16 Well, to me this part was just looking at the picture for the first sample carefully, so I didn't find it interesting.
•  » » » » 2 years ago, # ^ |   +16 All LGM testers failed to figure this for a hour.
•  » » » » » 2 years ago, # ^ |   +61 You shouldn't judge testing by the standings alone. You didn't talk with me and I don't know what antontrygubO_o told you, but I think that total time I spend on this problem is less than one hour.It doesn't mean I think that the problem is easy, or bad, or unsuitable for div1D position. I think it is on better side of this round.
•  » » 2 years ago, # ^ |   +36 Dp alone is of course not fascinating, but I find the understanding of the structure in this proble quite amusing (which is of course main part of the solution) and I really liked it.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 My approach to solving that problem was ignoring the geometrical structure as much as possible... I guessed what to do from the sample explanation and kinda-proved that it makes sense. Basically: ok, so we want a sequence of paths with length $\ge 2$ where we can always backtrack at most 1 edge from the previous path, what happens if we backtrack more?
•  » » 2 years ago, # ^ |   +100 Another comment: job of coordinator shouldn't be to reject problems that aren't amazing, it's to reject problems that are unsuitable or obviously bad. Otherwise the bar for problems will be too high.
•  » » » 2 years ago, # ^ |   +39 I just read the blog and saw these phrases: This problem is too standard.I don't like it.Isn't this obvious?This problem is not very interesting. So I had high expectations.
•  » » » 2 years ago, # ^ |   +12 I disagree with this; you don't want your contests to be "solve this query on tree problem for the 13245th time with minor modifications"; that's boring to everyone involved and then the standings are just a measure of how fast you can implement tedious standard problems.rng_58 takes the stance of not setting a contest with problems he doesn't like, and everyone not named Radewoosh seems to appreciate his coordination job a lot (both in old topcoder rounds and recent atcoder ones).
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +39 It is April and AtCoder has had how many Div1 contests this year? If I count correctly, one?EDIT: response to below: that's partly byproduct of differences in way contest are curated, if you consider how many quality problems are featured in Div1 CF vs Div1 AtCoder in last year, CF wins at least for me. (no new comment as it's not so useful conversation)
•  » » » » » 2 years ago, # ^ |   +3 It has been 10 years and Codeforces has had how many comparable by quality contests?You have a point, obviously, but the other side also has.
•  » » » » » 2 years ago, # ^ |   +41 If you want more contests with problems between a very high bar and a relatively high bar, please try our ARCs (orange-circled contests). I think they are enjoyable for reds, and sometimes not too easy to solve everything.Of course, I'm well aware that the number of contests is not so large even if we count ARCs. I'm sorry for that — we ran out of good ideas, and I feel it's time to change the generation. So, now I'm trying to share my experience with writers and maroonrk, and next year he will give fresh ideas. I hope the situation will get better then.
 » 2 years ago, # | ← Rev. 2 →   0 Would this work in E?First notice that for any node D, the edges induce a total order of the nodes that have edges towards D. That is due to that special property. Next, notice that any graph has at least one node with in-degree over N / 2. Choose the one with the highest degree and attempt some sort of centroid decomposition: divide the nodes in 2 halves based on whether they point towards D (set A) or D points to them (set B). The ones that point to D form a total order via above observation. There's plenty of complex case work for computing the min distances that are obtainable while using nodes from both sides. The main algorithm basically treats these cases and then recurses on B. By the choice of D, these are at most N / 2, so you have at most logN recursive calls on exponentially smaller subgraphs which amortizes to N^2. Also, note it's important in the casework part that you choose D to be the one with biggest indegree because this guarantees that all nodes in A, have at least one node in B they point to (if this wasn't so, then those nodes that are pointed to by D and all of B have a higher indegree so would've been a better choice of D). Considering the cases it appears that all min-distances will be either undefined (so 614N) or at most 5. It may also be the case that you need to first recurse and then consider paths that go through both A and B.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +11 It's pretty easy to show that the min distance is at most 3 or it is undefined.Suppose that the min-length path from $a$ to $e$ is $a\to b\to c\to d\to e$. Then $a,c,d,e$ will form the forbidden subgraph.EDIT: Fixed.
•  » » » 2 years ago, # ^ |   +10 $a, c, d, e$, not $b, c, d, e$
 » 2 years ago, # | ← Rev. 2 →   0 .
 » 2 years ago, # |   +55 XorForces
 » 2 years ago, # | ← Rev. 2 →   -165 Div1C is the most beautiful problem I ever solved)UPD. OK, some people don't like 000/123/231/312 pattern
•  » » 2 years ago, # ^ |   0 Can you explain it?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +56 Let's notice that $4^n - 4^m$ is divisble by $3$. We can group numbers from $1$ to $4^{n-1}$ into triples.If {$a, b, c$} is the lexicographically smallest triple where $a \geq 4^k$ then {$4 * a, 4 * b, 4 * c$} is the lexicographically smallest triple where $a \geq 4^{k+1}$.How to find next triple after {$4 * a, 4 * b, 4 * c$}? We know that $(4*a) \oplus (4*b) \oplus (4*c) = 0$ and last two bits $4*a$ are $0$. It means that {$4*a+1, 4*b+2, 4*c+3$} is the next triple (after it {$4*a+2, 4*b+3, 4*c+1$} and {$4*a+3, 4*b+1, 4*c+2$})$x = ((k+2)$ % $4$)So if we want to find $k$-th triple {$a1, b1, c1$}, we can find $(k+2)/4$ triple {$a, b, c$}, multiply it by 4 (because $a = a1 / 4$, it can be proved) and add {$0, 0, 0$} (if $x = 0$) or {$1, 2, 3$} ($x = 1$) or {$2, 3, 1$} ($x = 2$) or {$3, 1, 2$} ($x = 3$)
 » 2 years ago, # |   -10 I have 1 hour to solve D but still didn't complete it. After discovering my first approach didn't work, i think it seems like using LCA. Hope next time :(
 » 2 years ago, # |   +5 Did some very weird thing for div-2 D and somehow worked.First, we find the lower bound. We claim that it's equal to 1 if all leaves are an even distance from each other (indeed, just set each value equal to each other and use the fact that aXORa =0). If any two leaves have an odd distance from each other, then the lower bound is 3 (but I don't know how to prove this -- it's probably some construction).For the upper bound, we note that if we have a sequence between two leaves that have more than 2 edges, then we can set all the values on the path distinct. If there are only two edges, we need the values to be equal. Thus, in both cases, the upper bound is equal to n-1-k, where k is the number of pairs of leaves that are 2 edges apart.
•  » » 2 years ago, # ^ |   +1 Why is this weird? This just seems like the correct solution.
•  » » » 2 years ago, # ^ |   0 Maybe weird was too harsh -- it's just that I barely convinced myself that this worked during the contest. I took a leap of faith and it worked I guess.
•  » » » » 2 years ago, # ^ |   +8 Ah, the good old proof by AC. Helps for some contests but it's also useful to make sure you know the correct reasoning after the editorial comes out :)
•  » » » » » 2 years ago, # ^ |   0 for the upper bound why is possible to give all other edges different values?
•  » » 2 years ago, # ^ |   0 For the upper bound, consider a case like6 1 2 1 3 1 4 1 5 1 6there are 5 leaves, all at a distance of 2 from each otheranswer here is 1 1
•  » » » 2 years ago, # ^ |   +5 Oh yeah sorry, k isn't the number of pairs. If a vertex has x children that are degree 1 and x>=2, then k+=x-1. We sum over all vertices.
•  » » 2 years ago, # ^ |   0 for the upper bound why is possible to give all other edges different values?
 » 2 years ago, # | ← Rev. 2 →   -11 .
 » 2 years ago, # |   +2 I still don't understand what is said on D2A. I have never seen a complicated line like 3rd para in D2A
•  » » 2 years ago, # ^ |   0 same here...
 » 2 years ago, # | ← Rev. 2 →   0 Div2-E was similar in statement like_this Div1-D but not in difficulty.
•  » » 2 years ago, # ^ | ← Rev. 2 →   -9 Basically, I am an author of both problems.
•  » » » 2 years ago, # ^ |   0 McDic Can you see my div2A submission record? My score is wrong?
•  » » » » 2 years ago, # ^ |   0 Repeted submission will reduce your score by 50 points.
•  » » » » » 2 years ago, # ^ |   0 Okay, I feel very sad.
 » 2 years ago, # | ← Rev. 2 →   0 MikeMirzayanov My question A was submitted twice on the Internet, all pretest pass, the submission time of the two before and after are 10 and 11 minutes, but my score is 432, obviously 50 points less, I want to know why? These are my second submissions:633div2Athe first has been skiped
•  » » 2 years ago, # ^ |   0 Successful resubmission will make previous submission as "failed submission" which costs you 50 points
•  » » » 2 years ago, # ^ |   0 Ok i just knew
•  » » » 2 years ago, # ^ |   0 MikeMirzayanov His two submission only differs by a new line at the end. I think this counts as repeated submission and maybe should be prevented?
 » 2 years ago, # |   -60 The most pathetic contest I've ever seen. Now I know why they call you a dick.
•  » » 2 years ago, # ^ |   +3 Bruh whats so pathetic about logical questions? All of div2 A,B,C had barely any lines of code if you think.I generally hate questions that are easier to solve but has heavy implementation like those with too many cases. This contest was honestly pretty amazing
 » 2 years ago, # |   +8 Well written brief statements with nice diagrams and interesting problems!
 » 2 years ago, # |   0 The only thing that prevent me for 30 min to output just N in problem A was this 1e18 it's confusing Lol :"It can be shown that under given constraints this number of ways doesn't exceed 1e18.
•  » » 2 years ago, # ^ |   +4 problem A kinda remained me of the Apirl's Fools day's problems when I found out the solution is simply output N.....
•  » » 2 years ago, # ^ |   0 What is actually told in D2A? I understand nothing.
•  » » » 2 years ago, # ^ |   0 same here..
•  » » » 2 years ago, # ^ |   0 Basically it asks you to find the number of ways to fill up the shape the statement defines. For instance, when N = 2, we can only use one vertical diamond and two horizontal diamonds to shape that form, in this case we have 2 ways to do that. For other input N, there are N positions for diamonds to be vertical, but we can observe that if we make one diamond vertical, the rest can only be horizontal, so the answer is just the number of vertical positions which is N.
 » 2 years ago, # |   +122 Hi setters,I would like to be unrated this round for the following reasons. For the question div1 A, the statement was misleading before it was changed without any form of notice. The original statement had Find the smallest number k such that you can make the array nondecreasing after at most k seconds.. This was very misleading since the variable k is also used to denote the number of indices chosen. This statement led me to think that you could only perform k operations at the kth second. I had this version of the question until around 20 minutes left in the contest when I decided to reload the page. I feel like this heavily impacted my rating negatively, so I would like to request to be unrated. Thank you.
•  » » 2 years ago, # ^ |   -45 Ok Boomer
•  » » 2 years ago, # ^ |   +83 I can't understand why some stupid announcements about obvious things clearly written in the statement are broadcasted pretty often, but changes in the statements are treated completely silently. I was once a victim of a silently changed faulty statements as well. antontrygubO_o any comment on this?
•  » » » 2 years ago, # ^ |   +52 Now I agree that not to broadcast this was a huge mistake. The statement was corrected at the 3rd minute of the contest, and I couldn't see a way how problem could be understood in a wrong way (all our testers (of the last phase at least) didn't notice anything suspicious). So I decided that the broadcast wasn't necessary.Of course, it's better to broadcast if there is even the slightest chance that someone might be affected, I'll do so in the future. Sorry to everyone who was affected... But I don't see a way how we can make this unrated to those who were affected, unfortunately. I'll do my best to not let this happen again, huh
•  » » » » 2 years ago, # ^ |   +20 Does Codeforces not have the functionality to unrate individuals? Like most people, I joined the contest as soon as it started, and never refreshed the page (what reason would there normally be to do so). I believe changing the problem statement without notice is completely unfair, especially when the statement reuses the same variable for different purposes almost directly after each other.
•  » » » » » 2 years ago, # ^ |   +31 There is no way we can check if someone was really affected by the issue or just doesn't want rating drop.
•  » » » » » » 2 years ago, # ^ |   +35 You have a point. Please make sure to broadcast changes to the statement in the future, especially when it is changed for clarity. If you cannot unrate this round, I do not believe it is a big deal since rating will correlate to the user's skill in the long run regardless. Anyways, thanks for noting the mistake. I will continue to look forward to future rounds.
•  » » 2 years ago, # ^ |   -10 you seem pretty smart lad. you will be up in your feet in no time. just look us poor wretched souls having a hard time..ha deary
•  » » » 2 years ago, # ^ |   0 Thanks man, I'm just extremely disappointed since I had higher expectations than -98, and I believe I could have done way better without the misleading statement :/
•  » » 2 years ago, # ^ | ← Rev. 2 →   -10 Good to know I wasn't the only one. I thought I might have interpreted the question incorrectly initially, didn't realize that the statement was corrected :|Doesn't affect me a lot since anyway I didn't solve it. Had a bad day today.
•  » » » 2 years ago, # ^ |   0 no, you aren't the only one.
 » 2 years ago, # |   +140 very bad problem C.
 » 2 years ago, # |   +92 Did antontrygubO_o really think that Div1C was interesting?
•  » » 2 years ago, # ^ |   -17 Yes. He is one of the strongest pusher of Div1C.
•  » » » 2 years ago, # ^ |   +49 That's really disappointing
 » 2 years ago, # |   +49 McDic Are you trying to achieve komedy?
 » 2 years ago, # | ← Rev. 2 →   0 76395656 Can anyone explain for me, why I got WA on pretest 3 :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Consider this test case 1 3 1 2 4 Check whether your solution satisfy the requirement.
•  » » » 2 years ago, # ^ |   0 The result for this test case is 2 4 1 and it still satisfies the condition
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 My bad.Try 1 4 1 2 4 5 Your solution should output 2 4 5 1, which is wrong then.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 aaaa, i know where im wrong @@My submission: cout << arr[mid + 1 + i] << " " << arr[mid - i] << " ";And just change possion:cout << arr[mid - i] << " " << arr[mid + 1 + i] << " "; and it ís accepted.Tks you :(
 » 2 years ago, # |   +83 One more reason to skip McDic rounds
 » 2 years ago, # |   0 Am I the only one who found div2A more difficult than B and C? I solved B in ~40 mins then stuck in A for the rest of the contest. Finally just guessed the answer and got AC. When I read C at the end, I was able to come with solution in ~20 minutes. Of course time was over. What the hell is wrong with me.
•  » » 2 years ago, # ^ |   +1 Same , i thought this can't be that hard but i moved on to B and C after doing them , came back to A and then did that. I had more than an hour for D , couldn't come up with a solution though
•  » » 2 years ago, # ^ |   0 I am stuck in A as well.Finally, I found that the answer is up to the number of the diamonds.But when i noticed that the answer does not exceed 1e18 as stated in the problem, i dare not submit it...
•  » » 2 years ago, # ^ |   +11 I solved D2A like how April Fool problem were solved. Got nothing from statement. Looking for sequence on input output. Finally print n and got pretest passed.
 » 2 years ago, # |   +13 Anyone else was confused in problem A because of this statement....? :/
•  » » 2 years ago, # ^ |   0 Yea, I saw that and figured the output couldn't be more than 10^9. I went ahead and did B and went back to A and was trying to figure out combinations before realizing that it was just n. IMO it was pretty misleading. TBF, the problem was 500 points, indicating an incredibly easy solution.
•  » » 2 years ago, # ^ |   +9 I was one of the people against this. lol
•  » » 2 years ago, # ^ |   +1 Maybe lost about 4-5 minutes for this line -_-
 » 2 years ago, # |   +28 Thanks for the contest! Some notes: Maybe we should set a limit on how many times XOR can be used in the problemset? (By the way, Russian statements for B and C probably should call it "XOR" and not bitwise exclusive OR, just for clarity) Is there any good solution for C except printing the sequence and finding the pattern? Probably output section in the statement should say what the output format is, not just say "Print the answer" – then we wouldn't need to reread the statement and check the samples for that.
•  » » 2 years ago, # ^ |   0 Can you tell the pattern? I couldn't able to figure it out.