### Sereja's blog

By Sereja, 5 years ago, translation, ,

Hello everyone!

Codeforces Round #243 will take place on Sunday, April 27th at 19:30 MSK. This is my eleventh Codeforces round and I hope not the last.

I'd like to thank Gerald and KADR for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values in first division 500-1000-1500-2000-2000. In second division — standard.

Gl & hf ! :)

•
• +234
•

 » 5 years ago, # |   -18 Thanks for the recommendation. :)This information might be handy during the competition.
 » 5 years ago, # |   +24 nice to have the regular rounds back :)
 » 5 years ago, # |   +7 Another Sereja round to enjoy. Thanks and good luck to everyone :D
 » 5 years ago, # |   -12 ًWhat's meant by Gl & hf ?
•  » » 5 years ago, # ^ |   +7 Gl & Hf == "Good Luck and Have Fun!"
•  » » 5 years ago, # ^ |   -9 Good luck & have fun)
 » 5 years ago, # |   -34 hey sereja ! u r my best consest writer. I think u prepare too smart problems :)
 » 5 years ago, # |   -14 Time for some Sereja and [?] problems ... :-)
 » 5 years ago, # |   -10 Lets hope for math/ad-hoc problems!
 » 5 years ago, # |   -7 yes , another Sereja round :D
 » 5 years ago, # | ← Rev. 4 →   -13 I strongly recommend you to read ALL the problems. Not usually written by other authors... :)
 » 5 years ago, # |   0 Thank you Sereja! : D
 » 5 years ago, # |   +8 Thanks for your efforts for preparing problems:)
 » 5 years ago, # |   0 *standard — not standart ;)
•  » » 5 years ago, # ^ |   +11 OK :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 And as I remember this mistake has become a standart issue :D
 » 5 years ago, # | ← Rev. 3 →   +2 Problem D : I think that you wanted to say : two cells are connected if they are adjacent in sAme row or sAme column of the table NOT : two cells are connected if they are adjacent in sOme row or sOme column of the tableAm I right ? ;)
 » 5 years ago, # | ← Rev. 2 →   0 DELETED
 » 5 years ago, # |   +4 What is the approach to solve Div2 C / Div1 A?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Simple brute force in O(N^3) + Sorting in O(NlogN) should easily pass the time limit.
•  » » 5 years ago, # ^ |   +2 Bruteforce, more or less. Try all possible ranges [l, r]; for each of them, put the numbers from that range into a multiset and the numbers not from it into another multiset. As long as swapping the largest number out of the range and the smallest number in the range improves the result (and you still have swaps available), swap them. Time: .
•  » » » 5 years ago, # ^ |   0 So we have an O(N^2) for choosing the ends of the interval, but how can we do the rest in O(KlogN)?
•  » » » » 5 years ago, # ^ |   0 Since you are using a set, elements will be searched in O(log n) and you have to choose 'k' such elements.
•  » » » » » 5 years ago, # ^ |   0 But inserting N elements with take O(N*logN) in a multiset. I feel the time complexity for this solution will be O(N^3*K*logN)
•  » » » » » » 5 years ago, # ^ |   0 My solution along the same lines works in .
•  » » » » » » » 5 years ago, # ^ |   +1 I'm sorry for the offtopic, but how do you get such O?
•  » » » » » » » » 5 years ago, # ^ |   +15 Via \mathcal{O} in :
•  » » » » » » » » » 5 years ago, # ^ |   0 this looks really cool! :) and i think looks cooler than and :D
•  » » » » » » 5 years ago, # ^ |   0 My solution's complexity is O(N^2*logN + N*K*logN)
•  » » » » 5 years ago, # ^ |   0 As long as swapping the largest number out of the range and the smallest number in the range improves the result (and you still have swaps available), swap them. There are at most K allowed swaps and each can be done in (because multiset).
•  » » » 5 years ago, # ^ |   0 Any way to solve it without multiset?
•  » » » » 5 years ago, # ^ |   0 Sort the numbers that you'd put into multisets otherwise and do the swapping the same way.
•  » » » 5 years ago, # ^ |   0 Can you provide the link to a properly implemented solution? Thanks in advance!
•  » » » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 Bruteforce all l..r on array (for for), and try to calculate the best value on l..r by swapping worst values with best from 1..l-1 & r+1..n. I did it with sorting, but the best approach I saw is to create two piority queues "in, out" and take r-l+1 values from them (don't take more than "k" values from "out" queue)
 » 5 years ago, # | ← Rev. 3 →   +61 Div1 D was same as this ONTAK problemEDIT : Also it exist at stackoverflow
•  » » 5 years ago, # ^ |   +45 Yes, it seems that it is a very well-known problem.
•  » » 5 years ago, # ^ |   0 Is there any detailed analysis of the complexity?
•  » » 5 years ago, # ^ |   0 The one on StackOverflow does not requires sides parallel to axis.
•  » » » 5 years ago, # ^ |   0 Yes, but the algorithms described in the answers are very, very slow.
•  » » » 5 years ago, # ^ |   +5 At the bottom there is a link to a paper.
•  » » 5 years ago, # ^ |   +37 Btw, I like how the answer on StackOverflow which is clearly the most valuable has -1 votes :)
 » 5 years ago, # |   +8 what is the idea behind the problem D(div 1) ?
•  » » 5 years ago, # ^ |   +34 I had an solution. A square is uniquely defined by its 2 top (or 2 bottom etc.) points. Split the horizontal lines into large (at least points on the line) and small (otherwise); then, there are just squares whose 2 top points lie on a small line, same for those whose 2 bottom points lie on a small line and 2 top ones on a large one.There are at most large lines. For each point on one of these lines and each line below it, you can also check if there's a square for which these are 2 right points. There are also these questions.How to check the existence of many pairs of points (out of which all lie on 1 horizontal line)? Just make a vector saying if there's a point with some x-coordinate. You can do this for many lines with 1 vector, taking just O(1) time per query + O(N) time amortized for filling and cleaning the vector.
•  » » 5 years ago, # ^ |   +18 Or you could use the fact that unordered_set is extremely fast and write something very short like this: click ^_^
•  » » » 5 years ago, # ^ |   +1 Wow, that looks useful. I don't know more about unordered_set than it erasing a -factor in theoretical complexity (and decreasing the practical one) :D
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 I really liked next comparation: vx[x[i]].size() < vy[y[i]].size() in HellKitsune's solution.I believe hides behind it, does it? How to prove that? :)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 After reading the code again, I think it is O(n^1.5)
•  » » » » 5 years ago, # ^ |   0 To be honest, I have no idea how to prove it formally. :(But informally, we will most likely achieve the highest number of iterations if for each point we minimize the difference between the number of points lying on the same horizontal and the same vertical line with it. It then only seems logical to assume that the worst case scenario for this algo would be when the points form a square, which would give us complexity.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   -8 True.I got AC on your approach using unordered_set and got TL on using set.Does makes such a big difference? Or is it constant behind C++ set implemenation?However, author's approach has no unordered_set tricks. But I could not implement it.
•  » » » » » » 5 years ago, # ^ |   +5 Consider log N a factor of 20. It's a pretty good approximation.
 » 5 years ago, # |   +4 Paper for problem D and harder versions of it!!!Link
•  » » 5 years ago, # ^ |   0 Uhm, this paper is about checking if set of points contains desired figure, not about counting them.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +8 But the algorithm can be easily used to count number of figures.It's proved in the article that there's at most O(N1.5) squares in the plane and existence of the square is checked using brute force over all possible candidates.I used this article to solve this problem. Is there faster approach than O(N1.5log(N))? log(N) is for checking if the point is in set and I think we can avoid that logarithm but what about better estimation than O(N1.5)?
 » 5 years ago, # | ← Rev. 2 →   +8 How to solve B ? It was awsome. :)) But I did not get the idea.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Deleted.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +14 n, m <= k : bruteforce by any possible first row otherwise : freese one row and calculate min changes in case of this row is unchanged 6492596
•  » » 5 years ago, # ^ | ← Rev. 2 →   +26 If n>10 or m>10 there must be at least 1 line that does not change. Then iterate all such possible line. We know one line, so we know vertical partition of initial table and can easily find minimum number of changes.If n<=10 and m<=10 iterate all possible first lines(2^m) and we know one line again.
•  » » » 5 years ago, # ^ |   +11 I observed that if you have a line fixed you can compute the answer, but I didn't noticed that. Now it seems kind of obvious. Thanks. :)
•  » » » 5 years ago, # ^ |   0 "If n>10 or m>10 there must be at least 1 line that does not change"-why?
•  » » » » 5 years ago, # ^ |   0 because "k <= 10" !
•  » » » » 5 years ago, # ^ |   0 because k <= 10 and you can't change more than k rows/columns.
 » 5 years ago, # |   +5 very strong pretests low chance for hacks
 » 5 years ago, # |   0 when will the ratings be updated?
•  » » 5 years ago, # ^ |   0 soon
 » 5 years ago, # |   0 Div.1 B What about this case, what's the answer please? 3 4 10 1 0 1 1 0 0 1 1 1 1 1 1
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 2, it can be turned to 1011 1011 1011
•  » » » 5 years ago, # ^ |   0 what positions should be inversed ?
•  » » » 5 years ago, # ^ |   +5 Thx...
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Think about your number of rows, and try to figure out the answer from that! (Can odd rows be mirrored)
•  » » » 5 years ago, # ^ |   0 actually they are talking about div1 B not div2 B.
 » 5 years ago, # |   +3 I could not understand the problem C correctly until someone explained to me after the contest. a quote from the problem statement "the element of sequence a with the maximum index among the chosen ones must be equal to the element of sequence b with the maximum index among the chosen ones; remove the chosen elements from the sequences."If the maximum indices of two chosen values are equal, it means you take same number of elements from the sequence, isn't it? Shouldn't the wording be "the index of sequence a with the maximum value" instead of "the element of sequence a with the maximum index"?
•  » » 5 years ago, # ^ |   0 This means that the last deleted elements must be same in both sequences.
•  » » » 5 years ago, # ^ |   0 Ah... I think I was just wrong. Thank you.
•  » » 5 years ago, # ^ |   -8 What's wrong with removing the same number of elements from each sequence? It's a perfectly valid move.But since taking any more elements than the equal ones seems to be a non-optimal strategy, "maximum value" should mean the same as "maximum index".
•  » » » 5 years ago, # ^ |   0 That's a clear explanation. I now understand the problem statement :) Thanks!
•  » » 5 years ago, # ^ |   +61 Though I got it correctly during the contest I still don't see why it wasn't smth like: "both prefixes should end with same number", which is shorter and easier to understand. Sometimes formal language is too formal.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +60 Yes, I feel that sometimes problems on CodeForces are about deciphering the problem statement rather than understanding it and then having insights. Some authors also seem to be really into mathematical symbolic notation :)
 » 5 years ago, # |   +10 why is rating update delayed?
•  » » 5 years ago, # ^ |   -60 Because it's going to be unrated!!!! hahahaha =)))))))
•  » » » 5 years ago, # ^ |   -13 That wasn't very funny, and that you needed to add your laughter at the end didn't help. I guess you're going to be downvoted.
•  » » » » 5 years ago, # ^ |   0 Hey, glad you made it back to red.
 » 5 years ago, # | ← Rev. 2 →   +1 What exactly is the special point of test 22 of Problem B(Div 2)? Many got WA.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 You should check if n % 2 == 0 before each iteration.Test: 6 1 1 0 1 1 0 1 You should output 3, but ouput 3 / 2 = 1.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 my code works fine with that case, still don't know why WA on 22 :(my submission](http://codeforces.com/contest/426/submission/6491099)
•  » » » » 5 years ago, # ^ |   0 6 1 1 1 1 1 1 1 gives wa on your code
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 answer should be 1 right?
•  » » » » » » 5 years ago, # ^ |   0 No, it should be 3. You cannot get 3 rows by mirroring one.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 thank you very much, to correct something I forgot that part xD
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think it's all 0's, shows a portion of 100 * 100 grid in the submissions page.
 » 5 years ago, # |   +10 Good round, thanks.
 » 5 years ago, # | ← Rev. 2 →   0 in problem A why i need to make sort i mean what part of the problem told me that " i didnt make sort so the program fails at testcase 8 :/ "?? thanks in advance :)
 » 5 years ago, # |   +14 The problems in div1 are pretty good except problem D. Problem D in div1 is so classic that so many people have solved it before (at least I knew several well-known OJs have problems almost the same). And its time limit is so tight I thought. I first used std::set but got TLE at pretest 13 several times. But I changed my code to use lower_bound in a sorted std::vector, I got accepted. That's why I thought its time limit is too tight somehow. Does anyone agree with me?
•  » » 5 years ago, # ^ |   0 No, I don't agree with you. Using operations like lower_bound take log N complexity, so you got complexity O(n^3/2 log n) instead of O(n^3/2) so you shouldn't be surprised that you got TLE. Even more — tests weren't in fact maxtests. They could have been more time-demanding.
•  » » 5 years ago, # ^ |   +8 Besides, set<> has a large constant factor. Sorting is generally much faster than set<> operations, and this could serve as a lesson for you to prefer sorting in the future.
•  » » 5 years ago, # ^ |   0 I got my solution passed after changing from finding a point in O(log (n^2)) (i.e. 2 log n) to O(log n). Simply store a set for each possible x instead for all. However, I think the time limit is fine after all.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +3 Look at my solution 6490475Although I aware of N^1.5 solution, my solution, which base on two pointer method is O(N^2)If the test case is strong enough to contains test which is two far away parallel line ( <0,0>, <100000,0>, <0,1>, <100000,1>, ... ) my program would be easily TLEI realize it after the contest already end. So I'm lucky one to pass the problem D
 » 5 years ago, # | ← Rev. 2 →   0 At least to me, C/Div.2 was much easier to implement than B/Div.2. Any one thinks the same?
 » 5 years ago, # |   +11
 » 5 years ago, # |   0 My solution for D problem got AC luckily. I have thought that the complexity of my solution is O(n^1.5) but it is really O(n^2). For each point, my solution calculate right points, below points, and right-below points, then use three pointer to count how many square. The complexity become O(n^2) in this kind of input: 20 0 1 0 2 0 3 0 4 0 5 0 6 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 Execute the solution with larger input (with the same type of above input), I have the following statistic: - In my computer, Intel Pentium 2.2GHz, n=100000, the time is 22.312s - In my computer, compile with -O2, n=100000, the time is 3.444s I can not try to run the solution in Codeforces because my input is larger than 256KB (my input is 1020KB)