### Vovuh's blog

By Vovuh, history, 3 weeks ago, translation, ,

Suddenly, this round will consist of 7 different problems also!

UPD2: The round will consist of 7 problems and one of them will be in easy and hard editions!

<almost-copy-pasted-part>

Hello! Codeforces Round #555 (Div. 3) will start at Apr/26/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 PikMike Piklyaev, Maksim Ne0n25 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.

</almost-copy-pasted-part>

UPD0: I also would like to thank my friend Adilbek adedalic Dalabaev for helping me with understanding problems difficulty and other help with round preparation!

UPD1: Big thanks to dreamoon_love_AA, Ashishgup, jeel_vaishnav and lizi_lzy for testing the round!

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 FloodBenz 8 282
2 maguihong123 7 347
3 dreagonm 7 373
4 DeathYmz 7 571
5 BaiBatyr 6 189

Congratulations to the best hackers:

Rank Competitor Hack Count
1 WileE.Coyote 448:-33
2 Disappointment 127:-20
3 wzw19991105 39
4 ismagilov.code 50:-23
5 Kucha 20:-3
919 successful hacks and 365 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A ImAlsoChildish 0:01
B BaiBatyr 0:06
C1 darshit_99 0:10
C2 Injetzk 0:16
D iamnotacoder 0:21
E BaiBatyr 0:12
F Injetzk 0:29
G Injetzk 1:15

•
• +176
•

 » 3 weeks ago, # | ← Rev. 2 →   +46 Vovuh get ready to surpass Petr in the contribution table
•  » » 3 weeks ago, # ^ |   -26 Yes only 1
 » 3 weeks ago, # |   -25 Recovery Time of Rating. :)
 » 3 weeks ago, # | ← Rev. 3 →   +25 Nice round ID! I love it :)
 » 3 weeks ago, # |   -14 Suddenly, this round will consist of 7 different problems also!
 » 3 weeks ago, # |   -15 Can explain how it is possible: "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."?I hack myself? or i submit from other accaunt and hack this submission? in this case, how to identify this?
•  » » 3 weeks ago, # ^ |   -9 Probably both. It is really easy to detect — cheaters will often have something like if(n==123445): print([obviously wrong number])
 » 3 weeks ago, # |   -18 Only if this was my last div 3 :(
 » 3 weeks ago, # |   0 why does Vovuh mostly sets problem for Div3 and Educational Rounds only ??? P.S: I like his problems ;)
•  » » 3 weeks ago, # ^ |   0 because Vovuh loves us!
•  » » 3 weeks ago, # ^ |   -8 Not only Educational Rounds ;) Codeforces Round #374 (Div. 2) By the way, thanks to Vovuh
 » 3 weeks ago, # | ← Rev. 2 →   -17 When round start me "body oh my losing all my rating"
 » 3 weeks ago, # |   -8 In reference to the UPD1, what does it mean to "test a round" ?
•  » » 3 weeks ago, # ^ |   0 that means the testers will solve the problems of the round, and give feedback to authors if they found a bug or statement is unclear or something
 » 3 weeks ago, # |   -7 What does it mean that "the penalty for the wrong submission in this round [...] is 10 minutes"? Does this mean that if I submit a program that doesn't pass test #47 then I will only have 1h 50min for the whole competition?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 It means that the 'Penalty' displayed in 'Standing' page is increased by 10.
•  » » » 3 weeks ago, # ^ |   -8 Thank you!
 » 3 weeks ago, # |   0 How to solve D ?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +7 Hint : With $x$ as your first number, you can construct array for all $n$ in range $(kx + k*(k - 1)/2, x(2^k - 1))$
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Can first number be any integer? I took it as 1 and thought I can solve the problem with range updates easily by tracking max value of every index and what to add to reach N, but failed at TC 5. For first sample it is going like: [1,2,3,4,5,6] -> [1,2,4,5,6,7] -> [1,2,4,5,6,8]. Edit: Just saw TC 5, we can use any number as first number :)
•  » » » » 3 weeks ago, # ^ |   0 Interesting. It's actually not stated that $a_1$ has to be $1$. If this is the case, the solution could be much simpler.
•  » » » » » 3 weeks ago, # ^ |   +1 Looks like I made problem harder during contest. Spent 1 hour to fix my solution and noticed it's extra easy when you can start with any integer. (This one wrong attempt, and this one after I understood the problem)
•  » » » » » » 3 weeks ago, # ^ |   0 can you please explain your approach
•  » » » » » » » 3 weeks ago, # ^ |   0 Take the example for N = 60 and K = 6, initial array is [1,2,3,4,5,6], and sum is 21. You need 39 to reach 60. int(39/6) = 6. Add this to each element [7,8,9,10,11,12]. 39 % 6 is 3 remaining value. Check if you can add that to last item (max value is 2*a[previous id]), in this example it can be 22, so it safe to make last item 15. If array was something like [1,2,3,4], and remaining was 3, you need to do same thing for last 2 item [1,2,4,6]. A quick explanation, hope it's clear :)
 » 3 weeks ago, # |   0 What is 5th test case of E !? Can't find any mistake in my solution >_>
•  » » 3 weeks ago, # ^ |   +1 In your code :- " auto bs =pam.lower_bound(n-a[i]); " It may point to pam.end();
•  » » » 3 weeks ago, # ^ |   0 Thanks for the catch. I got it AC now T_T
 » 3 weeks ago, # |   +36 Very Very Very nice round! interesting problems!!!!!!!!!! easy to understand! hard to solve!( for me ..)
 » 3 weeks ago, # |   0 Can someone elaborate the part, where 12 hour phase of open hacks is written?
 » 3 weeks ago, # |   -32 plz don't ask about the solution since the hack is still avaliable.
•  » » 3 weeks ago, # ^ |   +1 Hacks in phase of hacks do not change anything
•  » » » 3 weeks ago, # ^ |   0 Thanks! I am new on this platform, so didn't know about that!1
 » 3 weeks ago, # |   +3 Can anyone please confirm if my following submission has a time complexity of O(n*n) or not for E? According to me , it does. Link. Moreover, I would appreciate if someone can hack it as I am not really aware of the working of the test generator to generate such tests. Thanks !!
•  » » 3 weeks ago, # ^ |   +1 Yes, it is o(n*n).try a=200000*0 b=200000*199999 , will get a tle
•  » » » 3 weeks ago, # ^ |   0 Hi. Thanks for replying. It got hacked but just to inform you, I think my solution will pass the test case provided by you as all the elements of input array a are same. So basically, it will only search once and in all the next iterations it'll just execute the O(1) operation. The test case over which it'll fail will be something of the type20000 0 1 2 3 4 ............ 19997 19998 19999 0 0 0 0 0 0 ..........0 0 0In this case, it will calculate the ideal mod for every entry in array a by going through every available value in b before choosing the optimal one.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -6 ..
 » 3 weeks ago, # |   0 Hey ! For problem C1 (https://codeforces.com/contest/1157/problem/C1) , I want to know what should be the output for these test case:case 1 5 1 2 3 4 5case 2 5 5 4 3 2 1case 3 1 2Thanks in advance
•  » » 3 weeks ago, # ^ |   0 case 1 and 2 are invalid input for C1 since there won't be duplicates
•  » » » 3 weeks ago, # ^ |   0 sorry i wanted to write 1 2 3 4 5 and 5 4 3 2 1
•  » » » » 3 weeks ago, # ^ |   0 LLLLL and RRRRR
•  » » » » » 3 weeks ago, # ^ |   0 Okay Thank you.
•  » » 3 weeks ago, # ^ |   0 Those are invalid test cases for C1.
•  » » 3 weeks ago, # ^ |   0 Case 3 -> 2 LRthat's right? in case 1 and 2 are invalid for C1
•  » » 3 weeks ago, # ^ |   0 If you get stuck on C1, consider cases like 3 5 7 6 2 4 1.
•  » » » 3 weeks ago, # ^ |   0 Thanks a lot.This case has just revealed a logical error in my code.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 what is the expected answer for this test case 3 5 7 6 2 4 1? 5 1 3 4 5 7 ?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +11 Case 1: Answer is 5. ( LLLLR ) or ( LLLLL )Case 2: Answer is 5. ( RRRRL ) or ( RRRRR )Case 3: Answer is 1. ( L ) or ( R )The cases are valid for C1, because the first number is N, so there are no duplicates.
•  » » » 3 weeks ago, # ^ |   0 Okay..Thank you.
 » 3 weeks ago, # | ← Rev. 4 →   0 Any counter case where my solution fails for C2? apparently codeforces is giving WA on TC 15, but string is of length>1000 so I can't dry run and see where it went wrong.My submission
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 input 5 5 6 7 6 6 causes infinite loop, you don't handle well situation when A[left] = A[right]
 » 3 weeks ago, # |   0 I want to know why my solution for C1 in java got TLE while the same solution in C++ got Accepted. Java version: 53356781 C++ version: 53359020I'd also like to know why I got compile error when I used linked list of java to solve C1. It works fine on my computer. The version of my jdk is 1.8 by the way. 53350776
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Because in java String concatenation creates a new copy of the string so that the overall complexity is O(n^2). You should use StringBuffer and use append() method for the concatenation. It will work in O(K). K is the number of characters.
•  » » » 3 weeks ago, # ^ |   +3 thanks
 » 3 weeks ago, # |   +45 Greedy Festival XD
 » 3 weeks ago, # |   0 is multiset erase() faster than vector erase() ? My solution got accepted when I used multiset instead of vector in problem E.
•  » » 3 weeks ago, # ^ |   +6 yep, vector erase() in O(n) and multiset erase in O(logn)!
•  » » » 3 weeks ago, # ^ |   +1 Oh..thank you
•  » » 3 weeks ago, # ^ |   +1 erase in std::vector have the complexity linear to the size of the vector (it have to move the elements after the deleted element forward), while that in multiset is have the complexity log of the size of the vector.
•  » » 3 weeks ago, # ^ |   0 Yes, multiset is implemented as a self-balancing binary tree, for which deletion is O(log n).Vector deletion is O(n) in the worst case.
 » 3 weeks ago, # |   0 Can someone please help me figure out why my solution is giving TLE on test 16 although similar solutions have passed all tests.
•  » » 3 weeks ago, # ^ |   +10 check this link
 » 3 weeks ago, # |   +6 Sorry, "Div3 round"… There won’t be a next time.
 » 3 weeks ago, # |   0 For Problem A I used a set to add values which are not present earlier . After generating next number if it is not in set add it until you find repeating number in set . Return set.size()Is the approach decent ?Started using STL more often now a days .
•  » » 3 weeks ago, # ^ |   0 yes, I did the same but with using unordered map STL . Here is my solution.
 » 3 weeks ago, # | ← Rev. 4 →   0 I wrote 2SAT for G, but I got TLE. It works O(const * N^3). For my opinion it must pass in 2 seconds :/.UPD. Number of edges are N^2, so that all program works O(N^4) :(
 » 3 weeks ago, # |   0 Need Help in Problem C1: why im gettting TLE in Testcase 10 whereas other similar soln's are working?? 53371370
•  » » 3 weeks ago, # ^ |   0 Hint:44 1 2 3See what your code does
 » 3 weeks ago, # |   +4 Yet another interesting case of cheating by 4ul_sharma and utkarshv3 who are from the same institute: Check here. MikeMirzayanov and Vovuh please look into it.
 » 3 weeks ago, # |   +23 Problems in this round are interesting and pretty good, thanks to Vovuh for setting these problems.
 » 3 weeks ago, # |   0 How to solve F?
•  » » 3 weeks ago, # ^ |   0
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 Take it for an example:74 3 5 1 2 2 1Instead of putting people of different heights randomly with keeping the difference between two adjacent heights one (e.g. 2 1 1 2 3), you can try to find a maximum height and a minimum height and form a cycle with other heights in between them. To do it, you have to find the longest possible contiguous non-decreasing sequence of numbers with difference between adjacent numbers 0 or 1 in the sorted array of heights. Notice that we need at least 2 elements of same value except for the maxima and minima in our output sequence, else we cant form the desired cycle.For our example we go like this, if we take 1 as our minima and we can go upto 3 as our maxima. As we have only one 3 we can't accommodate 4 here. So we can form a sequence like this, 1 2 3 2 1. So we start from our minima, climb up to the maxima and again climb down to the minima. I hope you got the insight.
 » 3 weeks ago, # | ← Rev. 3 →   0 In Problem B , What's wrong in this ? https://codeforces.com/contest/1157/submission/53365568 Gives WA on TC 7
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Try this case:62345671 1 4 4 6 7 8 1 1Your code stops at the 3rd element (4), while it is more optimal to continue.
 » 3 weeks ago, # |   0 Guys, given a multiset m; does someone know the explanation behind lower_bound(m.begin(), m.end(), x) timing out in E(>2000ms): here, whereas m.lower_bound(x) gives AC with 233ms: here. I feel so frustrated and confused right now.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/blog/entry/20553 BTW someone just asked same question in this post
•  » » » 3 weeks ago, # ^ |   0 It was useful, thanks!
 » 3 weeks ago, # |   +85 I really like problem G. With 1 clever observation, you can solve the problem in $O(nm)$.There is a solution to the problem if and only if there is a solution with first row all zeros or a solution with last row all ones.Proof: $n = 1$ is trivial. For $n \geq 2$, for a valid solution, as the array is sorted, the 0-1 boundary must lie on one row, and all the other rows should either contains all zero (rows before boundary row) or all ones (rows after boundary row).Therefore, we can try check only 2 column configurations (1. flip all ones in first row, 2. flip all zeros in last row) to find the answer. The row configuration can be found by checking whether the row have a mix of zero and ones after flipping the columns.Thanks for the great round! :D
•  » » 3 weeks ago, # ^ |   0 Thanks for your great idea!:)
•  » » 3 weeks ago, # ^ |   0 Very nice! thank you
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I had a different idea resulting in $O(nm)$ time complexity. But mine was very laborous to code. Submission: 53355339Assume that the array is fixed. How do we check if it can be turned to only zeroes? Either toggle the first row or not Toggle every column with a one in the first row Toggle every row with a one in the first column Make an data structure that can maintain the state of this algorithm when we change bits in the original array, and make two instances of it, one with the first row flipped and one without. Then do the following: check if either datastructure can be made all zeroes If either could, output its current row- and column flips. Otherwise, toggle the last bit that is not yet toggled in both. This essentially changes the solution we want to produce from all zeroes to zeroes in all but some suffix. If there was no bit to toggle, output NO Otherwise, update the two structures, and go back to step 1. Why is this $O(nm)$?When you toggle a bit that is not on the first row or on the first column, the structures do not need to be updated, so the change can be done in $O(1)$. There are $(n-1)(m-1)$ such bits.When you toggle a bit that is on the first column but not on the first row, you have to toggle one row, which can be done in $O(m)$. There are $n$ such bits.When you toggle a bit that is on the first row but not on the first column, you have to toggle one column, which can be done in $O(n)$. There are $m$ such bits.When you toggle the bit both on the first row and column, you have to run the algorithm again in time $O(nm)$, but there is only one such bit.So in total, we do $O(1) \cdot (n-1)(m-1) + O(m) \cdot n + O(n) \cdot m + O(nm) \cdot 1 = O(nm)$ work.
 » 3 weeks ago, # |   0 How to solve D with binary search?
•  » » 3 weeks ago, # ^ |   +1 I will try to explain the idea of how i did.Suppose an integer x can be used as a1. Let the restritions: sum of all ai for i from 1 to k should be n; the condition ai n $, we have to decrease x; If$ x*(2^{k}-1) < n$, we have to increase x. After find a possible x to be a1, we can binary the others elements of array a at same way. Complexity: O(k*log(N)) •  » » » 3 weeks ago, # ^ | +3 I did the same but for finding k, I applied the formula: x= (n-sum(1 to k))/k.This will give you x in O(1) time. So I don't think it necassary to apply binary search.  » 3 weeks ago, # | +20 "And for 1600-1899 the problems will be too easy" Not quite sure about this statement :o  » 3 weeks ago, # | +1 I overslept and finally I didn't participate this contest!Oh no.  » 3 weeks ago, # | 0 Can anybody show me what I did wrong in my submission (problem C2).Here is my submission : https://codeforces.com/contest/1157/submission/53384089  » 3 weeks ago, # | -18 what is trashforces without getting WA on at least one problem for making a stupid mistake that the shitty pretest couldn't alarm you about..............  » 3 weeks ago, # | 0 If S is a multiset. And what is the difference between S.lower_bound() and lower_bound(S.begin(),S.end())? •  » » 3 weeks ago, # ^ | +1 According to documentation: Complexity of std::multiset::lower_bound is: Logarithmic in the size of the container. Complexity of std::lower_bound is: The number of comparisons performed is logarithmic in the distance between first and last (At most log_2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.std::multiset::iterator is a bidirectorial iterator, but it isn't random access, thus std::multiset::lower_bound will work faster ($O(log(N))$vs$O(N)\$). In general, if you have to choose between container's method and an algorithm from std, the first option is more preferable. (There are some exceptional cases, but they are not related to competitie programming)
•  » » » 3 weeks ago, # ^ |   +3 It helps a lot，thanks ：D
 » 3 weeks ago, # |   0 How to solve problem G? I tried couple things, but nothing worked.
 » 3 weeks ago, # |   0 Hi everyoneMy submission 53393992 for problem E is failing on the first test case itself. But, when I run it on my terminal, it is giving the same output as the expected one. (same code on ideone.)Can anyone tell me what's going on?Thanks
•  » » 3 weeks ago, # ^ |   0 you never initialized the vector cnts
•  » » » 3 weeks ago, # ^ |   0 I thought it is initialized by default to zeros. Isn't it so?
•  » » 3 weeks ago, # ^ |   0 if (it == s.end() && *it < n - a[i]) { Maybe you mean if (it == s.end() || *it < n - a[i]) { 
 » 3 weeks ago, # |   0 editorials???
 » 3 weeks ago, # |   0 Can someone tell me what's wrong with testcase 6 for my submission 53339053. The input is no correct.... The third line is mssing....
•  » » 3 weeks ago, # ^ |   0 you get n integers instead of 9 for the third line input in your solution.
•  » » » 3 weeks ago, # ^ |   0 Thanks a lot, that was the solution!
 » 3 weeks ago, # |   0 Can anyone tell me why my solution is giving wrong answer for Test case 10 on problem C1. Submission 53345673
•  » » 3 weeks ago, # ^ |   0 65 6 3 4 2 1
•  » » » 3 weeks ago, # ^ |   0 Thanks, such a stupid mistake I made :|
 » 3 weeks ago, # |   0 For Problem D,I the lower bound of num[i] is max(a[i-1]+1,(int)ceil((double)n/sumb(k+1-i))); what's meaning? why not a[i-1]+1?(I know it's worng,but why?) Thx!
 » 3 weeks ago, # |   0 wileE.Coyote Hackcount 448 Wow! good job!
 » 3 weeks ago, # |   0 what should be the answer for this test case for problem C1 test case 54 2 3 1 5according me it should be 32 3 1am I right ??
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 you misunderstood the problem. take leftmost or rightmost elements and make a strictly increasing sequence with those. 5 4 2 3 1 5 the answer is 2 LR take 4 (the leftmost elements) first and then 5 and make this sequence that is in increasing order{4,5}