Can someone tell me how to solve this problem ALIENINV
Thanks!
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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.