Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### dalex's blog

By dalex, 5 years ago, translation, ,

Hi all!

Authors of today's round are craus and dalex. We just couldn't miss the round with such a beautiful number, so at 19.30 MSK you will solve problems which were invented by Pavel and prepared by me.

We thank Gerald and Delinur for their help in contest preparation and MikeMirzayanov for creating Codeforces.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins.

We wish you accepted solutions and successful hacks!

UPD. Contest is over, congratulations to the winners!

Div. 1:
1. Petr
2. tourist
3. Egor

UPD. 2 Problem analysis is published.

•
• +269
•

 » 5 years ago, # |   +35 Does that mean there will be some problems have tricks, and there will be a chance to hack for getting higher scores?:D
•  » » 5 years ago, # ^ |   0 That was a great contest! Good problems! New ideas! Thank You!
 » 5 years ago, # |   +62 "Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins."lol, I guess the setters are fed up with comments like "Only 10min/5min/30sec left before contest and there is still no updates!!"
 » 5 years ago, # | ← Rev. 4 →   -38 Best wishes to every one!!
 » 5 years ago, # |   +9 Don' t have time to take part, what a pity. Anyway, wish everyone a high rating [By the way, this is the 222ed round, so I guess there will be some prblems about twos. So try to search for some information ~ . Well,just kidding ]:):)
 » 5 years ago, # |   +78 Keep in mind that this will be a historic round, because today for the first time I'll become a redcoder :P.
•  » » 5 years ago, # ^ |   +32 Aha, Good luck to you. I'll pay attention to your performance on this round. :D
•  » » 5 years ago, # ^ |   +24 may the (code)force be with you ;)
•  » » » 5 years ago, # ^ |   -51 I hate starwars.
•  » » » » 5 years ago, # ^ |   -9 You Sith !!
•  » » » » » 5 years ago, # ^ |   -8 Now I hate it more!
•  » » 5 years ago, # ^ |   0 Good Luck Swistakk:) May God with you today :)
•  » » 5 years ago, # ^ |   +12 Congratulations =)
•  » » 5 years ago, # ^ |   +112 Did it :D!
•  » » » 5 years ago, # ^ |   +23 Wow... Congrats! You barely made it, but I would like to have your confidence. Because I have lost it competing here :D
•  » » » 5 years ago, # ^ |   +8 congratulation :D Swistakk
•  » » » 5 years ago, # ^ |   +24 By 1 point :D Happy New Year :)
•  » » 5 years ago, # ^ |   +8 Congratulations!!!
•  » » 5 years ago, # ^ |   +27 Astonished seeing your confidence !!!! Great !!! :)
•  » » 5 years ago, # ^ |   +9 and you really made it!!! congratulations man :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 challenge succeed!!!.... what a confidence!!! congratulation....
 » 5 years ago, # |   +12 You can't wish us accepted solutions and successful hacks! That's a paradox. :DOr maybe after we get hacked a few times we'll finally reach the good solution / program?
•  » » 5 years ago, # ^ |   0 thats always the case with wishing 'high ratings' also as it is designed in such a way that if one gains someone else loses.
 » 5 years ago, # |   -66 Please vote "I like it".
•  » » 5 years ago, # ^ |   0 Is this the new trend or something? Seems like there is always somebody asking for upvote or downvote in every contest. I am kind of curious now to see how long this will continue :p
•  » » » 5 years ago, # ^ |   -12 I did not read related comments before, therefore I do not know that others ask for up-vote or down-vote. Just do it for fun, nothing more.
 » 5 years ago, # |   +6 Yep. Good luck to me and everyone else ~
 » 5 years ago, # |   +6 We wish you accepted solutions and successful hacks!(Y)
 » 5 years ago, # |   -15 What's the idea behind putting STRONG pretests?! Hacking is almost impossible!
•  » » 5 years ago, # ^ |   +11 Well, when hacking is "I know one tricky case, and I'll check if all solutions works on it" It's not very interesting too. Pretests aren't strong today BTW at least in Div1.C. My solution is absolutely wrong but passed them.
•  » » » 5 years ago, # ^ |   -16 Well, it's not even like this. Even the extreme cases (big input) were present in the pretests! Some people in div2 got TLE because their algorithms were not to run in time under the problem constraints, I'm amazed that such cases were included in the pretests!
•  » » 5 years ago, # ^ |   0 Possible, in Div2 A, there is no test when a = b ;)
•  » » » 5 years ago, # ^ |   0 I hacked three submissions with a==b test. ^_^ .. Happy today.
•  » » 5 years ago, # ^ |   0 Maybe they wanted to make a more classic contest, but Codeforces is neither a classic type of contest nor an ACM type. So there is no point in very strong pretests. Problem C on Div2 could have had some cases not included in the pretests (like the case with all the matrix full, when the DFS should not be called at all).
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I didn't use dfs at all, my solution is kLogn + kLogm using segment tree, some people used sqrt segmentation.PS: failed sys test
 » 5 years ago, # |   0 phew the contest is over . . . thanks for the contest.. i can have fun with the problem .. :D
 » 5 years ago, # | ← Rev. 2 →   +13 It's fun to see a problem about Dota 2 :P
 » 5 years ago, # | ← Rev. 2 →   0 the second last codeforces round of this year and nice one..
•  » » 5 years ago, # ^ |   +12 Just got a popup message there is another round on 30th, which will be rated for both Divisions
 » 5 years ago, # |   0 Incredibly simple A (and impossible to hack as I've seen), simple DFS on C, hard to understand the statement on B (the explained sample though saved the day), not so hard solution (here the intuition on why it works was more important than the proof itself). Nice round for the 2nd last contest of this year. "Authors of today's round are craus and dalex" — keep up the good work.
•  » » 5 years ago, # ^ |   0 Three succesful hacks on A. :P
•  » » » 5 years ago, # ^ |   +2 Well, at least in my room, most solutions to A had the case a==b included in them (I tried at least 10 submissions).
•  » » 5 years ago, # ^ |   0 I was able to hack on A LOL :D
 » 5 years ago, # |   0 In Div2 B, I forgot to make size of my array which contains merged a and b to 2 * 105. Instead the size was 105. I wonder, will it fail or not? :|
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Probably it will fail, but, as all of us know, everything is possible. Tell us if it failed or not.
•  » » » 5 years ago, # ^ |   0 I tested my code on "custom test". I thought it would get AC or RTE but not WA. As in "custom test" there were no RTE, I gave up resubmitting. And now I got WA 37. :)
•  » » 5 years ago, # ^ |   0 FAILED T_T
 » 5 years ago, # |   0 I am interested is problem D Solvable by (Binay Search of Answer)+(Data structure)?
•  » » 5 years ago, # ^ |   +1 Let's find the amount of days we need to fix bugs with binary search. Now, let's check that k days is enough to do it. First of all sort the bugs. Then iterate through them and for each of them find a student with the minimal c that can fix(b >= a[i]) the bug using set >. And he also will fix next k — 1 bugs. If every time we have a student to do it(set is not empty) and the sum of all c is less or equals to s then we can do it. P.S for some reason my solution gets TLE on 9 test :(
 » 5 years ago, # |   +5 can't submit in the last 10s ? I submit my solution in the last 10s,but failed to submit
 » 5 years ago, # |   +43 Wow! Amazing strong-willed victory by Petr!Congratulations :)
 » 5 years ago, # |   +22 Failed Div2 Problem D because my program output N0 instead of NO ...
 » 5 years ago, # |   +11 In Div 2 A all different possible test cases is 6*6 = 36 but there is 38 test cases LOL :)
 » 5 years ago, # | ← Rev. 3 →   +14 Thank you for the nice contest! I've enjoyed it :). By the way, I got RE on problem B div1. But I've correct output at CF server (and on my local machine), and I can't see why it got RE. Can somebody tell me what I've done?My submission is here. => http://codeforces.com/contest/377/submission/5561801(UPD) I've submitted same code at practice, and got AC. http://codeforces.com/contest/377/submission/5562952
•  » » 5 years ago, # ^ |   +6 It seems to depends on the version of glibc. Using glibc with version 2.15, I got RE.I hope this information is useful.
•  » » 5 years ago, # ^ |   +12 Using the GNU C++ library debug mode, I get /usr/include/c++/4.8.2/bits/stl_queue.h:483:error: attempt to access an element in an empty container. Objects involved in the operation: sequence "this" @ 0x0xffd9f148 { type = St14priority_queueISt4pairIiiENSt7__debug6vectorIS1_SaIS1_EEESt7greaterIS1_EE; }on that test, which means that you attempt to access an empty priority queue.
•  » » 5 years ago, # ^ |   +73 It seems you had undefined behavior as mentioned by andreyv. But New Year will be soon, so it's time for miracles. Usually I do not do it, I rejudged your solution and got OK. Ratings will be updated soon. Happy New Year!
•  » » 5 years ago, # ^ |   +6 To : numa and andreyvThank you for investigating environments and my code! I'll be careful from now on. I'm glad to know the reasons :).To : MikeMirzayanovThanks for the rejudging! It seems that I was very lucky!And again, thanks for all whom tried to help me, and craus and dalex for helding a wonderful contest. Happy New Year for all!
 » 5 years ago, # |   +4 Very Fast system test. Loved it :)
 » 5 years ago, # |   +18 Why am I Expert with rating 1703 !?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 and I am Specialist with 1501!
•  » » 5 years ago, # ^ |   +4 And I am Pupil with rating 1504 !!
 » 5 years ago, # | ← Rev. 3 →   0 Thanks :D...I do on ideone without making it private.Have to take care from next time :(
•  » » 5 years ago, # ^ |   0 Maybe your solution and another one's solution were same.
 » 5 years ago, # |   +19 Div. 1 Div. 2 More info
 » 5 years ago, # |   +1 Hi If you visit my profile, hudai my rating is 1504. And when I take my mouse at the graph, it says EXPERT , But I am still Pupil . As far I know 1501-1700 is Expert range. But I am 1504 and still Pupil . I want to be blue :( :(
•  » » 5 years ago, # ^ |   +1 I saw this bug in other profiles too. I think it will be fixed soon.
•  » » » 5 years ago, # ^ |   +1 Its not a bug. Let the system alone it is working hard coloring coders :D
•  » » » 5 years ago, # ^ |   -7 Let's hope so, As I am going to be Blue for first time. Yayyy :)
•  » » 5 years ago, # ^ |   0 [1500,1699] is Expert range not [1501,1700] . :)
•  » » » 5 years ago, # ^ |   +1 I have the same problem. My rating has changed BUT the title and color is still NOT updated yet... Hope someone could help? Thanks!
 » 5 years ago, # |   +6 I took part in this contest but my rating hasn't changed (I submitted for problem A, div 2). I noticed that the ratings of other Div 2 participants has changed, but mine not. Could someone tell me why this happened?
•  » » 5 years ago, # ^ |   0 Same here. For a moment, I thought that my rating remained constant, which is rare :P
•  » » 5 years ago, # ^ |   0 Are you sure you registered for the contest?
•  » » » 5 years ago, # ^ |   +5 I'm sure. the submission during the contest: http://codeforces.com/contest/378/submission/5553767and the registered participants: http://codeforces.com/contestRegistrants/378/page/10?order=BY_RATING_DESC #2316
•  » » 5 years ago, # ^ |   +1 My rating didn't change too
•  » » » 5 years ago, # ^ |   0 My rating is the same
 » 5 years ago, # |   0 Can someone explain why DFS works for Div2 C?
•  » » 5 years ago, # ^ |   +6 flood fill s-k cells, that will remain empty. Mark the rest as 'X'.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2 @dbaluta As given graph is connected & consists of s empty cells, so, Run DFS from any empty cells & mark only (s-k) cells visited. Then, simply print the solution writing empty unmarked cell X . Thats all :)
•  » » 5 years ago, # ^ |   +1 For any cell, i can delete it if i am sure it won't block the path to any other "not deleted" node.So from every cell (x) ,we run dfs to delete cells reachable from (x).After deleting them, if i want to delete more cells, then it is safe to delete cell (x).
•  » » 5 years ago, # ^ |   0 --> Consider all the blocks where you have '.' as nodes..--> Now as you can read in the problem description , all the '.' are initially connected..--> So now you have a connected component with you..--> You have to now turn K '.' cells into WALL so that the component is still CONNECTED..--> Now , the Picture of DFS comes into the mind.. DFS will traverse all the nodes and will backtrack as soon as it reaches 'LEAF' node.. If you turn those leaf nodes into WALL your graph will still be a connected one!!Hope it helped!! :-)
•  » » » 5 years ago, # ^ |   0 Thanks a lot guys! Now is all clear :).
•  » » 5 years ago, # ^ |   0 i got wa on test 89 :( I had done bfs and marked levels.Then removed k nodes which have the highest levels.
•  » » » 5 years ago, # ^ |   0 Actually BFS should work : 5554249
 » 5 years ago, # |   +91 Now tourist really have to be ranked FIRST if he wants to increase his rating :o
•  » » 5 years ago, # ^ |   0 Думаю он может подняться со 2, если первым будет rng (судя по тому как считается рейтинг)
•  » » 5 years ago, # ^ |   -8 if his rank will be 2,and rng_58 rank 1,his rating will increase ;)
 » 5 years ago, # |   0 I don't have much experience about codeforces. Can u please explain** why am i not rated for contest** no.222 . i had solved 1 problem.
•  » » 5 years ago, # ^ |   0 finally updated..
 » 5 years ago, # | ← Rev. 3 →   +4 See these solutions : 5560186 5560332
 » 5 years ago, # |   0 Hey my raiting chnged to 1501 but y i am still graded as pupil?
 » 5 years ago, # | ← Rev. 2 →   +39 As noone has already done it, I will present solution to Div1 C, because in my opinion it is pretty funny and short.We just have to completely forget about n-m weakest heros and bruteforce remaining ones in O(2^m * m) using simple dp on masks. Why it is correct?In short, if we pick — we pick strongest one and if we ban a "bad" hero it doesn't matter which one (from the "bad" ones) we ban. It is obvious that if someone have to pick a hero, the best choice is to pick the strongest hero from remaining ones. So in a fixed moment of the game, if players will have to make k decisions, all picks will be among k actual best heros. Let us call that other heros are bad. Bad heros will never be picked. Since that, there is no point in missing a ban, because we can ban the weakest from remaining heros and that won't affect our solution, because noone will ever want to pick it. So if we consider an optimal sequence S1 of decisions for both players we can create another sequence S2 which will be still optimal for both players and chooses heros only from those m strongest ones. If there occurs missing a ban or banning a hero which can't be banned in S2, we ban the weakest remaining hero in S2 and there is no difference between those 2 choices in future picks, so these two states are equivalent.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Learn Russian, there are lots of comments with discussions of solutions after each round in our language =)
 » 5 years ago, # |   +13 If I'm not mistaken E is fairly easy. I will describe a solution with assumption that everything is continuous, not like in the problem statement (it's essentially the same problem, but easier to describe). Think about a whole process in a coordinate system OX — time axis and OY — cookies axis. Firstly sort buildings due to cookies per second (= possible slopes of our cookie graph) and process them in this order. After adding each building we want to maintain a graph of "maximum number of cookies we can achieve in a time t" — this graph consists of consecutive segments of lines with ascending slopes. It can be kept in a vector. When adding a building, we have to find first moment T (by binary search) when we can afford building it and update our graph (that means, finding an intersection of our graph and line passing through (T, 0) with slope corresponding to this building production. Just pop a few last elements of vector and push_back a new one. If we won't process buildings b such that there exists a building c such that c is cheaper and has bigger production, we can achieve O(n) time not O(n log n) by omiting binary search.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 This is convex hull optimization right? I didn't do contest because it was too late and I was tired, but I looked at questions and that is what I thought, but I wasn't sure because it was E and I thought it must be more complicated :PEdit: Actually I think I was wrong.
 » 5 years ago, # |   0 Can anyone explain me how to solve Div2 C/Div1 A?
•  » » 5 years ago, # ^ |   0 Div2 C: You need to create k walls and there are s empty cells. Start DFS from any empty cell but only walk s-k cells and mark those as visited. At the end, fill all the empty cells not visited with 'X'.Take care when k = 0.
 » 5 years ago, # |   +13 Can any one tell me about Good Bye — 2013 contest in detail? :)
 » 5 years ago, # |   +2 Well , my solution in Div2C is based on BFS , then there has a BFS tree when we run BFS then we can disconect their leaves( this are the nodes more farthest) . My submission. Code
 » 5 years ago, # | ← Rev. 2 →   -6 please can any one explain how good bye round will be for both divisions !? and how the rating system will be ?
•  » » 5 years ago, # ^ |   0 You can see here :)
 » 5 years ago, # |   +2 Wow, Zlobober became the new International Grandmaster, Congratulations! :)
 » 5 years ago, # |   +5 How do you solve Div 1 Developing Game?
 » 5 years ago, # |   0 I think there is a much simpler Greedy solution to Div 2 C. For each row note the number of empty cells in that row. Now if we have to delete k of the cells then we can completely convert the initial rows to X,such that the no of cells left in the row (which u have just processed ) is more than the number of cells left to convert to X. Now if there are some cells still left to convert ,except the cells which are connected to the row just immediately down u can convert into X. This algo works since when we convert entire intial rows to X the remaining is still connected.
 » 5 years ago, # |   0 In the problem B div 1, can anyone tell me why my JAVA solution got TLE (I do it in O(nlogn^2) : (.After the contest, I tried to rewrite it in C++ and got AC in 156 ms : (
•  » » 5 years ago, # ^ |   +8 Try to use classes with ints instead of Pairs of Integers and PriorityQueue instead of TreeSet.
•  » » » 5 years ago, # ^ |   +8 Thanks, I tried to use classes with ints instead of Pairs of Integers and got Accepted @_@. The objected data is so slow @_@
 » 5 years ago, # |   +3
 » 5 years ago, # | ← Rev. 2 →   +8 I think the test data of Div.1 E (Cookie Clicker) is not so strong for a Div.1 E problem. A simple O(n2) solution passes all the tests. In 5604868 I just deleted all the buildings which cannot be used in the optimal answer, using the method mentioned on the top of the editorial, and then used simple O(n2) dynamic programming.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +13 Thank you! It seems that in random tests this condition: `if(a[q[qe-1]].v