Hello there!

Codeforces Round #172 will take place on Sunday, March 10th at 19:30 MSK(23:30 CST).

This is my second time participating in prepration a Codeforces Round. Last time assist with WJMZBMR is an unforgettable experience. This time, the hardest problems were created by **Jiatai Huang**(CMHJT) and others by me and **Yuping Luo**(roosephu).

Testers are Sevenkplus, WJMZBMR, pashka and Seter.

We gratefully acknowledge **Gerald Agapov**(Gerald) for his help in giving advise about the problems, **Delinur** for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

Here let me express my personal thanks to the Codeforces community, which has given me so much gleamy idea in the past two years.

Believe it or not, Codeforces has kept her feet in China's ACM community since last year. AFAIK, some of the hardest problems have been used as this year's Winter Camp homework for our National Olympiad in Informatics.

Also thanks to watashi, ftiasch and xlk. Discussing problem with all of you, has inspired me a lot.

500 — 1000 — 1500 — 2000 — 2500.

We are going to use a standard score distribution in both divisions.

The problemset is a little bit easier than last time, but we still believe, getting all of those five problems accepeted will be a challenging mission even for an seasoned International Grandmaster. The problemset has been marriaged with variety flavor. Take a glance over all five problems before going to coding might be a wise strategy.

**UPD:**

The contest is over, congratulations to the winners:

Div1:

Div2:

Congratulation to tclsm2012, who also solve the problem D!

We feel so pity to al13n, your last optimization for problem D is wrong. Problem D has a **O(mklogn)** algorithm. And we are extremely sorry to Jacob, your solution for problem E can pass most of the random tests but actually is wrong.

Jacob... can you explain your solution for us :)

We need collect some feedback about this round .. So the editorial will appear after a period of time.

**UPD:**

I used to hate those guys who set problems, but didn't write editorial at all! But when things turn to myself, I found it is really difficult to cover all cases. Anyway, it has been done.

Very early announcement! Excellent!

QAQ..

123

ymm

Believe me . It will be a very interesting round. So , good luck and have fun

you have no chance to attend this contest. look at me!!!!!!! = = TAT(it's terrible to zhuangbi)

... No .. The problem has been substituted ... Actually he didn't know what the finally problem it is. ..

So you mean that he is going to participate???

Uw...That depends on himself ..

Surely I will not participate......

Ooooooooch , man ~ Are you crazy?

They are saying that the hardest problems were created.I think it's going to be interesting!!!

I think it will be interesting round with 9 creators :)

... Only setters and testers have saw the problems.)

What about translator?!:) She translated and she didn't see the problems?! WOW...Perfect:)

Well, you are right ..

Delinurisn't going to participate the contest after all .. We'll try our best on the confidential work of the problems, to ensure the competition run fairly. You can trust us on this point, seriously ~~ ... )Thx...I hope that in this contest will not be users like xiao_dao or xiaodao_50216 like previous contest (I mean rng_50216) :)

... And like peter50216?

Noo...i didn't mean peter50216 and rng_58...I mean only rng_50216...He registered 39 hours ago...before Round #171...

Maybe 4 problem-setter

... Why not participate ? .. (I am definitely sure you will lost your red handle after this round.) Uw, actually we are short of men right now... How about helping us test one or two of them? (′▽`〃)

xiaodao: you should protect your solutions:

these solutions are look very similar:

On codeforces: 3158774 3157931

3216871 3216492

On codechef: codechef1 codechef2

`Micro Mezzo Macro Flation -- Overheated Economy`

haha I love C too.That's how you announce a serious contest, not 2 hours before the competition! I wish everyone did the same.

it seems i am the only one holding a yellow handle among all the problem setters..lol

lol.. I think you can easily become red if you're willing to.

yes, maybe, but not this time, because he isnt participating :D

And you have created the hardest problem I've ever seen...lol

Because I'm the lost thing lol

your avatar ... Can't look directly <_<

I'm wondering if I miscalculated or scheduled time for this round conflicts with TCO qualification round 1C?

TCO round is scheduled for Saturday, not for Sunday.

Ouch... probably, I should sleep more. Thanks!

No , it doesn't . TCO round 1C is on Saturday March 9th and codeforces round 172 is on Sunday 10th March .

We intended to set on Saturday .. .

So is it going to be on Saturday which is today or on Sunday???

Why can't you read the topic before asking such questions?

or see the timer on top-right part of the page, which shows how much is left till the contest.

oh,I wasn't aware of this page because it's not on the top...

and the discussing members & testers seems very great!! I believe the round will be an interesting one

It would be an interesting contest :)

.

Big Fans !

I wish you can get fully accepted

Пишите по русскому!

I smell a lot of mathematics.

Hmm... Can you explain why?

He is right about that

Haha WTF ??? ! Picture

whahahah lol

I don't know it's my browser problem or nhandi graph really have logical problem ? btw it's a beautiful bug !

There is the same problem with my graph.

Wow you guys have interesting graphs!!!

and also ruban

I think anybody participate in code forces rounds #170 & #171 simultaneously have same problem . maybe for a little mistake in set history of code forces #170

Great! Wish we have a great night!

Wish you all one more "Share it!" in your profile page :)

ym..

Again 865 participants in Div 1. The record was not broken!:D

Div. 1 A is boring...

Div. 2 C is boring, too...

Is it joke? Don't you know, that those problems are same?

why boring? I've spent about an hour without any result :(

But you had not solved it, right?

Could somebody explain me, how to solve it without formulas divination?

For example, you can divide shaded figure into 8 triangles.

I absolutely don't like this contest.

The problems were really hard. Didn't like this contest.

Should swap Div1.A and Div1.B

Well, I think B was harder conceptually to find algorithm, but A was harder to implement, and edge cases = annoying, also takes quite some time to solve on paper.

I think it's so hard for div 2

some ideas about D div 2 (B div 1)? I wrote rmq and rmq1 for the second maximum, but i didn't invent something faster than n*n*logn...

I think author's solution has O( n * log( 10^9 ) ) complexity

There is easy O(n) solution using stack to find first next greater number for each number.

What a shame, I thought it is O(n^2) and didn't solve this problem...

me too ! :|

There's an O(N) solution based on all nearest smaller values. I think it's a shame the constraints weren't higher.

10^5 is enough to forbid O(n^2) solution

I was thinking about this too, but N^2 for N = 10^5 is too slow for sure...

I use only one rmq, each time fix a max, find second max in left and right, then recursively on each side. which gives O(n * log(n) * log(n)) algorithm. http://codeforces.com/contest/281/submission/3284484

Problem Standard in DIV-2 was A,B,D,E,E :S

more like A,C,E,E,E i think

nearly solved B at the end, maybe if 2 or 5 more minutes :(

B wasn't so difficult, you can try all bs from 1 to n-1 in limit...

in my solution, i try from n to 1, so that it will replace the previous denominator if it has same rate of error

here is my submission which is accepted (after the contest :P) http://codeforces.com/contest/281/submission/3284962

Correctly is A, B, D, D, E.

I love xxx :))

I think this contest had too much mathmatical problems :|

Nice problems, thanks for the contest. I almost solved C, but maybe next time...

My C was almost correct, I had to try to solve it immediatelly after B and not try to solve D first...

It's the first time I send my uncompiled code in DIV2 A Time -> 1:12 :D

Keep us informed.

Big useless images make me cry.

Why doesn't system test start?

Soon ...

too much mathematics, A (div2) is nothing but a fun, and others are harder for div-2 contestants.

Div2 B is rather easy

isn't it a ternary search problem?

No need, you can try every denominator and binary search to find the numerator.

i did it, and get wa on 6th pretest, then i checked for numerator, numerator+1, numerator-1 for every denominator. i m sure of getting system failure :(

or you can calculate numerator directly in O(1)

It was not necessary,easy math in O(N) :)

A bruteforce setting the denominator and approximating the numerator in small iterations passes the test.

CODE

why system test is not stated yet? a lot people are going to have system failure on B (div-2) i guess.

В-div2 — это тернарный поиск ?

я бинпоиск отправил, претесты прошел:)

А как ты делал ? У меня идея была такая — для каждого знаменателя от 1 до n считать тернарником минимальное значение модуля, а потом из всех выбрать минимум.

Да, нужно было перебирать значение знаменателя искомой дроби, а числитель, при фиксированном знаменателе задается единственно, что позволяло решать задачу за O(n)..

систесты не прошел:) WA тест 33

перебор по знаменателю спокойно проходит. Числитель при известном знаменателе находится по простой формуле.

UPD. систесты прошло

Я тупо перебрал знаменатель. числитель выбирал один из int((i * a + 0.0) / b) и int((i * a + 0.0) / b + 0.5) сравнивал если меньше погрешность запоминал числитель и знаменатель. Самое главное если погрешность равна, а знаменатель меньше запомнить опять числитель и знаменатель.

when starts testing?

Interesting, systests didn't start and I moved from 255. to 254. ...

`The problemset is a little bit easier than last time`

. I wonder how hard the problems were last time.:D

Even tourist solved only A&B....

No, he did A B C in 33 minutes and is 7th.

Edit: Sorry, I talk about current contest.

I think it's harder than last time, this time the Problem E is too hard to have an correct solution,but the Problem C is simpler.

Good problems! tnx! :)

I hope, there won't be 50 tests in A div.2, or else the system testing will be too long. For such a trivial problem 10 test cases are more than enough.

This is the hardest contest i ever participate... But i like the Problem Div.2 B.I spend almost two hours with so excitement.(Though i can't solve it yet.)

Just enumerate the denominator....you can calculate numerator quickly...O(deno) You may find it interesting if you have noticed Python's Fraction.limit_denominator method...O(log deno)

Fraction.limit_denominator fails the tests :(

http://www.codeforces.com/contest/281/submission/3278048

maybe you can try Fraction(x, y) to construct a fraction x/y

Accepted :| "Easy come, easy go" :'( Thanks alot

Thanks for interesting problemset, but it was hard)

Oh damn, my E solution failed on test 101...

I'm so sorry...Your solution was totally wrong but accept all the random testdata...So I generated the test 101...

Turns out you don't need to be a contestant in order to challenge solutions. ;)

He is responsible for the problem E bcz the writer is in hospital ...

In fact I'm one of the testers lol..I've mentioned it but got too much negative feedback so it's hidden T_T..

Can you explain then what kind of test is that (testing log doesn't show much)?

Just random data with N=6000,B-A<=1000...I didn't have thought I could make your solution WA but finally I did it..Thanks to my random data generator..Your solution got 3 WA in 10 with this kind of data.

Hm, let me get this straight — you've added a test to fail Jacob's solution during or after the contest?

During ... actually we want let him know about that during the contest but we can't ... His solution seems strange for us ..

Did you add test 52 for problem C too?

No..

I only make 50 tests for Problem C.I think the test 51&52 is add by challenge.The successful challenge will be check by system and if the hacked solution can pass systest, then that test will be added

I misread your answer, sorry.

Please forgive a tester without experience..Next time I'll make data not too weak...T_T

I think it's not good to add tests using participant solution.

Believe or not,we have prepared 4 data by this generator and rest by weak generators,and he passed them all.But when we use this generator for 6 more data,he got WA in 3 of 6...This is my first time to prepare problems for CF,I only made 12 large data in 100 T_T...

.. Did you have a gmail?. I'll send it to you as a gift :)

I think the challenge work is up to contestants, and if a tester like you challenge someone, you should at least show him a message during the contest warning that you've challenged him. Seems to be kinda unfair.

So If a wrong solution didn't get challenged then it would be considered the same as the correct one? I think it is more unfair. the basic rule in Contests like CF or TC is that the solution should be CORRECT to get the scores, if the solution is indeed wrong, then it shouldn't passed of course. You may think that the test data is weak. but It is really hard to consider all possible algorithm to generate all anti-test. As today's case, his solution is indeed an wrong greedy. A experienced coder like Petr will find this is wrong and won't try that, but if some one simply come up with it without proof and accepted, isn't that kind of unfair?

Yes, you're right. But at least you should warning him during the contest, so he'll be able to see what's wrong or either find the correct solution.

Umm, we indeed thought of things like that but don't know how. but anyway the systems only says that he pass the pretest,that doesn't mean anything else.passing pretest also has the chance of failing.

Unfortunately there are a lot of obviously "wrong solutions" which pass system tests and got accepted. (See this, for example http://www.codeforces.com/blog/entry/5947#comment-113634 ) Of course one needs to be lucky to get points for those, but by challenging a particular one you don't give any chance to its author. Did you prove that all other submissions of all of the problems produce correct output for any valid test case?

What solution is considered to be correct is an interesting question. As I know, if we use only subset of a functional language, we can indeed prove that the outputs of it and the correct one are identical for all possible inputs from given range efficiently. We can even write a checker for this. However, for CF/TC problems and procedural languages I always thought that solution is correct if it passes system tests.

If wrong solution's passing is because of good luck then isn't wrong solution's being challenged because of bad luck?:) I apologize for this but I won't discard test 101.I believe rating second,learning first.Correct solution for E is magical and worth learning.Why don't we look forward to it instead of stuck in a wrong solution?:)

I'd like to do so but I can't..because I don't know how to touch with him..I apologize for our weak data at the beginning :) In fact this kind of data(N=6000 B-A<=1000) his solution can accept 7 in 10~

I'd like to know is this the first time when tests were added during contests or is it a common practise? Maybe it's a question not to you, but to Gerald

I think DIV1 B has weak tests too. just run 3284652 or 3283083 with test like this:

It's so strange for a contest with so many problem setters and problem testers (with high ratings) that has weak data in three problem out of seven. (Div1 B, C, E)

What is the problem with tests to the task C?

For me this is unfair. One could use a random generator with a fixed seed (say, 123467) and it is always possible to find a specific test to fail this kind of solutions. Solutions using randomized algorithms based on some random assumptions (say, there are less then 100 tests) do not have to work for 100000000 tests you can generate on your own using full contest time and prepared generators to fail them.

We're so sorry about this ...... )

That doesn't make sense. If you're sorry, then you think you did something wrong. If you did something wrong, correct it. Is no one able to correct the results in this special case, considered unfair by many members, maybe majority?

If you're sorry, then you DON'T necessarily think you did something wrong.

people often say they are sorry when they learn someone who they just asked after had died for example )

Yes, you do think you did something wrong. In your example you did that accidentally, and if you could, you would withdraw your hurting words. But you can't do anything, so you say sorry. Please don't limit yourself to saying sorry when you can revert something you did. Just do it.

Now I it's apparent that you made right decision and everybody's happy. You had little time to make this decision, but you did it right. Even Jacob would be unhappy to win with incorrect solution. So you needn't be sorry :) I am sorry for my harsh words.

Cool A solution BTW.

it's my fault... better to say my heart trouble..?

kapec b-shka u mnogih upala

I hope the editorial be published soon, like the announcement!

What's up with B?

number of failed after test 10 ~ number of succeeded So, the thing is that pass rate for is well near 50%

Guys, is 10^-6 realistic for Python float?

my God, hash somehow blowed the text up!

So, the thing is that pass rate for is well near 50%

How to calculate eps in Bdiv2?

I tried to use 1e-12 as EPS, but solution was challenged. Without EPS handling solution passed system tests.

In order to avoid using float number in problem B(div2), you may can use stern-brocot tree, I think.

Or just implement your own fraction class.

Oh, okay

bugs in topological sort.

-74 in round #171 and your overall rating increases. lucky :)

http://www.codeforces.com/profile/Obaida

see last 4 contest in my rating graph!!! (funny BUG) :P

Who added test 52 for problem C? It doesn't look like prepared test case and it failed 4 people including me, because of wrong calculation of a node depth in a tree. I don't think it was a main challenge in this task and it was the last test...

Well, I mean, the problem didn't say the edges had to go a certain way?

Yes, but I'm just interested if test 52 is one of the successful hacks or it was also added by organizers during the contest to make solutions of 4 people fail.

I think that it might be the successful hack made at 1:58:14, that was added to the system tests — what a fuc.ing bad luck...

Wait, does this work like topcoder such that successful hacks get added to the system tests?

yes.All successful hack would be added in sys-test.

tourist isn't codeforces target after this contest =(

hahahah

tourist rating also goes below 3000 in div 146. coincidentally writers was same.

@Admin ....my solution of D is showing Skipped final test....Is there any problem in system testing.?

problem b div2 test 33's answer is 1/1 but i think 2/2 , 3/3 , 4/3 are another solutions of it. :( a lot of contestants failed on test 33

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.

why i forgot that????? :|

Why are you asking this question to ME? :D

WTF? this solution gives answer 4/3 on test#33 7 6 3 why it got AC?

UPD: Link: http://codeforces.ru/contest/281/submission/3277121 UPD2: I compiled this code in VS 2012

What solution are you talking about?

can u tell me the meaning of Skipped final test.?

Waiting for comprehensive editorial from you, xiaodao ^_^

I don't know what to say... just look at this link : http://codeforces.com/bestRatingChanges/220401

[user:xiaoda] why is it showing skipped in final testing?? please reply..

Try to send a personal message

I didn't know ... > < 。。。

Great Problems , Fantastic Contest , Amazing System Tests , Brilliant Announcements. :)

I have an answer about test case#31 B Div2 (99997 99999 99996):

Why the answer should be 49999/50000,

if 49998/49999 is a better result, and is "nearest" to 99997/99999 ???

just try to use calc, and you will see it:

99997/99999 = 0,999979999799997999979999799998

49998/49999 = 0,999979999599991999839996799936

49999/50000 = 0,99998

You're right.

I think if this round will be retested a lot of solutions will get accepted, and my too.

Nope)

99997/99999 — 49998/49999 = 0,000000000200006000140003000062

49999/50000 — 99997/99999 = 0,000000000200002000020000200002

You're wrong, dude.

Can someone explain in details how problem D div2 is solved ? Thank you.

Avoid floating point calculation totally, use long long etc i.e. x/y < a/b iff x*b<a*y peform binary/ternary for AC.

I was talking about D :)

lol,you can use stack to get next max after a number using stack.O(n) algo.

I saw the solutions, I just wanted theoretical explanation.

I solved it choosing the 'easy' way, ommiting any special XOR properties. We can see that there are only O(n) candidates which we should check e.g. pairs (f, s) such that TwoHighest(l..r) = (f, s).

Let's get some f and find the nearest, higher s on the right: f<s && S[f]<S[s] && s is minimal. Then there cannot exist such s' > s that some TwoHighest(l..r) = (f, s'), because if range (l..r) contains both f and s', then it contains s, but f<s && f<s'. Analogically for the right->left way.

For each number, we find nearest higher number on the left and right. Then check every candidate(pairs (i, right(i)), (i, left(i))) and print the maximum result.

How to find nearest higher number on right(left): Have the stack A after proceeded(0..f-1) numbers(top(lowest)->down(highest)). When we get S[f] = x, we look at A, erase every S[s] < x and set Right[s] = x.

wow i only solved A for 498 points (should have solved B too, i made a very silly mistake) and my rating increased by 140! my sincerest thanks to whoever assigned the new ratings! :) :P

Aren't they assigned automatically?

i'm not sure, but my point was thanks to the administrators who are in charge of assigning ratings after contests, as my rating increased drastically after solving just one problem!

Just curious, is there also an O(n) solution if in div2.D, the "lucky number" of S[l..r] is defined as the xor of the maximum number and the minimum number in S[l..r]?

Curious about it too.

http://ideone.com/vix2hL

Sadly, on the contest I didn't see O(n), I was writing inner loop with break on bigger number found. 5 minutes after contest i've wrote this 67-line(it was simply real_i before, and it was O(n^2) on 6 1 2 3 4 5 6 test).

Sorry for bad grammar in ideone comments. I think I should go to bed nao~.

Uh, I've misread question, sorry.

I guess minimum xor maximum is O(N^2).

Suggest this input: 6 1 2 3 4 5 6. You need to xor 1 with 2 3 4 5 6. Then you need to xor 2 with 3 4 5 6, then you need to xor 3... You can't skip any of them.

I thought about this too. But I wonder if there are any mathematical properties can be explored in XOR operations to improve performance.

I think xor in this problem is like "function of two args, returns some predictable number, which is not really dependent on size of args". So large_num xor large_num doesn't allways equals large_num, and you need to cound all xor's to get the answer.

But if there's some magical properties, it will be nice if someone explain.

I guess there's an O(n) solution, as my one was O(n) and failed test #13 which offered a special case.

Let's denote our two target values as Big and Small.

The idea is following: at first assume that there are two numbers in the whole sequence with different positions of the first '1'in the binary form. Then the two target values should differ in that 'first-1' position. That means, that the Big has to have the first '1' at the same position as the max value of the sequence does. That means that we should look for the Big only among such values, and the Small among the rest. So, we just take the sequence as a set of intervals [ Big?, Small?, ... , Small? ] and [ Small? , ... , Small?, Big? ] and check every one of them for linear time. Total length of those intervals is less than 2n.

The last case, which I personally failed, is when all values have the same 'first 1'position. In this case.... well, at least one could subtract a corresponding degree of 2 from each one start again.

You can reference my code, it's rather short)

1D's TL should have been 3s..Then the obvious O(k^2logn) solution would get TLE.

tutorial for 1C,1D and 1E in Chinese https://www.13331.org/420.html

Chinese..... = =|||||

Well the contest was great!!! Thanks for the problem setters.

He is an iranian : http://codeforces.com/bestRatingChanges/6073 Faghat bara inke ma ham ye commenti dade bashim .... :D

There's also an issue during testing:

The Problem D has the correct solution O(mklogn) , but the constant is not small. It also has an small constant approach O(mk^2logn).

During test I suggest that the TL shouldn't be very large because the O(mk^2logn) solution may pass it.

But indeed the difference between slow Java O(mklogn) and fast C++ O(mk^2logn) is minor. So if we want Java solution passed, we can't keep C++(mk^2logn) solution TLE. As a result, some competitor passed it by an straight forward O(mk^2logn) solution, which is not really expected.

So you should set k <= 100 and increase time limit and no problem...

Edit: Or you should stress test it until you find such a test that it gets TLE.

Actually during the contest,only liouzhou_101 got AC. not too bad..

Above all, Orz Shenben WJMZBMR && Chairman Fotile... I'm sorry for that my solution is O(m·k^2·logn) with highly optimized. In fact, I have no ideas about a O(mklogn) solution. Just waiting for the tutorial...

actually in standard solution,it takes O(logn) per update,O(klogn) per query. So limiting the sum of k to 10^5 would be ok.

Now, since some people were asking for my solution of E, I'll describe briefly the main idea.

First of all let's build a mechanical system that would solve the given problem. The system consists of:

Now the problem is to model this system and find its equilibrium. The key point is to add particles one by one. Apparently particles can only interact via hard links (item 3 in system description), so new particle can either drag some of the previous particles down or up, forming a "critical interval" (with difference between adjacent y's being equal to a or b). In my solution I simply iterate through the length of the critical interval to find the moment, when it stops interacting with preceding particles.

I honestly believe, that overall my solution is correct, but most likely I missed something when accounting for wall-particle interactions. There is an obvious question arising about uniqueness of mechanical equilibrium in the described system, but in my opinion there isn't any constraint that could lock the system in a local minimum.

Attention to this data:

Your solution gives correct answer:

But when n=3:

It gives wrong answer:

It seems you don't put forth your strength to drag first two particles down :)

I read your code and believe that without "derivative" it can hardly be correct..I insist that your solution was a kind of wrong greedy idea because you only focus on "critical interval",and it may not be always right.If I haven't understood your idea correctly,can you explain it again for me? Sorry for my bad English. (>_<)

BTW,I used to think your solution only works when all the delta is close to A or B,but it proves to be incorrect :) And your idea is a bit close to our correct one.

It seems I haven't properly dealt with the case when one critical interval shares one particle with another one. In that case verifying the equilibrium for that particle becomes more complicated.

Whatever,you are the hero in this round! :) Can you forgive me for what I have done?

From my point of view, that was absolutely valid in this particular case to do what you did.

Since it was a clear flaw in my implementation, that test should've been there prior to the beginning of the contest (just for the reason that it's clearly rather special case) as well as many similar tests (say, a test with answer "+a +b +a +b ... "). Your only fault was to rely on random test generator instead of manually finding some interesting cases.

It's so kind of you!Thanks!Now I feel much better :)

Fixed.

3314820

Well, I think the problems were very nice and easy to understand. Good job! ;)

For div1 B...I tested the case#3 on my PC and the answer is correct,but the result is different on CF..

You can try comparing double numbers as fractions with equal dominators.

Div1..not Div2

When will be the tutorial published?

Can someone give me a hint on problem DIV1 C (Div2 E)

I can tell you that the answer is the sum of 1.0/depth[v] for all vertexes in graph.

Why is that correct?

The answer is the sum of probabilities of direct removal of each vertex. Let's observe that in order to remove a specific vertex from the tree, you need either to remove it directly, or to remove one of its parents. All these choices are equiprobable, and their count is depth[v], so the probability of direct removal is 1 / depth[v].

why__

"The answer is the sum of probabilities of direct removal of each vertex."andwhy" the probability of direct removal is 1 / depth[v] but not 1/nit is explained here.

If that is correct, then the answer to example #2 should be 1+1/2+1/3=11/6 instead of 2, right??

Edit: Forget it, I see my mistake now

Using mathematical induction, suppose, that it is valid for some graph, ExpMoves = Sum{1/deep[i]}. Let add a leaf with deep V. The added leaf can be choosed with 1/V prob. So in case of 1/V prob the answer is ExpMoves + 1. And in case of (V-1)/V prob the answer remains ExpMoves. So, expected moves after adding a leaf: ExpMoves' = ExpMoves * (V-1) / V + (ExpMoves + 1) / V = ExpMoves + 1/V.

How to solve E(Sequence Transformation)? I think I have found an O(n^2) dp solution,but got TLE on test case 8,how to opatimization

http://codeforces.com/blog/entry/6952

I'll tell you the method in detail, but you need tell me how to solve this .. ( ⊙ o ⊙ )

http://www.spoj.pl/problems/NOTOKNOT/

———————————————— Generally .. There are 2 different ways to solve this problem so far... One is use a datastrcuture to maintain the derivative function ... Another way is doing a dp algorithm base on a prove.