Hmmm. I think my idea is appropriate with my thinking flow and the found solution is not hard to implement. Btw, could you tell me more in details about your idea?

yaswanth Sure.

I will tell you my idea, but I didn't implement it yet.

We need to sum the variances where a variance of a sequence S = s1, s2, ..., sn = VAR(X) = E[(si)^2] — E^2[si].

So if we have k sequences S1, S2, S3, ... , Sk

The answer will be = ( ∑ (E[Sij^2] — E^2[Sij]) ) / k = (∑ E[Sij^2] — ∑ E^2[Sij]) / k So we need to know four things :

1- To Know all the Sequences we can make.

2- How to compute E[X] for a Sequence.

3- How to compute E[X ^ 2] for a Sequence.

4- The number of Sequences K.

Ok, Let's Sort the Array and call it A. Now for every A[i], Consider all the Sequences that ends with A[i]. Get the smallest j where j <= i and A[i] — A[j] <= R (The index of the smallest element we can include in a set where A[i] is in) and Call that index Left, and call our index i (Right). So know we want to get ∑E[X] for all the sequences that ends with Right, ∑E[X ^ 2] for all the sequences that ends with Right, number of Sequences K that ends with Right.

If we got these 3 things then the problem is solved.

So I will tell you how to compute The total number of sequences K, ∑E[X] for all sequences that ends with Right and you should be able to continue from there.

So now we fixed Right and for sure any element between indices : [Left, Right — 1] may be included in our sequence and may not, so the total number of sequences here are :

K = 2 ^ ( (Right — 1) — Left + 1).

now I will tell you how to compute E[X] for this sequence S = s1, s2, ..., sm.

for sure s1 < s2 < s3 < ... < sm

You can solve it using dynamic programming. The state would be (curIdx, endIdx, left).

curIdx it the idx of the element you are deciding currently to take it or not (for sure you will add both ways to the answer).

endIdx is the last element you can take.

left is the # of remaining numbers you need to take.

Now what is E[x] for this Sequence S = s1, s2, s3, ... , sm (∑ (i : 0 -> m)) dp(1, m, i).

Which means that I will try to include 0, 1, 2, 3, ..., m Elements from this array.

BTW by S I mean the elements from Left to Right — 1.

I can prove an bound on the number of states.

Handle the case when the sum of either array is 0 separately.

Let S be the sum of first array and T be the sum of second. Note that the operation multiplies the sum by 2 on each step, so we must end in at most steps.

Now, for each step, we can have at most n distinct states. To see why, we note that the set of values we obtain will be the same no matter whether we use L or R. In fact, the states of each level are only cyclic shifts of each other. Thus, there are at most n states per level.

This proves the bound.

the operation is commutative anyways so the number of distinct states visited will be very less.

If we look at sequence a₀, a₁, ..., a_n - 1 as a polynomial a₀x⁰ + a₁x¹ + ... + a_n - 1x^n - 1, then operations are just multiplication by 1 + x and 1 + x^n - 1 modulo xⁿ - 1, so they commute. Because of that there will be only 100 + 99 + ... + 0 states (only number of operations of each type matters, not their order) at most and actually much less.

UPD. Fixed an error. Thanks to Swistakk.

Oh I didn't thought about memoization... I said that because I hacked two codes without memoization.

And yes there are at most 2000 states. This is because LR is equivalent to RL. so just like bubble sort, you can transform the sequence as LLLLL...RRRRR.... and get same results. (actually this observation results in short O(lg(n*ai)^3) solution)

I'm using BigDecimal, but looks like Petr didn't use it and still can produce correct result. (The key is divide number of subtrees for each term, instead of divide it in the end). (Edit: No, tried and this can't work)

My solution writes each term of the sums as Integer + Float, where 0 <= Float < 1, then sums them by 'components', as in all Integers are summed into a __int128, while all Floats into a double. Since the Floats are of form a/b for b <= 50^2 I assumed it would be enough to get high enough precision :\

Yes, basically when we do subtraction of two big numbers, the relative error can be huge. (Even we try the case where all weights are 10^9, we will output something much larger than 0).

Somehow when I did the analysis I thought we are just adding O(n^2) numbers and that should be fine. And I didn't test it thoroughly.

Btw, seems reducing weights to 1000 should be enough for avoid precision error.

There will be another problem: suppose that we have to compute it modulo p = 1e9+7, then the number of trees coulde be equal to p. In that case if the numerator of our huge fraction is also divisible by p, then we should know this numerator mod p^2... I guess bignums are needed in that case.

Another problem is that debugging can be harder. For example everyone knows 0.4 is 2/5, but it takes some time to understand that 800000006 is 2/5.

And I don't understand the authors not proving precision in their double solutions.

The 1e-9 comes by default — so if we want to override it into 1e-6 we need to write checkAnswer(), and when we don't think that is necessary we use 1e-9.

Btw even we change the precision to 1.0 lots of solution will still fail.

Wow, I thought about this solution and suggested 900 to be too easy.) What's the problem with knapsack?

No idea but my solution originally failed in the contest. After some time debugging, I took care of overflow, and AC. I was failing on {1,0} {0,0}.

If someone can explain how, it would be very interesting. I originally thought the probability was very low so didn't handle it. ( << so stupid).