We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Lazy White Falcon
  5. Discussions

Lazy White Falcon

Sort by

recency

|

14 Discussions

|

  • TChalla
     + 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))

  • yashpalsinghdeo1
     + 0 comments

    here is hackerrank lazy white falcon solution

  • samionex99
     + 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?

    • SaySachinYadav
       + 0 comments

      include

      include

      include

      include

      include

      using namespace std;

      const int N = 100010; const int LG_N = 20;

      vector adj[N]; int n, q;

      int tree[2*N]; vector euler; int first[N], last[N];

      int H[N], P[N][LG_N]; int val[N];

      void dfs(int u, int p, int h) { H[u] = h; P[u][0] = p; for(int i = 1;i < LG_N;i++) { P[u][i] = P[P[u][i-1]][i-1]; } first[u] = euler.size(); euler.push_back(u); for(int v : adj[u]) { if(v == p) { continue; } dfs(v, u, h+1); } last[u] = euler.size(); euler.push_back(u); } int lca(int u, int v) { if(H[u] < H[v]) swap(u, v); for(int i = LG_N-1;i >= 0;i--) { if(H[P[u][i]] >= H[v]) { u = P[u][i]; }
      } if(u == v) { return u; } for(int i = LG_N-1;i >= 0;i--) { if(P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } return P[u][0]; } void update(int idx, int val) { while(idx < euler.size()) { tree[idx] += val; idx += idx & (-idx); } } int query(int idx) { int ans = 0; while(idx > 0) { ans += tree[idx]; idx -= idx & (-idx); } return ans; } int main() {

      ios::sync_with_stdio(false);
cin >> n >> q;
for(int i = 0;i < n-1;i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

euler.resize(1, 0);
dfs(0, 0, 0);

for(int i = 0;i < q;i++) {
    int type;
    cin >> type;
    if(type == 1) {
        int u, x;
        cin >> u >> x;
        update(first[u], x - val[u]);
        update(last[u],  val[u] - x);
        val[u] = x;
    }else {
        int u, v;
        cin >> u >> v;
        int l = lca(u, v);
        int ans = query(first[u]) + query(first[v]);
        ans = ans - 2 * query(first[l]) + val[l];
        cout << ans << "\n";
    }
}
return 0;

      }

  • chickoo_1
     + 1 comment

    Finally AC with HLD with Segment Trees ;)

    • sonusingh_nitaa
       + 0 comments

      can anyone tell why this code is givin runtime error on few test cases

      import java.util.; import java.io.; class Solution{ static PrintWriter out = new PrintWriter(System.out); static int N =60000, LOGN = 20; static int n,q,ptr,chainNo; static int subSize[] = new int[N]; static int depth[] = new int[N]; static int st[] = new int[4*N]; static int chainInd[] = new int[N]; static int chainHead[] = new int[N]; static int base[] = new int[N]; static int posInBase[] = new int[N]; static int node[] = new int[N]; static int P[][] = new int[LOGN][N]; static LinkedList g[] = new LinkedList[N];

      static int LCA(int x , int y){ if(depth[x] < depth[y]){ int t =x; x=y; y=t; } int lg = 1; for(;(1<= 0 ; i--) if(depth[x] - (1<= depth[y]) x = P[i][x]; if(x == y)return x; for(int i = lg ; i >= 0 ; i--) if(P[i][x] != -1 && P[i][x] != P[i][y]){ x = P[i][x]; y = P[i][y]; } return P[0][x]; } static void build() {
      for (int i = n - 1; i > 0; --i) st[i] = st[i<<1] +st[i<<1|1]; }

      static void modify(int p, int value) { for (st[p += n] = value; p > 1; p >>= 1) st[p>>1] = st[p] + st[p^1]; }

      static int query(int l, int r) { // max on interval [l, r) int res = 0 ; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if ((l&1)==1) res = res+st[l++]; if ((r&1)==1) res = res+st[--r]; } return res; } static void dfs(int a,int p,int level){ depth[a]=level; subSize[a]=1; P[0][a]=p; for(Integer I : g[a]) if(I!=p){ dfs(I,a,level+1); subSize[a]+=subSize[I]; } }

      static int query_up(int u,int v){

      int uchain,vchain=chainInd[v],ret=0; while(1>0){ uchain=chainInd[u]; if(uchain==vchain){ ret=ret+query(posInBase[v],posInBase[u]+1); break; } else{ ret=ret+query(posInBase[chainHead[uchain]],posInBase[u]+1);
      u=P[0][chainHead[uchain]]; } } return ret; }

      static void update(int node , int val) { int pos = posInBase[node]; modify( pos,val); }

      static void hld(int curNode,int p){ if(chainHead[chainNo]==-1) chainHead[chainNo]=curNode;

      chainInd[curNode]=chainNo;
posInBase[curNode]=ptr;
node[posInBase[curNode]]=curNode;
base[ptr++]=0;

int sc=-1;
for(Integer I : g[curNode])
    if(I!=p){
       if(sc==-1 || (sc!=-1 && subSize[sc]<subSize[I]))
            sc= I;
     }
if(sc!=-1)
    hld(sc,curNode);
  for(Integer I : g[curNode])
    if(I!=p&&I!=sc){
           chainNo++;
            hld(I,curNode);
     }

      }

      public static void main(String[] args){ Arrays.fill(chainHead , -1); n = ni(); q = ni(); int value[] = new int[n]; // st = new int[2*n]; for(int i=0;i for(int i=1;i<=q;i++) { int type = ni(); if(type == 1) { int u = ni(); int x = ni(); value[u]=x; update(u , x); } else { int u = ni(); int v = ni(); int lca = LCA(u,v); int ans = query_up(u,lca) + query_up(v,lca)-value[lca]; System.out.println(ans); } } // out.flush(); } static FastReader sc=new FastReader(); 

        static int ni(){
             int x = sc.nextInt();
             return(x);
    }
  static long nl(){
          long x = sc.nextLong();
          return(x);
     }
  static String n(){
             String str = sc.next();
                 return(str);
   }
 static String ns(){
             String str = sc.nextLine();
               return(str);
  }
 static double nd(){
           double d = sc.nextDouble();
             return(d);
   }

      static class FastReader { BufferedReader br; StringTokenizer st; 

          public FastReader() 
    { 
        br = new BufferedReader(new
                 InputStreamReader(System.in)); 
    } 

    String next() 
    { 
        while (st == null || !st.hasMoreElements()) 
        { 
            try
            { 
                st = new StringTokenizer(br.readLine()); 
            } 
            catch (IOException  e) 
            { 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 

    int nextInt() 
    { 
        return Integer.parseInt(next()); 
    } 

    long nextLong() 
    { 
        return Long.parseLong(next()); 
    } 

    double nextDouble() 
    { 
        return Double.parseDouble(next()); 
    } 

    String nextLine() 
    { 
        String str = ""; 
        try
        { 
            str = br.readLine(); 
        } 
        catch (IOException e) 
        { 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}

      }

  • d_kokarev
     + 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).

    • yashpalsinghdeo1
       + 0 comments

      here is problem solution in python java c++ and c programming. https://programs.programmingoneonone.com/2021/05/hackerrank-lazy-white-falcon-problem-solution.html

    • chibby0ne
       + 0 comments

      Hey @d_kokarev thanks for the input. I've looked at Fenwick trees and seem like the way to go. But I still have a hard time between the mapping of the Tree/Graph nodes, and the Fenwick tree indexes.

      The strategy lies in the DFS tree representation, where all children lay sequentially

      I assume you refer here to the array so called "edgeTo" which contains the information encoded after a DFS or BFS is done in a Tree/Graph of the connections between the nodes. I'm still a a loss as I mntioned in the mapping. Do you have any pointers on that? I would appreciate any help. Thanks in advance

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in