### gen's blog

By gen, 8 years ago, translation,

Hello everyone!

The anniversary Codeforces Round #200 is scheduled to take place today at 7:30 PM Moscow time. The round will be held in both divisions and will be rated.

The round problems were prepared by Evgeny Vihrov (gen), Andrey Vihrov (andreyv) and Gerald Agapov (Gerald). As always, we would like to thank Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems, and also Maria Belova (Delinur) for translating the problem statements.

In this round you will help mad scientist Mike to realise his peculiar ideas and carry out unusual experiments. The authors think that the problems constitute a good balance between mathematics and programming. We also tried to make the statements short and easy to read :] As always, we hope that every participant will find a problem to his taste.

We wish you good luck and an interesting round!

UPD1: Score distribution is standard:

DivI: 500 1000 1500 2000 2500

DivII: 500 1000 1500 2000 2500

UPD2: Congratulations to the top 5 winners in each division!

#### DivII

• +204

 » 8 years ago, # |   +18 I love that balance between mathematics and programming!
 » 8 years ago, # |   +111 In round #100, the top 100 participants were awarded t-shirts. How nice if top 200 will be awarded in #200 and so on :-) Seriously, what will be the next round which awards the top X participants? Haha~
•  » » 8 years ago, # ^ |   0 Top 200 will be awarded in CF #200 and so on ? So after next few years Mike have to buy more than 1000 T-shirts :) What about your sons in the future when they start to compete :) I think Mike need to Open a T-shirts factory for next generation :)
•  » » 8 years ago, # ^ |   -7 200% rating for everyone:)
 » 8 years ago, # |   +8 There wasn't any surprise for this round! I was waiting a long long time for this day and CF #200! :)
 » 8 years ago, # |   +21 It will be better if there are extra T-shirts for coders which behaved excellently in CF Round #200!
 » 8 years ago, # | ← Rev. 5 →   +17 Time flies! Codeforces #100 is my first round, and now it comes to #200 rapidly.It gives a lot of fun, hope it to be better and better.(of course it's already terrific now, except the network speed some times... )
 » 8 years ago, # | ← Rev. 2 →   +11 I like your handle gen! MCZ Xian, a Gen user in Street Fighter 4, won EVO this year. EVO is the biggest fighting game tournament in the world. Did anyone watch it too on stream ?Sorry for being off topic :p
•  » » 8 years ago, # ^ |   +3 Thank you :)
 » 8 years ago, # |   -44 What about awarding all participants with +/- 20% of rating. If their rating is going to increase, increase it 20% more and if it is to be decreased, decrease it 20% less :-D
•  » » 8 years ago, # ^ |   +4 Rating changes are irregular in a way — even if you get the same place, the rating change depends on the others who compete (your 'relative place'). So that'd be hardly noticeable.
 » 8 years ago, # |   +3 Which Mike is he? :D
 » 8 years ago, # |   -14 So which is the score distribution? :-"
 » 8 years ago, # |   -26 and score distribution ??
•  » » 8 years ago, # ^ |   +13 Score distribution is standard
 » 8 years ago, # |   +3 Nice problem set linking science with coding :) !!
 » 8 years ago, # |   +2 cf was unavailable for long time. time should be increased.
 » 8 years ago, # |   -9 my code in mingw32 output correct answer but here ,cf said wrong answer!!!:| why?
•  » » 8 years ago, # ^ |   -10 because gods of computers hates you !
•  » » 8 years ago, # ^ |   0 different compiler may result in a slightly different result. Or may also happen when u compile using windows or linux. maybe u should post your code so we could check what is wrong with it?
 » 8 years ago, # |   -28 score distribution was so wrong
•  » » 8 years ago, # ^ |   0 I wonder what's wrong with the score distribution?
•  » » » 8 years ago, # ^ |   -13 A>B>C
 » 8 years ago, # |   +3 One of the best contests I ever participated on CF. Less to code more to think :)
 » 8 years ago, # |   +4 I loved the round and absolutely loved the problem statements and setting 5/5How could I approach problem C efficiently?I only managed to deduce a formula for some special cases... If anyone could give me some tips that would be great :)Thanks,Bruno
•  » » 8 years ago, # ^ |   0 f(a,b) = a/b + f(b, a%b);
•  » » » 8 years ago, # ^ |   0 But this might fail according to this
•  » » » » 8 years ago, # ^ |   0 Good catch. (fortunately it passed according to given scenario)
•  » » » » 8 years ago, # ^ |   0 The question permits only a.)one resistor; b.)an element and one resistor plugged in sequence; c.)an element and one resistor plugged in parallel.so u only can add one resistor at a time to the existing element. (u cannot add two elements)
•  » » 8 years ago, # ^ | ← Rev. 7 →   0 solve (a, b) = (b / a) + solve (min(a, b % a), max (a, b % a)) and solve (0, a) = 0;Explanation: you assume that b >= a, then you will take (b / a) resistors for taking in series with other resistors, so cost (b /a) for those resistors. For remaining you need to use 1 and x in parrallel which is a / b = x / (x + 1). which means x = a / (b — a).
 » 8 years ago, # | ← Rev. 2 →   0 In Div1, problem A, in my room, I saw two people use %lld to read or write 64-bit integers in c++, so I hack one of them, but unsucessful. Does it mean is using %lld to read or write 64-bit integers is no longer banned? Maybe next time, the warning "Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier." can be removed.
•  » » 8 years ago, # ^ |   +5 %lld was never banned. It is just recommended to use %I64d due to historical reasons. With modern MinGW %lld seems to work as well.The warning cannot be removed as some people could be using old compilers on their own Windows computers, and then wonder why %lld does not work locally.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +2 I think that means "there exists at least one number when %lld will read not exactly the same as %I64d will under some compiler" rather than "it will always read wrong". So maybe you just didn't guess with hack :)
 » 8 years ago, # | ← Rev. 2 →   +14 E can be solved by using Gomory-Hu algorithm. It takes the graph and in O(n * flow time) computes a tree such that maxflow from a to b is the minimum weight of an edge on a path from a to b (at first glance one can be amazed that such a tree exists but after some thought it makes sense). So we just have a tree and have to find a permutation that maximizes sum of the lightest edges on paths v_i -> v_{i+1} Answer to this problem is sum of weights of edges in such a tree. Just take the heaviest edge and use divide and conquer algorithm.
 » 8 years ago, # |   +6 Nice problemset!Especially for problem E, the solution is quite simple (maxflow-mincut theorem) but it's hard to think in that way. :)
•  » » 8 years ago, # ^ |   +13 Thanks; the intended solution was to use Gomory-Hu tree, as Swistakk explained earlier.
•  » » » 8 years ago, # ^ |   +18 I see. That tree can be easily obtained by analyze it in this way:Suppose X-Y is a minimal cut of graph G. Then: If x \in X and y \in Y then flow(x, y) = cut(X, Y) Otherwise, it will be no less than cut(X, Y), we focus on nodes only in X and only in Y, so we split S into X and Y. Then we focus on X and Y and do the same thing.
•  » » » » 8 years ago, # ^ |   +8 Exactly. That's how Gomory-Hu works :). But it's not straightforward to prove that these bounds are really the best ones.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +8 Frankly saying, sometimes I really don't understand people's reasoning regarding to rating comments. I described solution to E and gen replied "Intended solution was as Swistakk explained" and got more pluses than me and few posts below cgy4ever explained Gomory-Hu algorithm and I said "yes, that's how Gomory-Hu works" and I got more pluses than him :P.EDIT: Note that ratings I am reffering to may vary. When I was writing this comment cgy4ever's comment got +5 and mine response got +8, but now he has got +16 and I still got +8 :D.
•  » » » » » » 8 years ago, # ^ |   +3 It's even weirder when there are 2 comments below each other, both saying something along the lines of "good luck", one of them is rated around -50 and the other around +50. The only reasonable explanation is heavy trolling of some comments.As for me, I usually vote minus on "spam" comments (those that only contain one of the usual phrases related to contests etc.), plus on comments that contribute something to me or are well written (that, of course, requires the comment to talk about something useful, meaningful) and for comments that are just random short replies or I'm unsure of how to vote, I don't vote at all.
•  » » » » » » » 8 years ago, # ^ |   +21 Last Wednesday i took 10 random new neutral comments with 0 votes each, upvoted random 5 of them and downvoted other 5. In 12 hours first 5 had +2, +11, +5, +4, +8, and second 5 had -9, -5, -8, -3, -4 respectively. Funny, isn't it?
•  » » » » » » » » 8 years ago, # ^ |   +2 Yeah, that's one type of trolling. Just voting the more common option. Voting randomly is another common type. (In general, trolling is anything that isn't based at all on your view of the content.)Not like we can affect it, anyway. And when one has large contribution, it starts only depending on blogs — comments have much lower weight, so unless you're getting like +50 or -50 for one comment, it doesn't affect contribution at all...
 » 8 years ago, # |   0 Rating update was quite fast! :)
 » 8 years ago, # |   +5 Can anyone tell me why this code fails on time limit ? (Div.1 Problem C)
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 just my guess:  l1=5; r1=7; while (l1+1 < r1) { m1=(l1+r1)/2; if (true) l1=m1; else r1=m1-1; }
•  » » 8 years ago, # ^ |   0 Change l1, r1 and m1 to int.http://codeforces.com/contest/343/submission/4472161
•  » » » 8 years ago, # ^ |   0 thanks )) but why?? :(
 » 8 years ago, # |   -14 We want T-shirts : )
•  » » 8 years ago, # ^ |   +7 I wanted them too... ;(
 » 8 years ago, # |   0 Any hints for Problem D div2 ?
•  » » 8 years ago, # ^ |   0 My solution is prolly the easiest, though longer than optimal, to understand. I use linked list and remove ++s and --s http://codeforces.com/contest/344/submission/4465292
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 You can just use a stack and assign digits for + and -. Let's say '+' is 1 and 0 is '-' . Then you can do the following:If current character's code(0 or 1) is the same as the stack's top, then pop, otherwise push the code in the stack. Then, if the stack is empty the answer is "Yes", and if it is not, the answer is "No". Here is my solution 4464633
 » 8 years ago, # |   +2 i realy like div1 problem D , i think range assign with segment tree is not intended solution , is it?
•  » » 8 years ago, # ^ |   +5 It is actually, the core of the solution is to color some whole original tree subtrees in logarithmic time.
•  » » » 8 years ago, # ^ |   0 Time limit is 4 seconds , so i think that , intended solution is heavy — light decomposition.
•  » » » » 8 years ago, # ^ |   0 Nop, time limit 4 was set for Java solutions.
•  » » » » » 8 years ago, # ^ |   0 i see.
 » 8 years ago, # |   -8 The contest was very specific! It was about any kind of science: Chemistry, Physics, Math, ... . gen was right. It had questions for any tastes. :D
 » 8 years ago, # |   0 Is 21/10 a valid test case for Problem-C (Div.2).....?acc. to me (7) and (3) in parallel results in (21/10) which equals to 10 resistors minimum. But acc. to AC soln's. ans = 12.Pls clarify!!!!!!
•  » » 8 years ago, # ^ |   0 You cannot combine 7 and 3 in parallel. According to the question, you can combine an element with just one 1 ohm resistor. Hence, combination of two elements in parallel in not permitted.
•  » » » 8 years ago, # ^ |   0 Thanks for the clarification ...
•  » » 8 years ago, # ^ |   0 And 6/5 is also a wrong case. We can use (2) and (3) to get it: 1 / (1/2) + (1/3) = 6/5. So the answer should be 5, not 6.
•  » » » 8 years ago, # ^ |   +1 You should read the statements more carefully.There are only two types of combination:1) x -> x + 12) x — > 1/(1/x+1/1)There is no x,y -> 1/(1/x+1/y)
 » 8 years ago, # |   +5 What a great contest, I really enjoyed it...
 » 8 years ago, # |   0 I tried to hack this solution on test case "++++" because of the intermediate state (s[2] == s[-1]), but no runtime error, why?
•  » » 8 years ago, # ^ |   +9 Well, since it's not Pascal with its range checking for everything, he just access whatever byte is before the char array. It is most likely accessible to the program (hence no segmentation fault) and since we have no idea what's in there, it can only possibly affect the code if there is '-' or '+', meaning that in at least 127 out of 128 cases it will run just fine.
•  » » » 8 years ago, # ^ |   +2 thanks..i think i should ask this question to cpp compiler :P
 » 8 years ago, # |   0 What I liked about this round was that the problems were more connected to the real world than usually. Solving them almost felt like doing some actual work:) Way to go, gen!
 » 8 years ago, # |   +16 I became red and feel very happy!!! And first I solved 4 problems. Div1 D was very very cool problem! (I could answer the different types of queries by using the same euler-tour array!!) That should be one of my most favorite problems!! Thanks for writer.
 » 8 years ago, # |   +8 Where can we get an Editorial for this round?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 Don't worry guys, we will complete it by evening.Done, enjoy. ;)
 » 8 years ago, # |   +8 I think no one wrote about the solution of Div1 D, so I write it.third query can be said, "which was the last operation, adding water to the ancestors of the node, or emitting water from the children of the node?".So we want to calculate two values -- the time of last operation no.1 which added water to the ancestors of the node, and the time of last operation no.2 which emitted water from the children of the node.Both queries can be done with the different segment trees to the array of Euler-tour.So we can solve this problem in O(Qlog N).
•  » » 8 years ago, # ^ |   -18 not O(Qlog N) , O(Qlog NlogN)
•  » » » 8 years ago, # ^ |   0 This can be solved in O(Q log N), but I know another solution whose order is O(Q log^2 N). (Actually I found this at first, but I thought it is too slow to get accepted and too hard to code, so I tried to find another solution.)In this solution, we can use heavy-light decomposition or the general technique of merge the data structures like std::set.
 » 8 years ago, # |   +8 The problems were interesting! I liked them!
 » 8 years ago, # |   +13 Hello,Anyone has any tips about Problem E for Div. 2?I am totally clueless about it and still trying to grasp logic of problems C and D...
•  » » 8 years ago, # ^ |   +8 Hint for problem E Div. 2 (Read Time):Try binary search the answer. For particular time T you have to determine if it is possible to read all tracks (p1..pm) in time T.Another hint: There exists an optimal solution where heads don't change their relative order.
•  » » » 8 years ago, # ^ |   0 Thank you!
 » 8 years ago, # |   +5 What a nice tag for the blog post :) "everybody reads tags" Thanks for the laugh!
 » 8 years ago, # |   0 I think there is an issue with Problem 343A — Rational Resistance. Here according to the editorial the answer to the ratio 6/5 would be 6(I have verified this with an accepted solution). But this ratio can be achieved with a resistance of 2 and 3 in parallel, which makes the number of resistors required equal to 5 which would imply the editorial and the system tests to be wrong.Am I missing something here?
•  » » 8 years ago, # ^ |   +3 you cannot put resistance of 2 and 3 in parallel.According to the problem statement you can only put Ro and Re in parallel where Ro = 1.
 » 8 years ago, # |   0 Willing to join one of those one day xD