Sort by

recency

|

14 Discussions

|

  • + 0 comments

    PyPy 3 solution

    from collections import defaultdict, deque
    import sys
    
    def read():
        return (int(s) for s in sys.stdin.readline().split())
    
    N, Q = read()
    adj_matrix = defaultdict(list)
    for _ in range(N - 1):
        x, y = read()
        adj_matrix[x].append(y)
        adj_matrix[y].append(x)
    segment_size = 120
    parents = [None] * N
    s_parent = [None] * N
    s_weight = [0] * N
    levels = [0] * N
    update = [-1] * N
    refresh = [-1] * N
    weight = [0] * N
    def refresh_segment(node, sp, tick):
        if node == sp or refresh[node] >= update[sp]:
            return
        parent = parents[node]
        if parent == sp:
            s_weight[node] = weight[parent]
        else:
            refresh_segment(parent, sp, tick)
            s_weight[node] = s_weight[parent] + weight[parent]
        refresh[node] = tick
    
    # Initialize above with BFS, que is (segment parent, parent, node, level)
    que = deque([(0, 0, 0, 0)])
    while que:
        segment, parent, node, level = que.popleft()
        s_parent[node] = segment
        parents[node] = parent
        levels[node] = level
        child_segment = segment if level % segment_size else node
        for n in adj_matrix[node]:
            if n != parent:
                que.append((child_segment, node, n, level + 1))
    results = []
    for i in range(Q):
        op, u, x = read()
        if op == 1:
            weight[u] = x
            if levels[u] % segment_size:
                update[s_parent[u]] = i
            else:
                update[u] = i
        else:
            if levels[u] > levels[x]:
                u, x = x, u
            result = weight[x] + weight[u]
            # Traverse x upwards segment by segment until
            # levels[segments[x]] == levels[segments[u]]
            u_s = s_parent[u]
            while levels[s_parent[x]] > levels[u_s]:
                refresh_segment(x, s_parent[x], i)
                result += s_weight[x]
                x = s_parent[x]
            while s_parent[x] != s_parent[u]:
                refresh_segment(x, s_parent[x], i)
                refresh_segment(u, s_parent[u], i)
                result += s_weight[x]
                result += s_weight[u]
                x = s_parent[x]
                u = s_parent[u]
            for _ in range(levels[x] - levels[u]):
                x = parents[x]
                result += weight[x]
            while u != x:
                x = parents[x]
                u = parents[u]
                result += weight[x]
                result += weight[u]
            result -= weight[x]
            results.append(result)
    print('\n'.join(str(x) for x in results))
    
  • + 0 comments

    here is hackerrank lazy white falcon solution

  • + 1 comment

    Hello. Please can anyone help me with this problem? I'm getting a timeout for the testcase with 100000 queries. I suspect the problem is from my algorithm to calculate the sum. The code is below:

    int sumPath(Node* x, Node* y) {
        int sum = 0;
        // while x is on a level below y, ascend while adding the values to sum
        while (x->level > y->level) {
            sum += x->data;
            x = x->parent;
        }
        // while y is on a level below x, ascend while adding the values to sum
        while (y->level > x->level) {
            sum += y->data;
            y = y->parent;
        }
        //x and y are on the same level now.
        //ascend while their parents are not equal and add values to sum
        while (x != y) {
            sum += y->data;
            sum += x->data;
            x = x->parent;
            y = y->parent;
        }
        //x and y must be pointing to the same node now which is the lowest common anscestor.
        //Add the node's value to sum.
        return sum + x->data;
    }
    

    Is there a better way to implement it?

  • + 1 comment

    Finally AC with HLD with Segment Trees ;)

  • + 2 comments

    Quite a tedious problem. The catch is in the fact that the tree may be very unbalanced, so you cannot directly “walk” the tree to aggregate.

    Don't know if there is an official name for the summarized tree representation, but I'm reasonably proud that invented it independently:

    First modification we make is node set operation has to be expressed in terms of node increment operation (just remember the last value independently)

    Then we come to the concept of aggregate tree representation where each child node has a summary of all parents up to the root. That way the answer is L + R - LCA(L,R)

    We will get such aggregate tree if every node increment operation will be performed as entire subtree increment.

    Here is how to perform all children increment efficiently:

    The strategy lies in the DFS tree representation, where all children lay sequentially. That way updates turn into interval increment commands which we can perform using Fenwick or segment tree with O(logN) update and O(logN) to summarize.

    Lowest common ancestor (LCA) routine has to be accelerated too. That part is relatively straightforward, just have pointers to 1, 2, 4, 8, 16th, etc parent above in each node to perform ascend operation in O(logN). Then use a binary search to find LCA in O(logN * logN).