Codeforces problem C

general
,
1

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

1 Like
2

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-

alt text

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

2 Likes
3

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

\text{E}[X] = x_1p_1 + x_2p_2 + \cdots + x_kp_k

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.

4 Likes
4

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

5

Ohh so u too got the pretest 5 failed?

6

Thanks for the help…I got WA due to what u pointed out xD

7

Thanks for the help mate!!
Yup @vijju123 I too regret taking it litely lol :frowning:

8

It would be great if u can send a link of your code for reference @meooow

9

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

2 Likes
10

@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 :slight_smile:

11

Thank you @meooow. It was helpful:)

12

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

13

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.

14

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

1 Like
15

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

1 Like