Binary Lifting #1 CF-702E

Introduction to Binary Lifting

This is a technique that is widely used to solve problems based on trees and graphs. As the name suggests, we take leaps from current node in powers of 2.

The basic building recurrence is :

dp[node][jump] = dp[[node][jump-1]][jump-1]

Here jump denotes the leap of pow(2,jump) from vertex = node

It is very easy to derive this recurrence, it simple states that to make jump of pow(2,k+1) , first jump from current node to pow(2,k) node and from there jump pow(2,k), which ultimately means you jump pow(2,k+1) from current node.

Problem Statement- E. Analysis of Pathes in Functional Graph

Link to problem – https://codeforces.com/contest/702/problem/E

The problem asks us to find out that , taking any vertex v from graph, if we walk a length of k, then what is the sum of all weights in our path and which is the minimal weight in our path.

Now, we can use binary lifting because each vertex is guaranteed to be directed only to single vertex, i.e. , outdegree =1. So, we can use binary lifting here.

We will create the table of binary lifting using the above recurrance, but also we can create the tables for each question, i.e., the sum of weight of edges and minimum weight over a path.

The solution for the problem statement is here –

ll n,k;
ll table[100005][45]={};
ll sumt[100005][45]={};
ll mint[100005][45];
void solve()
{
	
	cin >> n >> k;
	rep(i,0,n){
        cin >> table[i][0];
    }
    rep(i,0,n){
        cin >> sumt[i][0];
        mint[i][0] = sumt[i][0];
    }
    rep(jmp,1,45){
        rep(i,0,n){
            table[i][jmp] = table[table[i][jmp-1]][jmp-1];
            sumt[i][jmp] = sumt[i][jmp-1] + sumt[table[i][jmp-1]][jmp-1];
            mint[i][jmp] = min(mint[i][jmp-1],mint[table[i][jmp-1]][jmp-1]);
        }
    }
    rep(i,0,n){
        ll jmp = k;
        ll sm = 0;
        ll mn = INT_MAX;
        ll ct = 0;
        ll t = i;
        while(jmp>0){
            if (jmp&1){
                sm += sumt[t][ct];
                mn = min(mn,mint[t][ct]);
                t = table[t][ct];
            }
            ct++;
            jmp>>=1;
        }
        cout << sm << " " << mn << endl;
    }   
}

What to try next ?

Binary Lifting is commonly used to calculate LCA, make sure you have done that already.

Try this one- https://codeforces.com/contest/609/problem/E

Leave a Reply