### gridnevvvit's blog

By gridnevvvit, 6 years ago, translation, ,

Hello!

Soon (on January 30 at 19:30 MSK) you are lucky to participate in Codeforces Round #227 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

The main character of the tasks is the cat George.

UPD1: Scoring will be next: 500, 1000, 1500, 2000, 2500.

UPD2: Contest finished, congratulations to winners!

UPD: Editorial

UPD: Statistics

• +101

 » 6 years ago, # | ← Rev. 2 →   +37 It is Chinese Spring Festival tomorrow- a very large and important event, so Happy Spring Festival to everybody:) Tonight is called Chu Xi in Chinese, means that wait for the coming new year( in lunar calendar), and I hope this contest will make this night better. Good luck to everybody.
•  » » 6 years ago, # ^ |   -39 边看春晚边比赛Y(^_^)Y
•  » » 6 years ago, # ^ |   +5 Which means it will be a challenge because of the firecrackers π_π
•  » » » 6 years ago, # ^ |   +13 orzzzzzzzzzzzz literary giant！！！
•  » » 6 years ago, # ^ |   +4 Happy Chinese New Year, I have received a big red pocket. :)
 » 6 years ago, # | ← Rev. 2 →   +1 Sorry, a slip of pen. That is Spring Festival, not Spring Festive.
•  » » 6 years ago, # ^ |   +12 u don't have to make a new comment for a typo or a grammar mistake. u can click the Edit option on ur old comment and change whatever u want! :)
•  » » » 6 years ago, # ^ |   0 Yes, thanks for ur notice.
 » 6 years ago, # |   0 As Chinese people，in this coming New Year's Eve。。。Good luck to everybody
•  » » 6 years ago, # ^ |   +15 Thank you. I am Vietnamese and I would also like to take this opportunity to wish everyone success for new year.
 » 6 years ago, # |   0 Happy lunar new year!!! I'll see firework at home and practice this round :))
 » 6 years ago, # |   +3 Today I wish I go to DIV 1 :)
•  » » 6 years ago, # ^ |   +3 I see you made it... Congratulations :)
•  » » » 6 years ago, # ^ |   0 Thank you. Now I wish to stay in Div 1, for that I need to practice more!
 » 6 years ago, # |   +16 yeeeeeeeeeeees another <3 gridneeeeeev <3 contest
 » 6 years ago, # |   +11 Finally, the main character is a cat! I hope he is fat and orange like Garfield.
•  » » 6 years ago, # ^ |   +6 No. He is fat, but not orange like Garfield.
 » 6 years ago, # |   +11 We hope problems will be normal ;) ...
 » 6 years ago, # |   0 Registered participants are too many for this contest.(about 3500 till now)
 » 6 years ago, # |   +4 good luck everyone
 » 6 years ago, # |   0 Guys, Happy Chinese New Year!!!码年快乐哈。。。。。。
 » 6 years ago, # | ← Rev. 3 →   +7 some bugs with hacks . When i press F5 i can hack guys from another room.when i try to hack it gives Apache Errori think it should be unrated if it's not only my errorsometimes when i press @hack@ nothing happens
 » 6 years ago, # |   +16 I'm having trouble opening solutions in my room even though I locked both the relevant problems. And sometimes I get redirected to another room (that I'm not in). Has anyone else experienced this?
•  » » 6 years ago, # ^ |   -58 yes,contest must be unrated!
•  » » 6 years ago, # ^ |   0 Thank you for the report. We are investigating the issue. We will do our best to fix it before the next round.
•  » » 6 years ago, # ^ |   +3 Yes... I faced same problem too... :/
•  » » 6 years ago, # ^ |   0 What was "another" room? Was it the 1-st room? Or random? Or not the 1-st but fixed for you?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Room number is shown correct, but users are not. I have seen that room where this user (sayeer_24) was
 » 6 years ago, # |   +7 Very glitchy today! "Room" button does not work very well (puts into random room often) and viewing solutions does not always work even after locking problems.
 » 6 years ago, # |   +30 I don't want to offend anybody (talking about authors of contests), but this round is really interesting. Thanks a lot, gridnevvvit
 » 6 years ago, # |   -7 It's a shame that server problems spoiled an interesting contest. Server was down for much of the contest, room button often redirected into some other room, and hack button rarely worked even if the solutions would finally show up. Very frustrating contest to participate in, but nice problems nonetheless.
 » 6 years ago, # |   +2 Round duration increased for 10 minutes. can you announce us before 15 minutes say , before the end of the contest , I've really stop coding at last 2 minutes . Very good contest thanks :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 yes, me too.
 » 6 years ago, # | ← Rev. 3 →   -7 Most fun contest i ever participated on CF. Best regards to everybody who helped in creating this round. I think I got the idea at E (after spending 15 minutes to properly understand the statement) — You use anything you want to create a vector prot[i] which tells you whether or not i is protected then you use divide-et-impera solve(a,b) = get the answer for interval [a,b]. You will need quick queries for sum (0/1 if a number has already been eliminated) and minimum value. All these can be acomplished by a segment tree. Didn't have enough time to implement this though. Is this the right solution? Anyway thanks for the round, Gerald, gridnevvvit, Delinur and of course MikeMirzayanov. Keep up the good work!
 » 6 years ago, # |   0 Is it me or the "room" is buggy today? On another note: Thanks for the awesome problem set! :)
 » 6 years ago, # |   +16 what a fun bug!! :D
•  » » 6 years ago, # ^ |   +1 So the winner is vas.and.tor, who made 2 hacks:D
•  » » » 6 years ago, # ^ |   0 Even I had the same problem. But still managed to hack 1. :D And I had vas.and.tor in my 'buggy' room. But the users he hacked were not shown in that room. What a bug. And regarding ' extended duration' I did not get any notice until after the contest. :( I closed the browser 10 seconds before the end of the competition.
 » 6 years ago, # |   +3 one more great contest, with interesting problems and bugs :)
 » 6 years ago, # |   0 I managed to make CF show me a standings page full of -1 and -2 where everybody failed all his submissions (even the top 10). A refresh fixed this.
•  » » 6 years ago, # ^ |   0 same here in Friends standings
•  » » 6 years ago, # ^ |   0 This was happening throughout entire systests. It was a pleasant surprise to see myself in 20th position, but it was quickly revealed to be only a dream :(
 » 6 years ago, # |   0 As Chinese people，Good luck to everybody。
 » 6 years ago, # |   0 very nice problem set. great contest. thanks! :)
 » 6 years ago, # |   +4 This was a nice round. I especially enjoyed solving E. Keep up the good work !
 » 6 years ago, # | ← Rev. 2 →   0 Can someone please explain the main idea behind problem D? Thank you! I tried to fix my center, delete it from the graph and then see what the solution is (this is the problematic part — I was thinking about maxflow, but n is too large).
•  » » 6 years ago, # ^ |   +3 The same problem. I think we have to check all vertexes as center and choose the best. But how delete arcs in optimal way?
•  » » 6 years ago, # ^ |   +6 You should use biparate matching on the graph, where left side is outdegree of vertex, right side is indegree of vertex.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 But how to decision which arc delete? If we have 2 indifferent variants?
•  » » » » 6 years ago, # ^ |   +2 We will delete all arcs, except that arcs, which is in maximal biparate matching.
•  » » » » » 6 years ago, # ^ |   0 Thank you. I have understood.
•  » » » 6 years ago, # ^ |   0 I didn't understand, Can you please explain it more ?
•  » » 6 years ago, # ^ |   0 No, n is not too large at all. Maxflow algorithm's (good implemented for biparate matching) complexity is O(FLOW * (N + E)) , E is number of edges here. FLOW's limit is N so overall complexity O(N * E).
 » 6 years ago, # |   0 How to solve E?
•  » » 6 years ago, # ^ |   +8 First, a slow (but useful) solution:In one step, we can remove the minimum of an interval. That means the smallest number (overall) will be removed whenever it's inside the interval picked. If it's supposed to stay, it's clear that we can't ever include it in our interval, and we can just consider our algorithm running on the parts of the original array to the left and right of it.Otherwise, we have to pick it eventually. If we pick it in the k-th operation, we can get a larger answer just by picking swapping the k-th and k - 1-st operation (think why it works), which means we should pick it in the first operation. And why not with as large w as possible — picking the whole array. Further in the algorithm, we just operate on the same subarray without the deleted element, without doing any splitting (like above).The slow (O(N2)) solution would now be simulating this algorithm. We can do better, though: we can see that it's all right to remove numbers in increasing order (the order among 2 distinct parts of the array doesn't matter), and we know how much the optimal solution will cost: the number of elements in the subarray on which we're running the algorithm, which haven't been deleted yet.Splitting subarrays into even smaller parts and checking which one the current element belongs to can be implemented with map<>, counting deleted elements with a Fenwick tree. The implementation is just straightforward now. Complexity: .
 » 6 years ago, # | ← Rev. 5 →   +9 Failed submission:5850238 Time: 2000 ms (MS C++) Accepted submission:5850920 Time : 872 ms ( GNU C++ ) It shows that ios::sync_with_stdio(false) in GNU C++ does a Miracle!!!!
•  » » 6 years ago, # ^ |   +5 Yes. Input is very large to read input with cin
•  » » 6 years ago, # ^ |   +5 Having it in your template is a good idea...
 » 6 years ago, # |   0 rating change reverted after some time... anyone else experiencing it ?
•  » » 6 years ago, # ^ |   -7 Looks like I'm still blue even though I'm over 1700.
•  » » » 6 years ago, # ^ |   0 I'm also still green although I'm over 1500. I imagine this is just a small lag between rating change and color change and should be resolved soon though.
•  » » » » 6 years ago, # ^ |   -8 The problem is that I oscilate between the 2 colors.
•  » » 6 years ago, # ^ |   0 nice bug in your account.you are blue but your name is green.
 » 6 years ago, # |   0 Finally reached blue ^_^ !!
 » 6 years ago, # |   0 someone must stop multiple accounts for div.2 only contests. PS: http://codeforces.com/blog/entry/10543
 » 6 years ago, # |   -11
 » 6 years ago, # | ← Rev. 4 →   +3 Violet "Candidate Master" and blue "amirMD" (1741) ! :D
 » 6 years ago, # |   +15 RedStar_13 supposedly solved C in 3 minutes, has different code templates in his solutions and even different tab settings. And yet he is allowed to take first place.
•  » » 6 years ago, # ^ |   0 Also after solving D, submited E in 2 minutes which has just a bug : 5843619.He have to explain this situation i think...
 » 6 years ago, # |   0 Can't find what's wrong, with this code: 5847679.Can someone help me?
•  » » 6 years ago, # ^ |   0 try with 120200 correct o/p — 1
 » 6 years ago, # |   +7
 » 6 years ago, # |   +3 For the problem B: 10010111Can somebody tell me how to merge 100,10,1,1,1 into 10010111 ? I try but fail.So I think this data's answer is 4 ..
•  » » 6 years ago, # ^ |   0 Sorry, problem C..
•  » » » 6 years ago, # ^ |   0 I have tested some Accepted code,all their answers are 5.I got confused now.
•  » » » » 6 years ago, # ^ |   0 After test data '111',I believe the system test data is not strong enough.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 You can do it with this operations (I hope my notation is clear):100 + 10 -> 10010, 1, 1, 110010 + 1 -> 100101, 1, 1100101 + 1 -> 1001011, 11001011 + 1 -> 10010111
•  » » » 6 years ago, # ^ |   0 Sorry,I misunderstand the Description。。 thanks ：）
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 {100, 10, 1, 1, 1} → {1, 1, 1, 10010} → {1, 1, 100101} → {1, 1001011} → {10010111}
•  » » » 6 years ago, # ^ |   0 Oh.sorry,I mistake 'i!=j' to 'i