Hello Fellas ,
I am trying to solve this problem from Quora Hackathon but not able to come up with a idea .. how to appraoch it ?
Can any one help ..
Just for the convenience i have copied the problem statement here otherwise you can use this link
Problem Statement
For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes Ti time to read. There exists exactly one path from any question to another, and related questions form undirected pairs between themselves. In other words, the graph of related questions is a tree.
Each time Steve reads a question, he will see a list of related questions and navigate to one that he hasn't read yet at random. Steve will stop reading once there are no unread related questions.
Which question should we show first to Steve so that we minimize his total expected reading time? It is guaranteed that there is one unique question that is optimal.
Input Format
Line 1: A single integer, N
Line 2: N integers, Ti
Line 3...N+1: Each line contains two integers A, B indicating that question A and B are
related
Output Format
Line 1: A single integer, X, the best question to show first.
Constraints
1≤N≤105
1≤Ti≤106
Sample Input
5
2 2 1 2 2
1 2
2 3
3 4
4 5
Sample Output
3
This question was already asked few weeks ago, here is that post.
I am unable to understand your approach . Can you be more clear .. Please
As you said that this is standard DP problem there must be some more problems based on the similar comcept. So , can you provide links for those problems too .
Maybe my solution from a contest will help you — here it is. Sorry, it looks a bit messy, like almost all my solutions :) But I hope it will help you.
Problem based on the similar concept — Long Drive from recent CodeChef contest. There are lot of possible ways to solve this one, but you can try similar DP on a tree. First of all for every vertex you can find length of longest path going down from this vertex in a single run of dfs. Then run another dfs to find longest path going up — it will be either path going to a parent and then up (and you should already have an answer for moving up from a parent) or path going to a parent and then down into one of subtees (and answers for this case you already got while solving moving down only part).
In your problem from Hackathon we have to deal with a bit more complicated formulas for calculating probabilities, but general idea is same.
Hey you are right.
I knew this idea even i was able to solve long drive during the contest itself but not this one from Quora Hackathon with the similar approach. I coded the same way as you suggested but i got WA for all the cases except some test cases .
Thank you so much ..
Finally I got the idea .
Thanks for sharing your code . Yeah .. It was messy but it helped me a lot ..
once again thanx .
Hey i got AC with the solution described above . Tell me the use of rand()%N+1 in your code . It has something really interesting .
Well, it is a common trick while solving/debugging/testing some problems with a tree — to change a root of a tree; for this problem — change root of a tree, and if it will change received answer — then I have a bad news for you.
And at original contest my code with a bug was failing either 1 or 2 cases, depending on number of vertex choosen as a root)
By the way, has anyone received e-mail from hackerrank "Quora is interested in talking to you" after this hackathon?
Check my comment