BOFS - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Farhod

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Segment Tree with Lazy Propagation (Segment Tree Beats would be added advantage)

PROBLEM:

Given N segments and two integers A and B, you have to find the minimum number of coins required to end all games if you start a game with parameters (x, y). You have to answer this for Q queries.

A game (x, y) is played as follows.

  • If x = 0, the game ends immediately.
  • Otherwise if y \leq l_x OR y \geq r_x, end this game and play game (x-1, y).
  • Otherwise if l_x < y < r_x, you must choose one of the following.
    • Pay A coins, end this game and play a game with (x-1, y).
    • Pay B coins, end this game and play two independent games - one with (x-1, l_x) and one with (x-1, r_x).

Let’s denote C(x, y) as the minimum number of coins needed to end all games starting from game (x, y).

QUICK EXPLANATION

  • Let’s maintain a Data structure of size 2*10^5 which can answer query C(x, y) quickly for a fixed x. Let’s try to update this data structure to answer queries of type C(x+1, y).
  • We can see, if y \leq l_{x+1} OR y \geq r_{x+1}, then C(x+1, y) = C(x, y).
  • By third condition, if l_{x+1} < y < r_{x+1}, then C(x+1, y) = min(A+C(x, y), B+C(x, l_x)+C(x, r_x)).
  • The above update and query operations can be done efficiently by a data structure storing Q values x_i supporting
    • update for i \in [L, R] x_i = min(x_i+p, q)
    • query x_i.
  • A segment tree with lazy tags can be used here. The tag is represented by f_{p, q}(x) returning min(x+p, q) is used, which implies all positions in range of current node shall be applied update.
  • This tag can be merged, f_{a, b}(f_{c, d}(x)) = f_{a, b}(min(c+x, d)) = min(a+min(c+x, d), b) which can be written as min(a+c+x, min(a+d, b)) which is equivalent to f_{a+c, min(a+d, b)}(x). This allows lazy propagation of tags.
  • We can sort queries by x, and apply updates till the DS can answer queries (x, y) and then make the queries on this Data Structure.

EXPLANATION

First of all, Let’s assume we have an array D of length 2*10^5 which stores answers for a fixed x and all possible values of y. It is not hard to see that C(x+1, y) depends only upon C(x, z) for some values of z.

We shall update this data structure to answer queries for each x incrementally, and if we have any query for current x, we shall answer that before updating the data structure to move a step forward.

We can see, that if the data structure is currently answering for current x, then C(x, y) = D_y. So, answering queries is easy with this data structure. Let’s come to updating it to move from answering C(x, y) to C(x+1, y) for each value of y.

If y \leq l_{x+1} OR y \geq r_x, then by second condition, C(x+1, y) = C(x, y), involving no change in cost.

But if l_{x+1} < y < r_{x+1}, then D_y is updated to min( A+D_y, B+D_{l_x} + D_{r_x}).

This allows us to solve the problem, but is too slow, since each update may take up to 2*10^5 iterations and there can be N updates in the worst case,

Clearly, we need a data structure to handle following operations efficiently on array D of length 2*10^5.

  • update for i \in [L, R], set D_i = min(D_i+p, q)
  • query D_i.

Let’s define a function f_{a, b}(x) = min(a+x, b). Above update can be written as applying update D_i = f_{p, q}(D_i) for each i \in [L, R].

Time to revert to our beloved Range update Data Structure, Segment Tree with Lazy Propagation, about which, you can read here.

Now, the criteria for using lazy propagation on any problem, is the ability to merge the lazy tags into one lazy tag, which combines the effect of both tags.

Here, we can make a segment tree where ith leaf denote D_i for some fixed x. For updating the segment tree, if next interval is [l_{x+1}, r_{x+1}] and G = C(x, l_{x+1}) + C(x, r_{x+1}), we need to apply update on range [l_x+1, r_x-1]. setting D_i = f_{A, B+G}(D_i). This can be done by using Tag (A, B+G) on internal node of segment tree.

Suppose, for a value v, First tag (c, d) is to be applied, then tag (a, b) is to be applied on resultant value. It can be written as f_{a, b}(f_{c, d}(x)) = min(a+f_{c, d}(x), b) = min(a+min(c+x, d), b) = min(a+c+x, min(d+a, b)) = f_{a+c, min(a+d, b)}(x). Hence, we have managed to merge the lazy tags, so whenever we query a position, we can just push down the tags till the leaf, and apply the tag on leaf to obtain value after alll updates.

This solves the problem,

TIME COMPLEXITY

Time complexity is O(Q*log(Q)+(N+MX)*log(MX)) per test case where MX = 2*10^5.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;

using namespace std;

int n;
int A;
int B;
int l[N];
int r[N];
long long res[N];
vector < pair < int, int > > eq[N];
pair < long long, long long > t[4 * N];

pair < long long, long long > comb(pair < long long, long long > x, pair < long long, long long > y)
{
	    if(!x.fi) return y;
	    if(!y.fi) return x;
	    pair < long long, long long > res;
	    res.fi = x.fi + y.fi;
	    res.se = min(x.se, x.fi * A + y.se);
	    return res;
}

void push(int x)
{
	    if(t[x].fi){
	            t[x * 2] = comb(t[x], t[x * 2]);
	            t[x * 2 + 1] = comb(t[x], t[x * 2 + 1]);
	            t[x] = {0, 0};
	    }
}

void upd(int x, int l, int r, int tl, int tr, pair < long long, long long > y)
{
	    if(tl > tr){
	            return;
	    } else if(l == tl && r == tr){
	            t[x] = comb(y, t[x]);
	            return;
	    }
	    push(x);
	    int m = (l + r) / 2;
	    upd(x * 2, l, m, tl, min(m, tr), y);
	    upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, y);
}

long long get(int x, int l, int r, int g)
{
	    if(l == r){
	            return min(t[x].fi * A, t[x].se);
	    }
	    push(x);
	    int m = (l + r) / 2;
	    if(g <= m){
	            return get(x * 2, l, m, g);
	    } else{
	            return get(x * 2 + 1, m + 1, r, g);
	    }
}

void solve()
{
	    for(int i = 1; i < 4 * N; i++){
	            t[i] = {0, 0};
	    }
	    int q;
	    cin >> n >> q >> A >> B;
	    for(int i = 1; i <= n; i++){
	            cin >> l[i] >> r[i];
	            eq[i].clear();
	    }
	    for(int i = 1; i <= q; i++){
	            int x, y;
	            cin >> x >> y;
	            eq[x].push_back({y, i});
	    }
	    int G = 200000;
	    for(int i = 1; i <= n; i++){
	            if(l[i] + 1 < r[i]){
	                    long long cost = get(1, 1, G, l[i]) + get(1, 1, G, r[i]) + B;
	                    upd(1, 1, G, l[i] + 1, r[i] - 1, {1, cost});
	            }
	            for(auto p: eq[i]){
	                    res[p.se] = get(1, 1, G, p.fi);
	            }
	    }
	    for(int i = 1; i <= q; i++){
	            cout << res[i] << "\n";
	    }
}

int main()
{
	    ios_base::sync_with_stdio(0);

	    int T;
	    cin >> T;
	    while(T--){
	            solve();
	    }
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*10+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll


int l[212345],r[212345],answ[212345];

int MAXL = 2e5+5;
int flag=0;
int iinf;
vector<vii> vec(212345);
int lazy1[812345],lazy2[812345];
int build(int node,int s,int e){
	lazy1[node]=0;
	lazy2[node]=iinf;
	if(s==e){
		lazy2[node]=0;
		return 0;
	}
	int mid=(s+e)/2;
	build(2*node,s,mid);
	build(2*node+1,mid+1,e);
}

int update1(int node,int s,int e,int l,int r,int val){
	if(lazy1[node] || lazy2[node]!=iinf){
		if(s!=e){
			lazy1[2*node]+=lazy1[node];
			lazy2[2*node]+=lazy1[node];
			lazy2[2*node]=min(lazy2[node],lazy2[2*node]);

			lazy1[2*node+1]+=lazy1[node];
			lazy2[2*node+1]+=lazy1[node];
			lazy2[2*node+1]=min(lazy2[node],lazy2[2*node+1]);
			lazy1[node]=0;
			lazy2[node]=iinf;	
		}
	}
	if(r<s || e<l){
		return 0;
	}
	if(l<=s && e<=r){
		lazy1[node]+=val;
		if(s==e)
			lazy2[node]+=val;	
		return 0;
	}
	int mid=(s+e)/2;
	update1(2*node,s,mid,l,r,val);
	update1(2*node+1,mid+1,e,l,r,val);

	return 0;
}

int update2(int node,int s,int e,int l,int r,int val){
	if(lazy1[node] || lazy2[node]!=iinf){
		if(s!=e){
			lazy1[2*node]+=lazy1[node];
			lazy2[2*node]+=lazy1[node];
			lazy2[2*node]=min(lazy2[node],lazy2[2*node]);

			lazy1[2*node+1]+=lazy1[node];
			lazy2[2*node+1]+=lazy1[node];
			lazy2[2*node+1]=min(lazy2[node],lazy2[2*node+1]);
			lazy1[node]=0;
			lazy2[node]=iinf;	
		}
	}
	if(r<s || e<l){
		return 0;
	}
	if(l<=s && e<=r){
		lazy2[node]=min(lazy2[node],val);
		return 0;
	}
	int mid=(s+e)/2;
	update2(2*node,s,mid,l,r,val);
	update2(2*node+1,mid+1,e,l,r,val);

	return 0;
}

int query(int node,int s,int e,int pos){

	if(lazy1[node] || lazy2[node]!=iinf){
		if(s!=e){
			lazy1[2*node]+=lazy1[node];
			lazy2[2*node]+=lazy1[node];
			lazy2[2*node]=min(lazy2[node],lazy2[2*node]);

			lazy1[2*node+1]+=lazy1[node];
			lazy2[2*node+1]+=lazy1[node];
			lazy2[2*node+1]=min(lazy2[node],lazy2[2*node+1]);
			lazy1[node]=0;
			lazy2[node]=iinf;	
		}
	}
	if(s==e){
		return lazy2[node];
	}
	int mid=(s+e)/2;
	if(pos<=mid){
		return query(2*node,s,mid,pos);
	}
	else
		return query(2*node+1,mid+1,e,pos);
}

main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,q,a,b;
		cin>>n>>q>>a>>b;
		iinf=inf;
		iinf*=inf;
		int i,j;
		build(1,0,MAXL);
		rep(i,n+10){
			vec[i].clear();
		}
		f(i,1,n+1){
			cin>>l[i]>>r[i];
		}
		int x,y;
		rep(i,q){
			cin>>x>>y;
			vec[x].pb(mp(y,i));
		}
		int ans=0;
		f(i,1,n+1){
			if(l[i]+1<=r[i]-1){
				ans=query(1,0,MAXL,l[i])+query(1,0,MAXL,r[i])+b;
				update1(1,0,MAXL,l[i]+1,r[i]-1,a);

				update2(1,0,MAXL,l[i]+1,r[i]-1,ans);
				
			}
			rep(j,vec[i].size()){
				answ[vec[i][j].ss]=query(1,0,MAXL,vec[i][j].ff);
			}
		}
		rep(i,q){
			cout<<answ[i]<<'\n';
		}

	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class BOFS{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), q = ni(), mx = (int)2e5+1;
	    long a = nl(), b = nl();
	    SegTree t = new SegTree(mx);
	    int[][] seg = new int[1+n][];
	    for(int i = 1; i<= n; i++)seg[i] = new int[]{ni(), ni()};
	    int[][] qu = new int[q][];
	    long[] ans = new long[q];
	    for(int i = 0; i< q; i++)qu[i] = new int[]{i, ni(), ni()};
	    Arrays.sort(qu, (int[] i1, int[] i2) -> Integer.compare(i1[1], i2[1]));
	    int cur = 0;
	    for(int i = 0; i< q; i++){  
	        while(cur < qu[i][1]){
	            cur++;
	            long min = t.query(seg[cur][0])+t.query(seg[cur][1]);
	            if(seg[cur][0]+1 <= seg[cur][1]-1)t.update(seg[cur][0]+1, seg[cur][1]-1, a, b+min);
	        }
	        ans[qu[i][0]] = t.query(qu[i][2]);
	    }
	    for(long l:ans)pn(l);
	}
	class SegTree{
	    int m = 1;
	    long[][] tag;
	    long[] val;
	    final long IINF = (long)1e18;
	    //Tag is a function f{a, b}(x) = min(a+x, b)
	    public SegTree(int n){
	        while(m<n)m<<=1;
	        tag = new long[2][m<<1];
	        Arrays.fill(tag[1], IINF);
	        val = new long[m];
	    }
	    void push(int i, int ll, int rr){
	        if(tag[1][i] == IINF)return;
	        if(i>=m){
	            val[i-m] = Math.min(val[i-m]+tag[0][i], tag[1][i]);
	        }else{
	            tag[0][i<<1] += tag[0][i];
	            tag[1][i<<1] = Math.min(tag[1][i<<1]+tag[0][i], tag[1][i]);
	            tag[0][i<<1|1] += tag[0][i];
	            tag[1][i<<1|1] = Math.min(tag[1][i<<1|1]+tag[0][i], tag[1][i]);
	        }
	        tag[0][i] = 0;
	        tag[1][i] = IINF;
	    }
	    //Update -> for all i in [l, r], change x to min(a+x, b)
	    void update(int l, int r, long a, long b){update(l, r, 0, m-1, 1, a, b);}
	    void update(int l, int r, int ll, int rr, int i, long a, long b){
	        push(i, ll, rr);
	        if(l == ll && r == rr){
	            tag[0][i] = a;
	            tag[1][i] = b;
	            return;
	        }
	        int mid = (ll+rr)/2;
	        if(r <= mid)update(l, r, ll, mid, i<<1, a, b);
	        else if(l> mid)update(l, r, mid+1, rr, i<<1|1, a, b);
	        else {
	            update(l, mid, ll, mid, i<<1, a, b);
	            update(mid+1, r, mid+1, rr, i<<1|1, a, b);
	        }
	    }
	    //Apply all lazy tag on path from pth leaf, answer when y = p;
	    long query(int p){return query(p, 0, m-1, 1);}
	    long query(int p, int ll, int rr, int i){
	        push(i, ll, rr);
	        if(i >= m)return val[i-m];
	        int mid = (ll+rr)/2;
	        if(p <= mid)return query(p, ll, mid, i<<1);
	        return query(p, mid+1, rr, i<<1|1);
	    }
	}
	
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new BOFS().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

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

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

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

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

3 Likes

@taran_1407
Thanks for the excellent tutorial.

Could we not instead pass on the “lazy” value to the children and once the lazy value on this node is nil, update it with the current update operation?