the story of a tree hackerrank solution error
Found this problem in hackerrank and have failed to pass some testcases.
One day Bob drew a tree, with n nodes and n-1 edges on a piece of paper. He soon discovered that parent of a node depends on the root of the tree. The following images shows an example of that:
Learning the fact, Bob invented an exciting new game and decided to play it with Alice. The rules of the game is described below:
Bob picks a random node to be the tree's root and keeps the identity of the chosen node a secret from Alice. Each node has an equal probability of being picked as the root.
Alice then makes a list of g guesses, where each guess is in the form u v and means Alice guesses that parent(v) = u is true. It's guaranteed that an undirected edge connecting u and v exists in the tree. For each correct guess, Alice earns one point. Alice wins the game if she earns at least k points (i.e., at least k of her guesses were true).
Alice and Bob play q games. Given the tree, Alice's guesses, and the value of k for each game, find the probability that Alice will win the game and print it on a new line as a reduced fraction in the format p/q.
Solution: There is a tree with some edges marked with arrows. For every vertex in a tree you have to count how many arrows point towards it.For one fixed vertex this may be done via one DFS. Every arrow that was traversed during DFS in direction opposite to its own adds 1.If you know the answer for vertex v, you can compute the answer for vertex u adjacent to v in O(1). It's almost the same as for v, but if there are arrows u->v or v->u, their contributions are reversed.Now you can make the vertex u crawl over the whole graph by moving to adjacent vertices in the second DFS.
Problem: It is not able to pass all the test cases. I did sanity testing of the code and found no problem but I am not getting any clue why this is not working in hackerrank platform.
import sys
def gcd(a, b):
if not b:
return a
return gcd(b, a%b)
def dfs1(m, guess, root, seen):
'''keep 1 node as root and calculate how many arrows are pointing towards it'''
count = 0
for i in m[root]:
if seen[i][root] != 1 and seen[root][i] != 1:
seen[i][root] = 1
seen[root][i] = 1
count += (1 if guess[root][i] == 1 else 0) + dfs1(m, guess, i, seen)
return count
def dfs2(m, guess, root, seen, cost, k):
'''now make every node as root and calculate how many nodes
are pointed towards it; If u is the root node for which
dfs1 calculated n (number of arrows pointed towards the root)
then for v (adjacent node of u), it would be n-1 as v is the
made the parent now in this step (only if there is a guess, if
there is no guess then it would be not changed)'''
win = cost >= k
for i in m[root]:
if seen[i][root] != 1 and seen[root][i] != 1:
seen[i][root] = 1
seen[root][i] = 1
win += dfs2(m, guess, i, seen, cost - (1 if guess[root][i] == 1 else -guess[i][root]), k)
return win
q = int(raw_input().strip())
for a0 in xrange(q):
n = int(raw_input().strip())
m = {}
guess = [[0 for i in range(n+1)] for i in range(n+1)]
seen = [[0 for i in range(n+1)] for i in range(n+1)]
for a1 in xrange(n-1):
u,v = raw_input().strip().split(' ')
u,v = [int(u),int(v)]
if u not in m:
m[u] = []
m[u].append(v)
if v not in m:
m[v] = []
m[v].append(u)
g,k = raw_input().strip().split(' ')
g,k = [int(g),int(k)]
for a1 in xrange(g):
u,v = raw_input().strip().split(' ')
u,v = [int(u),int(v)]
guess[u][v] = 1
cost = dfs1(m, guess, 1, seen)
seen = [[0 for i in range(n+1)] for i in range(n+1)]
win = dfs2(m, guess, 1, seen, cost, k)
g = gcd(win, n)
print("{0}/{1}".format(win/g, n/g))
One possibility is that the code is correct but you are getting a stack overflow.
There can be 100,000 nodes and if these are all connected in a line your depth first search recursion will fail.
If this is true, then converting the DFS code from a recursive to an iterative formulation (by keeping a stack of things to try in an array) should help.
Another possibility is that there could be a guess such as 1,2 and a guess such as 2,1. In this case I am not sure that the score updating code would work:
win += dfs2(m, guess, i, seen, cost - (1 if guess[root][i] == 1 else -guess[i][root]), k)
perhaps this would work better:
win += dfs2(m, guess, i, seen, cost - guess[root][i] + guess[i][root], k)