die Geschichte eines Baumes hackerrank Lösung Fehler

Question

Found this problem in hackerrank und gescheitert sind einige Testfälle passieren.

Einen Tag zog Bob einen Baum, mit n Knoten und n-1 Kanten auf einem Stück Papier. Er entdeckte bald, dass Eltern eines Knotens von der Wurzel des Baumes abhängen. Die folgenden Bilder zeigen ein Beispiel, dass:

die Tatsache, Lernen, erfand Bob ein aufregendes neues Spiel und beschlossen, es mit Alice zu spielen. Die Regeln des Spiels wird im Folgenden beschrieben:

1. Bob wählt einen Zufallsknoten des Baumes Wurzel und hält die Identität des gewählten Knoten ein Geheimnis von Alice zu sein. Jeder Knoten hat die gleiche Wahrscheinlichkeit, als Wurzel ausgewählt zu werden.

2. Alice macht dann eine Liste von g Vermutungen, wobei jede Vermutung in der Form ist u v und Mittel Alice vermutet, dass parent (v) = u wahr ist. Es ist garantiert, dass eine ungerichtete Kante, die u und v verbindet, im Baum existiert. Für jede richtige Schätzung verdient Alice einen Punkt. Alice gewinnt das Spiel, wenn sie mindestens k Punkte verdient (das heißt mindestens k ihrer Vermutungen wahr).

Alice und Bob q Spiele spielen. Gegeben der Baum, Alice Vermutungen und der Wert von k für jedes Spiel, finden Sie die Wahrscheinlichkeit, dass Alice das Spiel gewinnen wird und es auf einer neuen Zeile als ein reduzierter Bruch im Format p/q drucken.

Lösung: Es ist ein Baum mit ein paar Kanten mit Pfeilen markiert. Für jeden Knoten in einem Baum muss gezählt werden, wie viele Pfeile darauf zeigen. Bei einem festen Knoten kann dies über ein DFS geschehen. Jeder Pfeil, der während des DFS in entgegengesetzter Richtung durchlaufen wurde, fügt 1 hinzu. Wenn Sie die Antwort für den Knoten v kennen, können Sie die Antwort für den Knoten u neben v in O (1) berechnen. Es ist fast das gleiche wie für v, aber wenn die Pfeile u-> v oder v-> u sind, sind ihre Beiträge umgekehrt. Jetzt können Sie den Knoten über den gesamten Graphen kriechen lassen, indem Sie zu benachbarten Eckpunkten im zweiten DFS gehen .

Problem: Es ist nicht in der Lage, alle Testfälle zu bestehen. Ich habe den Code getestet und kein Problem gefunden, aber ich habe keine Ahnung, warum das nicht in der hackerrank-Plattform funktioniert.

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)) 

Answer 1

Eine Möglichkeit ist, dass der Code korrekt ist, aber Sie erhalten einen Stapelüberlauf.

kann es 100.000 Knoten sein, und wenn diese alle in einer Linie Ihre Tiefensuche Rekursion nicht verbunden sind.

Wenn dies wahr ist, dann auf eine iterative Formulierung den DFS-Code aus einem rekursiven Umwandlung (durch einen Stapel der Dinge zu halten in einem Array versuchen) soll helfen.

Eine andere Möglichkeit ist, dass es so eine Vermutung, wie 1,2 und eine Vermutung als 2,1 sein könnte.In diesem Fall bin ich, dass die Partitur Aktualisierung Code funktionieren würde, nicht sicher: vielleicht

win += dfs2(m, guess, i, seen, cost - (1 if guess[root][i] == 1 else -guess[i][root]), k) 

dies besser funktionieren würde:

win += dfs2(m, guess, i, seen, cost - guess[root][i] + guess[i][root], k)