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!

I love that balance between mathematics and programming!

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~

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 :)

There wasn't any surprise for this round! I was waiting a long long time for this day and CF #200! :)

It will be better if there are extra T-shirts for coders which behaved excellently in CF Round #200!

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... )

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

Thank you :)

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

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.

Which Mike is he? :D

So which is the score distribution? :-"

and score distribution ??

Score distribution is standard

Nice problem set linking science with coding :) !!

cf was unavailable for long time. time should be increased.

my code in mingw32 output correct answer but here ,cf said wrong answer!!!:| why?

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?

score distribution was so wrong

I wonder what's wrong with the score distribution?

A>B>C

One of the best contests I ever participated on CF. Less to code more to think :)

I loved the round and absolutely loved the problem statements and setting 5/5

How 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

f(a,b) = a/b + f(b, a%b);

But this might fail according to this

Good catch. (fortunately it passed according to given scenario)

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)

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).

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.

`%lld`

was never banned. It is justrecommendedto 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.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 :)

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.

Nice problemset!

Especially for problem E, the solution is quite simple (maxflow-mincut theorem) but it's hard to think in that way. :)

Thanks; the intended solution was to use Gomory-Hu tree, as Swistakk explained earlier.

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:

Then we focus on X and Y and do the same thing.

Exactly. That's how Gomory-Hu works :). But it's not straightforward to prove that these bounds are really the best ones.

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.

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.

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?

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...

Rating update was quite fast! :)

Can anyone tell me why this code fails on time limit ? (Div.1 Problem C)

just my guess:

Change

`l1`

,`r1`

and`m1`

to`int`

.http://codeforces.com/contest/343/submission/4472161

thanks )) but why?? :(

We want T-shirts : )

I wanted them too... ;(

Any hints for Problem D div2 ?

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

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

i realy like div1 problem D , i think range assign with segment tree is not intended solution , is it?

It is actually, the core of the solution is to color some whole original tree subtrees in logarithmic time.

Time limit is 4 seconds , so i think that , intended solution is heavy — light decomposition.

Nop, time limit 4 was set for Java solutions.

i see.

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

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!!!!!!

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.

Thanks for the clarification ...

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.

You should read the statements more carefully.

There are only two types of combination:

1) x -> x + 1

2) x — > 1/(1/x+1/1)

There is no x,y -> 1/(1/x+1/y)

What a great contest, I really enjoyed it...

I tried to hack this solution on test case "++++" because of the intermediate state (s[2] == s[-1]), but no runtime error, why?

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.

thanks..i think i should ask this question to cpp compiler :P

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!

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.

Where can we get an Editorial for this round?

Don't worry guys, we will complete it by evening.

Done, enjoy. ;)

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).

not O(Qlog N) , O(Qlog NlogN)

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.

The problems were interesting! I liked them!

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...

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:

Thank you!

What a nice tag for the blog post :) "everybody reads tags" Thanks for the laugh!

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?

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.