neelshahr92's blog

Quora Haqathon : Related Questions
By neelshahr92, 9 years ago, In English

Hi

Can someone please describe the solution for the following problem which was asked in the quora haqathon 2014. Thanks in advance.

https://www.hackerrank.com/contests/quora-haqathon/challenges/relatedquestions

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Related questions is one of standard problems "given a tree, you are not allowed to walk over some edge twice, calculate something" — and it can be done with DP. In first run you solve problem in which you are not allowed to move upward on tree — this is easy one; then you run dfs once again to solve remaining part (calculating EV for going up from some vertex — you may either go up from it's parent, or go down from it's parent to some other subtree; but once you go down — you'll move to previous problem, because remaining part of path will always move down, as moving up means using some edge twice).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I first tried to form a dp using (node,parent), which was O(n^2). Then I realized, every pair of (node,parent) is simply an edge. So I decided to enumerate all edges. Since it was a tree, there were n-1 edges. Since an edge can go both ways, I had to make them directed. And finally, there was this (node,-1). That is the initial node, which has no parent. There for I had a total of 3*n edges. So my DP was O(3*n). Yet, I only got 70 points :(. Remaining test cases got TLE. What was your exact complexity?

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved it using DP on tree and some quite complicated handling inside. Complexity O(N) (Using a hashtable, with a bit of effort you can use normal arrays) http://ideone.com/pPlbTB

The total number of states is O(Edges) which is O(N). And the loop inside which calls all children will never be called more than TWICE! We use these answers and sum them up to answer future calls to this node without doing this loop.

If you loop everytime, complexity can go up to O(N^2). My first solution had TLE because of this. Feel free to ask if you are having troubles analyzing the complexity of this solution...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the code. It is very readable.

    If i understand the algo correctly then exact complexity of the algo is o(N + 2*Edges). (As the algo makes sure that each edge is traversed at most and maybe exactly twice)

    I re-coded it using the same logic to make sure i understand the algorithm. here is the link http://ideone.com/qma94w , but it does not pass all the test cases. can u help me with that? I appreciate the help, thanks.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well you are correct for your complexity analysis but this applies to my code. Your code however can go up to O(N^2). Take for example a case like this one

      What happens in this case? There are total of 2*Edges states as each edge can result in two different states. But what happens within each state? Can you see what happens each time the root vertex is called? It will iterate over ALL Edges! And all edges have one of their two states with the root as their node! So for each call to the root, it iterates over all edges and we have total of O(N) possible calls to the root so the complexity is O(N*N) which is O(N^2).

      The way to work around this which I did was little complicated but you can find it in my code or you can think of it. Think of a way to get rid of this iteration which iterates over all the node edges.

      → Reply