### vovuh's blog

By vovuh, history, 2 years ago, translation,

Miss Div. 3 rounds? :)

<copy-pasted-part>

Hello!

Codeforces Round #540 (Div. 3) will start at Feb/19/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD0: I also would like to thank zimpha and Arpa for help with the round testing and finding some bugs!

UPD: Due to the problems being really interesting the round will last 2 hours 15 minutes.

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Ghajini 7 259
2 ACtest 7 271
3 chrome 7 274
4 AuSquare 7 341
5 bonchinche 7 343

Congratulations to the best hackers:

Rank Competitor Hack Count
1 limstash 73:-9
2 MarcosK 59:-6
3 TheRoot 28:-1
4 yqdjl6 23:-6
5 2014CAIS01 24:-9
497 successful hacks and 574 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 1021869 0:00
B 15Y 0:05
C oldpreisnerboy 0:11
D1 omeravci372742 0:17
D2 Ghajini 0:17
E __1900__ 0:12
F1 Seidukan 0:10
F2 1021869 1:33

UPD3: Editorial is published!

• +180

 » 2 years ago, # |   -8 Div. 3 is back!
 » 2 years ago, # |   +11 Hoping to become expert with this contest.GoodLuck and High Rating to everyone!
•  » » 2 years ago, # ^ |   +6 big oof
 » 2 years ago, # |   +68 I wish all rated(<1600) users in this DIV-3 will be Unrated in the next coming div-3 rounds!:-)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +21 the only way it's happening is if next Div-3 will be unrated because of some problems. Is that what you wish?
•  » » » 2 years ago, # ^ |   -19 I'm pretty sure they wish those who are Div3 now soon to get over the 1600 threshold. They wish everyone a good performance, that is.
•  » » 2 years ago, # ^ |   +2 Hugdiya
 » 2 years ago, # |   0 Can anyone explain to me please, how the hacking session works? I would like to try it for this round. Thanks
•  » » 2 years ago, # ^ |   +5 Iirc you get 12 hours after the contest to hack any solutions you want, but not for credit like the normal rounds. The only reward is to named as top 5 hackers (though the top spot is almost always halyavin!
 » 2 years ago, # | ← Rev. 2 →   +2 I love vovuh's Codeforces Round!! I wish I would go to expert..
 » 2 years ago, # |   +13 I noticed that "(or 8)" was added next to the problem count in the copy-pasted part. On the last div3 round that part wasn't included. Does this mean that this round will have 8 problems?
•  » » 2 years ago, # ^ |   +34 Yes, I suppose :^) But one spoiler: two of them will be in two (easy-hard) versions.
 » 2 years ago, # |   -6 We need more div.3!!!
•  » » 2 years ago, # ^ |   +44 we also need div.4 !!!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -17 Sorry i have changed it due my wrong opinion.
•  » » » » 2 years ago, # ^ |   +23 This problem is too hard for Div.4, the sum overflows int.
•  » » » » » 2 years ago, # ^ | ← Rev. 4 →   -17 Y
•  » » » » 2 years ago, # ^ |   +10 do you mean, now we need less div 3?
•  » » » » » 2 years ago, # ^ |   +2 yes so that will be better for the beginners
•  » » » » » » 2 years ago, # ^ |   0 I don't know how having less contests is better for beginners. The more the better!
•  » » » » » » » 2 years ago, # ^ |   0 yaaa... more contests are not necessary. Because we can participate in virtual contest. But division 4 will be helpful for the participant whose have rating below the 1200. and it will also encourage the rating below the 1200 and beginners. Because it not possible for everyone to cross rating 1600.
•  » » » » » » » » 2 years ago, # ^ |   +63 if this comment gets more than 100 votes, I'll create a div4 contest in gym
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Let's upvote!
•  » » » » » » » » » 2 years ago, # ^ |   +2 Heh heh good try riela :P
•  » » » » » » » » » 2 years ago, # ^ |   0 Is it rated?
•  » » » 13 months ago, # ^ |   0 His dream come true.
 » 2 years ago, # |   +12 Is there going to be a problem with an Easy and a Hard edition ?
 » 2 years ago, # |   +1 I love cf
 » 2 years ago, # |   0 good luck guys GG HF!
 » 2 years ago, # |   0 Best of luck to all.
 » 2 years ago, # |   -7 I feel like I need a Div 4 too. :P
 » 2 years ago, # |   +4 That "(or 8)" smells like an easy-hard version
 » 2 years ago, # |   0 An uncertain-problem number contest :D.
 » 2 years ago, # |   0 I wish everyone high increase in ratings today. Happy Coding!
 » 2 years ago, # |   +1 Happy New year all...
 » 2 years ago, # |   0 today we have a ratings party :))
 » 2 years ago, # |   0 I hoped that there will be 7 or 8 problems,because a new problem can provide you a new skill.
 » 2 years ago, # |   0 Please make Div 3 rounds as frequent as Div 2. It is really good from the competition point of view. Otherwise Div 2 rounds include upto 2100 rated competitors on the ranklist which push coders like me to the bottom of the ranklist. Its really hard to even get to the top 1000.
 » 2 years ago, # |   -6 All the way to Expert. :D
•  » » 2 years ago, # ^ |   0 for me lol
 » 2 years ago, # |   0 Good Luck and Have Fun all!!
 » 2 years ago, # |   -31 Broken Div.3 again? Why not to use this problemset for Div.2, when its difficulty is even about Div. 1.5... Or division is adjusted only by problem A? Look at good examples of problemsets of Div.3 contests: Codeforces Round #479 (Div. 3), Codeforces Round #481 (Div. 3).
•  » » 2 years ago, # ^ |   +1 I know when you're this low rating you shouldn't really complain, and I am not. I am genuinely interested who should be able to solve these problems ? Is it aimed for people with rating around 1600? first ones were.Anyways, liked the round and thanks for doing this to help beginners.
•  » » » 2 years ago, # ^ |   +1 This image was taken with "show unofficial" disabled, so it seems like many under 1600 rating were able to solve the problems (with the exception of F2).
 » 2 years ago, # |   +30 After reading the problem C I hated the problem and quit solving :)
•  » » 2 years ago, # ^ |   0 Me too :v :v :v
•  » » 2 years ago, # ^ |   0 C was very interesting, there are several different ways to implement it (I think so), and you are to choose (find) one which is easiest to implement.
•  » » 2 years ago, # ^ |   +3 The only thing which came to my head(after reading C) was to jump out of the window
•  » » 2 years ago, # ^ |   -23 I think quality of rounds must be more important than quantity of them, seen many implementation and brute-force recently...
 » 2 years ago, # | ← Rev. 2 →   +67 "Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy."Sees reds failing to solve F2... O_O
•  » » 2 years ago, # ^ |   +13 Div3 Problem Setters these days — If (We have Div1F problem)__ Print "Let's announce a Div3 round."else__ Print "Let's Wait for a Div1F problem."
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +2 I don't think F2 is that hard. It is just a smart extension and careful implementation of F1 (provided I did this things correctly :p). Maybe a Div 2 F though.
•  » » » » 2 years ago, # ^ |   +6 I found approach for F2 similar to XDCOMP
•  » » » » 2 years ago, # ^ |   0 yeah, that's why reds failed to do that during contests
 » 2 years ago, # | ← Rev. 3 →   +1 I think E is similar to Your text to link here...I am sorry that it just have chinese description.You can see the solution of this from Your text to link here...And I think that it can swap C and E
 » 2 years ago, # |   +2 What's pretest 6 of problem C ?
•  » » 2 years ago, # ^ |   0 me too ! i got WA at pretest 6 :((
•  » » » 2 years ago, # ^ |   0 It may well be a matrix with odd n and quantities of several numbers not divisible by 4, but divisible by 2. For instance, consider: input: 3 1 1 1 1 1 1 4 4 7 output: YES 1 4 1 1 7 1 1 4 1 
•  » » 2 years ago, # ^ |   0 maybe try: 3 1 1 1 1 2 2 3 3 4answerYES1 2 1 3 4 3 1 2 1my code accepted after handling this test case
•  » » 2 years ago, # ^ |   0 try this5 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 8 8 9 9 7 7 6 6
•  » » 2 years ago, # ^ |   0 My code works well for all the above cases.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe a case when N is odd and not equal to 3. I rectified that case and got AC on C.
 » 2 years ago, # |   0 how to solve D1 and F1
•  » » 2 years ago, # ^ |   +4 For F1:You need to count total number of red vertices and blue vertices in all the tree, then you can use simple dp to calculate for every vertex i the number of red children and blue children, let this value is pair dp[i], now let's root the tree at node 1 and traverse using dfs, for each edge joining vertex "u" and vertex "v" you can remove it and check the number of red & blue vertices in each new tree in O(1) using (total number of red & blue vertices, number of red & blue vertices of the child), and count good edges
•  » » 2 years ago, # ^ |   0 D1: binary search to check if we can get m pages in range [1, n] daysoptimal strategy to finish m pages in x days is to use largest value in 1st days, 2nd largest in 2nd days, ..., x largest in 1st days again (cyclic)
•  » » 2 years ago, # ^ |   +1 D2 : Binary search on number of days. To find maximum number of pages he can write in d days, Greedily pick largest a[i]'s and distribute them over d-days. This will work because in optimal solution, difference between number of elements in any two days is less than or equal to 1.F1 : First store the red and blue vertices in subtree rooted at v for all v, using dfs.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 D1 or D2 : Let's apply binary search on the number of days required. For the current mid, let us greedily write pages restricting ourselves to at most "mid" number of days. We take the maximum value of a and write a[n] pages on day1, a[n-2] pages on day2 and so on. If at any point we exhaust the number of days, we continue by reading 1 less page from the current book. If at any point we are able to read m pages then mid is a candidate for the answer. submissionF1 : let's root our tree at vertex 1 for simplicity. For every vertex, let's calculate the number of blue and red vertices in its subtree. We can do this using dfs. After this we can check for every vertex by removing an edge to one of its children. The number of red and blue vertices left in each of the new trees is blue[v], red[v], red[1] — red[v] and blue[1] — blue[v]. Here we are at vertex u and v is one of its children. We can calculate answer easily then. submission
•  » » 2 years ago, # ^ |   +3 For D1: I dont know if my solution will pass, but i used dp.First, i noticed that if we will drink k cups in some day, then we need to drink the lower first, keeping the higher amount of caffeine to the end, so i sorted the array of inputs in the beginning.Then, the dp state is dp[i][rem] is the number of days we need to write rem pages, using cups with indices from i to n, the recurrence is simple as we try to drink k number of cups in each day such that k is in this range [0,n-i+1].solve( idx , rem ) = min( solve( idx+1 , rem ) , solve( idx + k , max( 0 , rem-k ) ) + 1 )This solution is O(n*n*m) which is not bad. That's why i didn't manage to solve D2 as this solution will not pass the time or the memory limit.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 for D1, 1. sort them in decreasing order. 2. apply binary search on ans. for F1, do a dfs to know ho many reds and blues for each subtree
 » 2 years ago, # |   0 very good problems for DIV3 , enjoyed very much . Hope all my problems gets accepted after hacking phase.
 » 2 years ago, # |   0 Author should stop setting problem C.
 » 2 years ago, # |   0 what is testcase # 9 in D1?...T^T
 » 2 years ago, # |   +35 I think, I should change the first sentence in the announcement to "Miss Div. 1 rounds? :)"But surely, this was expected that F2 is a pretty hard problem ¯_(ツ)_/¯
 » 2 years ago, # |   0 Why I got TL in F2 https://codeforces.com/contest/1118/submission/50197337
•  » » 2 years ago, # ^ |   0 cin/cout?
•  » » » 2 years ago, # ^ |   0 Actually the same
 » 2 years ago, # |   -30 The problem setter of C should be banned for some time for creating such bad problem
 » 2 years ago, # |   +4 I hate filling numbers in matrix...it's so time-costing and brain-f***ing to consider about symmetry and indices...my poor little brain...
 » 2 years ago, # |   0 Is it possible to optimize the dp solution for D1 to solve D2?
 » 2 years ago, # |   0 WTF Why B test 1 1 Answer 1 ?!?!??!?!?!??!
•  » » 2 years ago, # ^ |   0 Because giving away 1 candy would mean even and odd sum are equal to 0 because no element remains. So the answer should be 1.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 The amount of candies you eat in odd days is the same as the amount you eat in even days, which is 0 because you don't eat in any.
•  » » 2 years ago, # ^ |   0 0 = 0
 » 2 years ago, # |   0 Bonus:Solve E with additional constraint: first and last pairs are also considered adjacent for the 4th constraint (formally b1 ≠ bn and g1 ≠ gn)Fun fact: seems like this problem can be solved with this limitation in all the cases when the original problem can be solved. Who can prove it or find a counter-test (or bug) in my solution 50193010, that solves problem with this additional constraint?
•  » » 2 years ago, # ^ |   +10 i solved the problem with a simple pattern that also satisfy this constraintfirst use all pairs i(from 1 to k) and i + 1 mod kthen all pairs i and i + 2 mod kafter that pairs i and i + 3 mod kand so on,you can easily see that this patern satisfies all the constraints
•  » » 2 years ago, # ^ |   0 I don't see how your solution solves this problem. It fails on the first testcase itself, I think (b1=b4).
•  » » » 2 years ago, # ^ |   0 For the test case 4 3 my solution prints YES 1 2 2 1 1 3 3 1 I see no problem there.
 » 2 years ago, # |   0 Can D2 be solved without binary search, maybe using priority queues?
 » 2 years ago, # |   +6 Really enjoyed the problemset. Best Div.3 round so far.
 » 2 years ago, # |   +16 How to solve F2?
 » 2 years ago, # |   0 The contest would have been great if E and C were swapped.
•  » » 2 years ago, # ^ |   0 What purpose swapping them will serve. Afaik both of them carries equal points??
•  » » » 2 years ago, # ^ |   0 Yes all carry equal points. Your point seems good, these things actually remind us to pick easy questions first (until you reach that level when C's implementation is a 8-10 min. cakewalk for you)
•  » » 2 years ago, # ^ |   -10 Problem E is rated 2000. If E and C were swapped,it would be rated no more than 1600.
 » 2 years ago, # |   +3 Can someone explain D2. I can't understand why we used a binary search in this.
•  » » 2 years ago, # ^ |   0 Forget about the binary search for now, the idea is that for every number of days we know the optimal cups to drink, and their optimal order too, so we can get for every number of days the maximum number of pages we can write (we will talk about this optimal order later).So if we know this kind of information, we can simply check all numbers of days between 1 to n, and select the least one that allows us to write at least m pages, and that's will be our answer.Here's where binary search helps, as if we can write x pages in k days, then we can write x or more using more than k days.The optimal cups to drink for a given number of days k is:The largest cup in the first day, then the second largest one in the second day, and so on until we take k cups in the k-th day. Of course we can take more than one cup in a day, then we extend for the first day by drinking the k+1-th cup (don't forget to subtract the number of cups that are already drank as in the first day we actually will drink the k-1-th cup first then drink the largest cup, so we need to subtract it, same goes for all days), and for the second day we also extend it with the k+2-th cup, and so on.submission
 » 2 years ago, # |   +3 These two participants have same source code in problem A, B, C, D1, D2, F1
•  » » 2 years ago, # ^ |   +1 Probably Fantasyice is an alt account of tim25871014. Don't worry though, they will be skipped =)
 » 2 years ago, # |   0 Is there a way for which test case my code failed for B ques. It was hacked. I implemented this logic — store prefix sum of elements in odd and even indices in an array, and store the total sun. Then loop through given array once again , and check if sum to left of it the odd(/even) and right tO it the even(odd) prefix sun if equal to (totalSum-arr[I])/2. My submission is this: https://codeforces.com/contest/1118/submission/50179395[prob. B](https://codeforces.com/contest/1118/submission/50179395)
•  » » 2 years ago, # ^ |   0 Hack Test: 1 6575
•  » » » 2 years ago, # ^ |   0 yeah found (in submission history). Thanks.My code is giving output as 0 for n=1. It should have been 1 instead.
 » 2 years ago, # | ← Rev. 2 →   +4 When does my brand-new rating reflects? I have to show off my [ LEGENDARY SHINING BLUE ] to my friends
 » 2 years ago, # |   +6 "I forgot to fix participant types (official <-> unofficial) if you registered before rating changes of the yesterday contest. It will be fixed after the contest. Thus, you will be a rated (official) participant if and only if your current rating is strictly less than 1600. Mike." **** Some people above 1600 had their ratings increased
•  » » 2 years ago, # ^ |   +11 Oh, sorry. I'll fix it soon. So don't be surprised with temporary disappeared ratings. I'll fix the issue and return ratings back.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Also, "Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must: take part in at least two rated rounds (and solve at least one problem in each of them), do not have a point of 1900 or higher in the rating."Check https://codeforces.com/contest/1118/ratings, in top 10 you can see 7 are giving the contest first time
 » 2 years ago, # |   -27 I received a message from codeforces system today regarding the similarity of my code with 2 other users. The reason for this may be that I was using ideone in public mode by mistake. Here are the links of my solution: https://ideone.com/s2sHpB https://ideone.com/Yax8pe https://ideone.com/9qbTAoThe only proof I can give you that I have not copied is that I coded the solution for problem for D1 and used the very same solution for D2 and got runtime error. The reason for that was the difference in array size I was using. In problem D1 I defined my array size=100 #define N 100 in my code. I submitted the very same code for problem D2 and got runtime error on a test case. I figured it out very soon due to large size constraints which the problem statement had and changed my array size by, #define N 200005Had it been a copied code from somewhere I must have got accepted answer in first go or it would have taken me a significant amount of time to realize the error in the code.The next proof I have is that you can see my coding style which is consistent across problems. I declare global variables with long long data type, use macros for defining array_size, #define N 200005Request you to please give back my rating. It took me a lot of hard work and motivation to get a rank among top 1000 after such a long time.
•  » » 2 years ago, # ^ |   0 MikeMirzayanov Can you please look into this. Thanks in advance
 » 2 years ago, # |   0 Can anyone tell why my solution for D2 fails for test 49?In my machine its output is 1 as expected?The problem is solved when is decrease the upper bound for binary search to n + 1.¯_(ツ)_/¯
•  » » 2 years ago, # ^ |   +9 Because in the test 49 n=1 , but in the fuction check ,for(ll i = 0; i < mid; i++) pgs += arr[i];the i is too large , and then the arr[i] is unexpected
 » 2 years ago, # |   0 Does anyone know where we can find the editorial for this contest?
 » 2 years ago, # |   +1 Why the updated rating has gone? Any particular reason?
•  » » 2 years ago, # ^ |   +1 See this comment and reply.
 » 2 years ago, # | ← Rev. 2 →   0 I think this was the much tricky contest then last div3 contest.
 » 2 years ago, # |   0 So, what is the method to think about the Problem A ? Couldn't get any idea.
 » 2 years ago, # |   +10 vovuh, Editorials please.
 » 2 years ago, # |   0 the user ereased rating who has been skipped
•  » » 2 years ago, # ^ |   0 the all my solution is skipped.....and i have rated ,down 128.
 » 2 years ago, # |   0 i had a problem on submitting , after i submitted A i couldn't submit B after the contest i could submit B and now i can't submit C ? Has anyone faced this problem?
 » 2 years ago, # |   +13 It looks like codeforces have a new way to tackle plagiarism. The one whose solutions are skipped have been given a score of 0, and their rating changes have been calculated by keeping that score in mind !!!!
 » 2 years ago, # |   +4 How to solve F2? I don't have any idea about it. Waiting for Tutorial.
 » 2 years ago, # |   +5 This submission 50181596 got AC on D2 and WA on D1.
 » 2 years ago, # |   +2 can anyone plz provide me the link to editorial
•  » » 2 years ago, # ^ |   +1 Here it is. You are welcome :)
 » 2 years ago, # | ← Rev. 2 →   0 So basically, no matter what, div1 coders will solve and win div 3 contests too. Great!