Hello guys!

This is a link to the question from the recent Codeforces Round 428. My solution kept on failing on Pretest #5. Can anyone explain me the correct solution pls.

Thanks

This actually occured because we calculated wrong expected value. Perhaps you tried the Total_Distance/Number_of_leaves formula here. I guess this image should clear it-

(PS: Even i got it wrong during the contest XD)

There, since you wanted a code for reference-

I didnt use the approach said in editorial, as i think there is this alternate, easy way out.

Just modify dfs a bit. We are already calculating path length (which is the level/depth, whatever you prefer to call). All we now need us the probability that journey ends there. At every node u, the chance that 1 of its children are chosen is 1/(arr[u].size -1) . This is because, lets say that the node has X children. Then arr[u].size should be X+1 due to an edge connecting the node to its parent (where the horse will not go- we need to exclude this edge, hence size-1).

THIS FORMULA NEEDS A BIT MODIFICATION TO WORK FOR NODE 1. Since node 1 has no parent, we manually add 1 to above formula if u=1.

Now at every node,we have the distance, and probability. So its just a simple multiplication to get AC.

(PS: Make sure you use setprecision and fixed in this method, chances are, your answer MIGHT get rounded off while printing.)

From Wikipedia,

*Let X be a random variable with a finite number of outcomes x_1, x_2, ..., x_k occurring with probabilities p_1, p_2, ..., p_k, respectively. The expectation of X is defined as*

For the given problem, the horse will always stop at some leaf of the tree if the starting vertex 1 is considered the root. This is because the horse keeps on moving to new vertices until it cannot, which only happens at a leaf vertex. The â€śoutcomesâ€ť here are the distances to the leaves. And because it is a tree, there is always just one path from the root to each leaf. So one can easily compute both the distance to a leaf x_i and the probability of ending up at that leaf p_i by traversing from the root to the leaf.

You can apply a simple dfs here like

function dfs(u, dist, prob): if u is leaf: return dist * prob sum = 0 for each child v of u: sum = sum + dfs(v, dist+1, prob/(number of children of u)) return sum

â€¦ and call it with `dfs(1, 0, 1.0)`

to get the answer.

Regret taking Prob Stats lite in my sem XD. Actually no, that subject was hell

Ohh so u too got the pretest 5 failed?

Thanks for the helpâ€¦I got WA due to what u pointed out xD

Yeah, this was the most common error. Cant believe over 2k people did this correctly. My mathsâ€¦;_;

@vijju123 why are we calculating for each node the probability if we know that we are going to end on a leaf only. Probability to end journey at a node which has atleast one child should be 0. Because journey can never end there .Right? Please Help.

EDIT Oh got it because we have to find probability thatâ€™s why number of child at each node matters.

Nice explanation

Btw whatâ€™s that value if it is not the expected value in the second method(which was wrong). I mean what is the explanation of that value (in terms of probability).

You can call it â€śaverage valueâ€ť This value would be the answer if the question stated that â€śProbability of journey ending on any of the leaf is equalâ€ť. In actual case, this probability was unequal (probability of journey ending on some leaves is more than others) and this is the reason for deviation of answer.

I also tried Total_Distance/Number_of_leaves formula during the contest but fortunately in the contest itself I realised my mistake and was able to get an AC

Haha great @naksh9619! Wish I could test my solution on many cases and figure out my mistake ;_;