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

### meret's blog

By meret, 6 years ago, ,

Welcome to Codeforces Round #134!

After over two years, it is again my great pleasure to be the main problemsetter of a contest on Codeforces. Thanks a lot to Gerald for helping me organize the round. I hope you will enjoy solving the problems as much as we enjoyed preparing them for you.

Dynamic scoring will be used, but the problems will be ordered by their expected difficulty, from easiest to hardest. Are our predictions correct? I am eager to see. :-)

Good luck!

Update: The contest is over! Here are the results:

First division:

All contestants from the top seven solved three problems. Note that there was a tie for second place. :-)

Second division

In second division, seventeen contestants solved four problems. Nobody managed to crack E; it was also present in the first division as problem C, and proved tricky even for the experienced competitors.

Congratulations to the winners!

•
• +236
•

 » 6 years ago, # |   -31 Анонс как-то слишком заранее сделан... Давно такого не было.
•  » » 6 years ago, # ^ |   -16 А CFR129 давно был? И в нем анонс еще раньше сделан.
•  » » 6 years ago, # ^ |   +10 Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).
•  » » 6 years ago, # ^ |   +116
•  » » » 6 years ago, # ^ |   -58
•  » » » 6 years ago, # ^ |   +11 Can someone translate this for me please? I feel left out!
•  » » » » 6 years ago, # ^ |   +10 ...But when i do "you don't know what i am saying"
 » 6 years ago, # |   +4 Thanks for your hardwork,and I must say that I love the sentence "but the problems will be ordered by their expected difficulty, from easiest to hardest" most.Hope to solve as much as I can.
 » 6 years ago, # | ← Rev. 2 →   -20 Registration duration is diffirence,only 9 hour and 30 minutes, will be start 01:00AM,will be end 10:30AM
•  » » 6 years ago, # ^ |   -8 Why have negative votes,He is true.
•  » » » 6 years ago, # ^ |   -30 As mentioned before. One does not simply try to understand negative votes on codeforces.
 » 6 years ago, # |   -31 And the score distribution is… :-?
•  » » 6 years ago, # ^ |   +1 There is dynamic scoring. Read this for more information: http://codeforces.com/blog/entry/4172
 » 6 years ago, # |   -13 Good luck, everybody!
•  » » 6 years ago, # ^ |   -8 and have fun!
•  » » » 6 years ago, # ^ |   +3 and read every problem statement! ^_^
•  » » » » 6 years ago, # ^ |   +5 attentively
 » 6 years ago, # |   0 I'm so happy, that round start 5mins after full hour :D
•  » » 6 years ago, # ^ |   0 why?! contest duration was 2 hour and no 2h 5m so this is not main
 » 6 years ago, # | ← Rev. 2 →   0 Объясните, пожалуйста, D div 2) Больше часа на ней просидел( Explain , plz , D div 2)
•  » » 6 years ago, # ^ |   +3 translate from google: Explain, please, D div 2) more than an hour spent on it (
•  » » 6 years ago, # ^ |   +8 Hint: use Euclidean algorithm.
•  » » » 6 years ago, # ^ |   0 Ok, thanks, I think about it
•  » » 6 years ago, # ^ |   +2 Think backwards: if a>b then (a, b) -> (a, b-a)
•  » » » 6 years ago, # ^ |   +3 eg. 6 10 solve 10 test 1 to 9 when test 8 must be below: 10 8 2 8 2 6 2 4 2 2 assert not this. when test 7 must be below: 10 7 3 7 3 4 3 1 2 1 1 1 here have two possible, choice best one 
 » 6 years ago, # |   +8 Great contest! All tasks were very interesting, even A(Div 2)!
 » 6 years ago, # | ← Rev. 3 →   -8 Сорри, поспешил.
 » 6 years ago, # |   +10 Problem B is fine. Solution is easy but I could not guess it during the contest...
 » 6 years ago, # |   -13 so quickly rating!
 » 6 years ago, # | ← Rev. 2 →   +8 Nice problem-set but two 500 pointers in div 2, and no 1500 or 2000 pointers in between 1000 and 3000 seemed odd.(Though it happened due to dynamic scoring)
 » 6 years ago, # |   +46 It's a nice contest!Well done problemsetter meret!
 » 6 years ago, # |   0 How soon will the rating be refreshed?
 » 6 years ago, # |   +10 Nice problems.I'm looking forward to tutorial because nobody solved all problems.
•  » » 6 years ago, # ^ |   +10 Wish meret would write the editorial.
•  » » » 6 years ago, # ^ |   +5 I'm eager to learn to solve problem D and E.
 » 6 years ago, # |   +6 Nice problem C div 2. I was studying Graph Theory some hours ago and I got AC in this problem with a DFS.
•  » » 6 years ago, # ^ |   +1 I use UFS in this problem.I think this problem is very flexible,and there's more than one way to solve it.
•  » » » 6 years ago, # ^ |   +3 What is UFS, I never heard this algorithm, by the way I solved this problem with Union-Find Set.
•  » » » » 6 years ago, # ^ |   +3 Union-Find Set.A useful data structure.
•  » » 6 years ago, # ^ |   0 shater -_-
•  » » 6 years ago, # ^ |   0 UFS is a better choice.
 » 6 years ago, # |   0 Problem E is so Hard..
 » 6 years ago, # |   +1 is there any other way (other than graph theory) to solve the problem C(div 2)?if yes,can anyone provide a hint..
•  » » 6 years ago, # ^ |   0 You can use DSU.
•  » » » 6 years ago, # ^ |   0 sorry，what's DSU short for?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Disjoint-Set Union
•  » » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ |   +3 Just wrote a code that solves it without explicitly involving graphs: 2031563The idea is the same as in the graph solution, you just assign each point to a group as you process the input (creating a new group when a point you just added has no other reachable point), and if necessary merge groups if a point is found that merges some groups together. The result is the amount of groups minus 1.
•  » » » 6 years ago, # ^ |   0 This problem can be solved in N log N time with union find. I think I wrote a good example http://codeforces.com/contest/218/submission/2046921
 » 6 years ago, # |   +6 [user:meret]will someone write the editorial???
 » 6 years ago, # | ← Rev. 4 →   0 In Problem B Div.1 (Blackboard Fibonacci), I try to run the large test case (999997 999997) in www.Ideone.com and my laptop then I got runtime Error. But when i submit it to Codeforces system, it accepted :-o (Although the final test has the same test case :-o)My submission: Can anyone tell me why?
•  » » 6 years ago, # ^ |   +14 Maybe problem is in stack size, because you use recursion.Here, on CodeForces, stacksize is increased for g++ using compilation string
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Thank you!Upd: Another Online Judge don't increase stacksize :-(, so my solution can't get AC in some problems. Is it possible to increase stacksize in C++ source code :-(.As far as I know #pragma comment(linker, “/STACK: 268435456”) works only in MS Visual C++.How about G++ compiler ?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 AFAIK, there no way to do in G++, but you can write your problem not recoursively(or use MSVC++, of course)
 » 6 years ago, # | ← Rev. 2 →   +13 I don't know if DIV I — C was so hard or DIV I — B was hard enough that people spent a lot of time in that problem and didn't have enough time for problem C.BTW... My solution for DIV I — B was hacked during the contest and I couldn't fix it... The test case? 1 1... I hardcoded it asTinstead of0 TEDIT: Fixing that case passed system test after contest was over.
•  » » 6 years ago, # ^ |   +1 I feel your pain.
 » 6 years ago, # |   +13 Thanks for holding a match at a different time than usual. I enjoy Codeforces contests but have a hard time competing at the usual time. I enjoyed these problems and hope I don't have to wait so long before my next contest.
•  » » 6 years ago, # ^ |   -22 To the opposite, it was really hard for me to compete here, in Russia, because of that awful Saturday morning:( I wish next time morning-contests would be held one or two hours later — just to have a good sleep... please!:-)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +18 Oh, common, 11am is not a problem, SRM at 5am is :)
•  » » » 6 years ago, # ^ |   +5 Please think about other countries.For example,the usual contest time(7:30PM Moscow Time) is 11:30PM in China.So I think we should have more contests at times like this one.
•  » » » » 6 years ago, # ^ |   +1 Ok, so why not to have contests always at different time?
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -6 becose in other countris is different time and many people will not participate in contests. UPD: and 7:30 PM (moscow time) is great time for many countris
 » 6 years ago, # |   +6 Could anyone tell me how to solve Problem E of Div1?Thanks.
•  » » 6 years ago, # ^ |   +3 I have solved the problem.
•  » » » 6 years ago, # ^ |   +6 YM I haven't solve C of Div1 now. I can't understand the code. So I play DotA.. How can you solve D and E?
•  » » » 6 years ago, # ^ |   0 Indeed，my solution is the same as panyuchao's
•  » » 6 years ago, # ^ | ← Rev. 2 →   -22 you need idea? or to know how solved problem? to solved problem E link here and problems official tutorial(ideas) is not public but is 5 different accepted solution,which i think help you. authors and solutios:
•  » » » 6 years ago, # ^ |   +7 Solutions 2032857 2029369 are very different.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -11 ...
•  » » » » 6 years ago, # ^ |   +1 Submissions 2033918 and 2028007 are also very different!
 » 6 years ago, # | ← Rev. 2 →   +2 Could anyone tell me how to solve Problem C of Div1 (Problem E of Div2)? I have seen some codes but I still can't understand them. Who can give me some hints or useful conclusions to solve this problem? Thanks very very much!
•  » » 6 years ago, # ^ | ← Rev. 4 →   +8 It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {c1, ..., cn}.Replace each '?' by either ci or cj, i and j being arbitrary for now. Look at the values in the four cases (ci, cj) = (0, 0), (0, 1), (1, 0) or (1, 1).For example, for (ci&(ci&cj)) we would get 0, 0, 0, 1. Note that there's only one way to get 1. If a "3 versus 1" or "1 versus 3" can happen, then choose the right i and j, and the answer will be "YES". If a "2 versus 2" of the form 0, 0, 1, 1 or 0, 1, 0, 1 or 1, 1, 0, 0, or 1, 0, 1, 0 can happen, you can deduce ci or cj, the answer will be "YES". If none of those situations happen, the answer will be "NO".
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 Thank you very much.Supose that F(ci,cj) is the result of permulation,what is the inital value of F(0,0) F(0,1) F(1,0) F(1,1)? Thank you.
•  » » » » 6 years ago, # ^ |   +3 You can compute the values taken in the four cases recursively. Look at this submission for a better idea: 2032900
•  » » » 6 years ago, # ^ |   0 Could any one can explain why "not all colonies are of the same type" is so important ? ..
•  » » » » 6 years ago, # ^ |   +6 “not all colonies are of the same type” is important for '((?^?)&?)'
•  » » » » » 6 years ago, # ^ |   0 I Got!..
•  » » » 6 years ago, # ^ |   0 Could anyone provide some tricky test cases for Div1-C? I am failing case 13 and its huge :/ (all the tests after 13 are huge too..) Thank you.
•  » » » » 6 years ago, # ^ |   +3 '((?^?)|(?^?))'
 » 6 years ago, # |   -12 Why is the task of E so little decided?
 » 6 years ago, # |   +29 why the editorial is not uploaded yet ?
 » 6 years ago, # |   0 It looks weird to have 7 people in top 6 when the "6th" place is non-tied. If there is a 2-way tie at place n, I believe the standard way is to denote the next place (n+2), not (n+1).
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 This is how I did it in the code of the message, for some reason the system replaces it with the enumeration that you see.
 » 5 years ago, # |   0 No editorial yet ... :/
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   0 I meant editorial for all problems. In the link given by you, there is no editorial for 218B - Airport. I was searching for its dp solution.