You are not logged in. Please login at www.codechef.com to post your questions!

×

Codeforces problem C

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

asked 13 Aug, 00:31

dishant_18's gravatar image

4★dishant_18
47218
accept rate: 7%


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.

link

answered 13 Aug, 01:20

meooow's gravatar image

5★meooow ♦
5.5k411
accept rate: 47%

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

(13 Aug, 01:24) vijju123 ♦4★

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

(13 Aug, 11:21) dishant_184★

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

(13 Aug, 11:23) dishant_184★

Thank you @meooow. It was helpful:)

(13 Aug, 23:22) vishesh_3454★

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-

http://ideone.com/QI2X14

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

link

answered 13 Aug, 01:17

vijju123's gravatar image

4★vijju123 ♦
11.4k1316
accept rate: 18%

edited 13 Aug, 11:39

Ohh so u too got the pretest 5 failed?

(13 Aug, 11:06) dishant_184★

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

(13 Aug, 11:07) dishant_184★
2

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

(13 Aug, 11:25) vijju123 ♦4★

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

(13 Aug, 22:49) vishesh_3454★

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 Aug, 23:24) vishesh_3454★

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 Aug, 00:02) vijju123 ♦4★
1

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

(14 Aug, 06:19) naksh96195★
1

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

(14 Aug, 22:49) dishant_184★
showing 5 of 8 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×967
×457

question asked: 13 Aug, 00:31

question was seen: 287 times

last updated: 14 Aug, 22:49