[백준] 1005번: ACM Craft

https://www.acmicpc.net/problem/1005

initial

It is reaching node x so initially I thought BFS. Close but it is topological sort but with DP memoisation. Dafuq? let's see

solution

This question requires full exploration of nodes at same indegree level (i.e. max cost at same indegree). For example, 1-2 1-3 2-4 3-4 and if cost of each node is [10,1,100,10], answer is 120 not 21 like BFS. In order to solve this, we make a dp cost list. As we traverse from current node to next connected node, we compare 1) dp recorded cost of next connected node 2) dp recorded cost of current node + cost of next node. This is because we want the biggest cost value for a given node. We can express it like

## cost is dp list 
cost[i] = max(cost[i], cost[cur]+lst[i])

DP's memoization is used to find the cumulative cost up to the target point .

From the starting point where topological alignment begins, the value is accumulated at the moving vertex, but recorded only if it is greater than the accumulated value at the corresponding vertex.

correct sol:

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n,k = map(int,input().split())
    lst = [0] + list(map(int,input().split()))
    graph = defaultdict(list)
    indegree = [0 for _ in range(n+1)]

    for _ in range(k):
        a,b = map(int,input().split())
        graph[a].append(b)
        indegree[b]+=1

    x = int(input())

    def topo_sort():
        queue = deque()
        ans = []
        cost = [0 for _ in range(n+1)]
        for i in range(1,n+1):
            if indegree[i]==0:
                queue.append(i)
                cost[i] = lst[i]
        while queue:
            cur = queue.popleft()
            if cur == x:
                print(cost[x])
                break
            for i in graph[cur]:
                indegree[i]-=1
                cost[i] = max(cost[i], cost[cur]+lst[i])
                if indegree[i]==0:
                    queue.append(i)
    topo_sort()

revisited feb 27th 24

So this is harder than just reusing topo sort template. Since we are given the final node that we wanna reach, we can utilise DP memoisation to record the MAX cost value to reach a node in 1d DP list. Well explained in intial section.

i couldnt think of dp memo but I thought of a way where when we get some nodes which indegree is 0, I get the maximum cost out of all those nodes and accumulate add that to my answer variable. But i dont think this wil lead to right cases

complexity

time

The provided code appears to solve a problem using topological sorting on a directed acyclic graph (DAG). Here's an analysis of its time complexity:

1. Parsing Input:

   • Parsing the input values takes O(1) time for each test case because the number of operations performed is constant for each test case.

2. Creating the Graph:

   • The code constructs a directed graph (graph) using a defaultdict and computes the in-degrees (indegree) of each node. Constructing the graph takes O(k) time, where k is the number of edges.

3. Topological Sorting:

   • The topological sorting algorithm used in the topo_sort function operates using a deque (queue) and iterates through the nodes in the graph.
   • In the worst case, the while loop runs for all n nodes in the graph.
   • For each node, it processes its outgoing edges, which takes constant time per edge.
   • Therefore, the overall time complexity of topological sorting is O(n + k), where n is the number of nodes and k is the number of edges in the graph.

4. Printing the Result:

   • Printing the result, which is the cost of reaching node x, takes O(1) time.

5. Overall Complexity:

   • The dominant factor in the time complexity is the topological sorting step, which is O(n + k).

So, the overall time complexity of the code is O(n + k), where n is the number of nodes in the graph, and k is the number of edges. This is the time complexity for each test case, and if you have multiple test cases (as indicated by the variable t), the total time complexity would be O(t * (n + k)), where t is the number of test cases.

space

Let's analyze the space complexity of the provided code:

1. Input Storage:

   • The code stores the input values, including t, n, k, lst, graph, indegree, and x, in various data structures. These data structures use space proportional to the size of the input.
   • The space used for input storage is O(n) for each test case because it stores lists with up to n elements, where n is the number of nodes in the graph.

2. Graph Data Structures:

   • The graph variable is a defaultdict of lists. It stores the adjacency list representation of the graph. The space it consumes depends on the number of edges (k) and nodes (n) in the graph.
   • The indegree list stores the in-degrees of each node, which requires space for n integers.

3. Additional Data Structures:

   • The queue in the topo_sort function stores nodes during the topological sorting process. In the worst case, it can store all n nodes, so it requires O(n) space.
   • The cost list stores the cost associated with each node, using space for n integers.

4. Output:

   • The code prints the result, which is the cost of reaching node x. Printing results typically doesn't contribute significantly to space complexity.

5. Overall Space Complexity:

   • The space complexity is primarily determined by the data structures used for the graph (adjacency list and in-degrees) and the auxiliary data structures for topological sorting (queue and cost list).
   • Therefore, the overall space complexity is O(n + k).

Keep in mind that this analysis assumes that the input size is the dominant factor in space usage. If there are additional factors not considered in this analysis (e.g., large constant factors or additional memory usage within the functions), the space complexity may need to be adjusted accordingly.