Google Kickstart Truck Delivery Partially Correct Answer-CodePudding

I was trying to solve the Truck Delivery problem from Google Kick Start 2021 Round B (4th Question) and I came across a problem with my code that I can't figure out;

import sys
import math

sys.stdin = open('input.txt', 'r')


def solve(index):
    if index == 0 :
        return
    else:
        for j in range(len(roads)):
            if roads[j][0] == index:
                if roads[j][2] <= w:
                    fines.append(roads[j][3])
                    solve(roads[j][1])


T = int(input())
for case in range(1, T 1):
    n, q = [int(x) for x in input().split(" ")]
    roads = []

    for rd in range(n-1):
        road = [int(x) for x in input().split(" ")]

        if road[0] < road[1]:
            temp = road[1]
            roads.append([road[1], road[0], road[2], road[3]])
        else:
            roads.append(road)
    roads.sort(reverse=True)

    result = ""
    for query in range(q):
        c, w = [int(x) for x in input().split(" ")]
        fines = []
        solve(c)

        if len(fines) != 0:
            result  = str(math.gcd(*fines))   " "
        else:
            result  = "0 "

    print("Case #{}: {}".format(case, result))

And I get a partially correct answer from the sample case, my output is;

Case #1: 1 0 0 5 7 
Case #2: 0 5

The correct output should be;

Case #1: 1 4 0 5 7
Case #2: 10 5

For some reason my recursion doesn't append the fine in case 1 day 1 and case 2 day 0. Can you guys spot the problem? Also feel free to inform me with the bad practices in my code etc. PS: I am not looking for the best answer to this question, I am just trying to solve it on my own

CodePudding user response：

The cause for failing those two test cases is that your solve code exits recursion as soon as it finds a road where no toll has to be paid. But this is not right: the rest of the path to city #1 may still have other roads that will incur a toll.

So move the recursive call out of the if block, like this:

            if roads[j][2] <= w:
                fines.append(roads[j][3])
            solve(roads[j][1])

Although this will solve the issue you bumped into, there are more problems ahead:

Your algorithm assumes that the path from a city k to city #1 will always go from a city with a greater number to a city with a lesser number. Although this is the case with the 2 sample test cases, this is not guaranteed. It might well be that the path would run from city 20 to city 80 and then to city 1.

To resolve that problem, you'll have to change your approach. I would suggest to create a list where the index is a city number and the value is a tuple (parent, maxweight, toll), such that parent is the city's parent node when the tree is rooted with as root node city #1.

In order to make that list, I would suggest first creating an adjacency list, then run through that graph in a depth-first traversal starting at city 1. During that traversal you can register which are the "upward" edges towards the root, and create that data-structure described in the previous paragraph.

Here is some (untested) code:

def solve(parent, city, weight):
    fines = []
    while city > 1:
        if weight >= parent[city][1]:
            fines.append(parent[city][2])
        city = parent[city][0]
    return math.gcd(*fines) if fines else 0


def buildtree(roads):
    # Adjacency list:
    adj = [[] for _ in range(n   1)]  # index is city number (1 .. N).  
    for city1, city2, maxweight, toll in roads:
        # Add road in both directions to adjacency list
        adj[city1].append((city2, maxweight, toll))
        adj[city2].append((city1, maxweight, toll))

    # Each node has only one parent in a rooted tree. 
    #   Find that parent for each node, when node #1 is the root:     
    visited = [False] * (n   1)
    parent = [None] * (n   1)

    def recur(city):
        visited[city] = True
        for nextcity, maxweight, toll in adj[city]:
            if not visited[nextcity]:
                parent[nextcity] = (city, maxweight, toll)
                recur(nextcity)

    recur(1)  # build `parent` data structure
    return parent


sys.stdin = open('input.txt', 'r')
numcases = int(input())
for case in range(1, numcases   1):
    numcities, numqueries = [int(x) for x in input().split(" ")]
    
    roads = [
        [int(x) for x in input().split(" ")]
        for road in range(numcities - 1)
    ]
    queries = [
        [int(x) for x in input().split(" ")]
        for query in range(numqueries)
    ]

    parent = buildtree(roads)

    result = " ".join(
        str(solve(parent, city, weight)) for city, weight in queries
    )

    print("Case #{}: {}".format(case, result))