Can someone tell me how to solve this problem ALIENINV
Thanks!
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Name |
---|
When you ask for help with a problem, say what you already came up with (more instructions here).
A good first step might be to compute the answer for every leaf. Take a leaf $$$L$$$ and root the tree there. For every other vertex $$$V$$$, it will be removed before $$$L$$$ if and only if the whole subtree of $$$V$$$ has values smaller than the value in $$$L$$$. Let $$$s[V]$$$ be the size of the subtree of $$$V$$$. Then, we want $$$L$$$ to have the smallest value among $$$s[V]+1$$$ vertices (that subtree and vertex $$$L$$$ itself), so the probability of $$$L$$$ being the smallest is $$$\frac{1}{s[V]+1}$$$. Since this is the probability of $$$V$$$ being before $$$L$$$, you can sum this up to get the expected value of the place of $$$L$$$ — because with that probability the place of $$$L$$$ is increased by $$$1$$$.
This is $$$O(N)$$$ solution to find an answer for a single leaf. I don't know how hard it is to apply it for non-leaf vertices. Try it and let us know.
Thanks a lot for your help. I'll keep in mind about the instructions next time. And do you mean $$$L$$$ should have the largest value than the whole subtree of $$$V$$$? or am I missing something?
Thanks!
Yup, the largest.