BURARRAY - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Mladen Puzic

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

DIFFICULTY:

PREREQUISITES:

Treap plus Binary Search, or Union-Disjoint Sets using maps with path compression.

PROBLEM:

There’s an array A of length N \leq 10^{18} such that A_i = i. We are required to handle updates A_p = 0 for some position p and answer queries finding the maximum value in range [L, R]. Queries are online, so we don’t get next update or query until we answer the current one.

EXPLANATION

For this problem, I shall describe two solutions, one used by the tester and one mine. Setter uses the third method similar to keeping intervals idea described here.

In all solutions, common observation is that maximum of range [L, R] for some query is the rightmost value in range [L, R] which is not yet updated to 0, or 0 if all positions in range [L, R] are assigned to 0. We all seek to find this value, in our own ways.

Tester’s Solution

Suppose you maintain N disjoint sets, one for each position, and for the update on position p, assign p-1 as the parent of set on position p.

By this, we always know that root of the disjoint set is always a position which is not yet updated to zero, and secondly, since each position is assigned parent the position to its immediate left, the root of the disjoint set containing position p shall be the rightmost position which is not updated to 0. Hence, if the root of the disjoint set containing R for a query [L, R] is less than L, all positions in the range are updated to zero and thus a maximum is zero. Otherwise, The root of the disjoint set containing R is the rightmost position not yet updated to zero, which is the required answer we are looking for.

Since N is way too large, we cannot store sets in the array, but we can use maps. See tester’s solution for implementation.

Editorialist’s Solution
Let us maintain a mysterious data structure which is capable of following operations in O(log(size)).

  • Insert a value.
  • Determine whether the value x is present.
  • Count the number of values present in set smaller than or equal to x.

Suppose at each update, we insert the position into this DS, if not already present. Then, at each query [L, R], If all positions in [L, R] are assigned to zero, then the number of elements in range [L, R] in DS = Number of elements less than or equal to R less the number of elements smaller than or equal to L-1 which should be R-L+1. The answer, in this case, is zero.

Otherwise, Let us find the rightmost position p such that Number of elements in the range [p, R] is less than R-p+1. We can see that since all positions q > p satisfies the condition that the number of elements in the range [q, R] = R-q+1, p is the largest value \leq R which is not present in DS which is the required answer for our query.

This mysterious data structure can be any Balanced Binary Search Tree such as AVL-Tree, Treap, Red-black tree or so on. Editorialist solution is based on Treap which you may refer below.

Bonus: There are updates of the second kind updating A_p = p for position p.

TIME COMPLEXITY

For tester’s solution, the time complexity is O(Q*α(Q)) per test case. (Or O(Q*α(Q)*log(Q)) if we consider ordered maps.
For editorialist’s solution, the time complexity is O(Q*log(Q)*log(N)) per test case.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pll pair<lld,lld>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 2000000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
set<pll> S;
set<pll>::iterator query(lld X) {
	auto p = S.lower_bound({X, LINF}); p--; ///last interval with l smaller than X
	return p;
}
void update(lld X) {
	auto q = query(X);
	auto p = q; q++;
	pll in1 = *p, in2 = *q, rez;
	if(X <= in1.se) return; ///if X is already in some interval
	if(X > in1.se+1 && X < in2.fi-1) rez = {X, X}; ///if X doesn't touch any other interval
	else if(X == in1.se+1 && X != in2.fi-1) rez = {in1.fi, X}, S.erase(p); ///if it touches only left interval
	else if(X != in1.se+1 && X == in2.fi-1) rez = {X, in2.se}, S.erase(q); ///if it touches only right interval
	else if(X == in1.se+1 && X == in2.fi-1) rez = {in1.fi, in2.se}, S.erase(p), S.erase(q); ///if it touches both intervals
	S.insert(rez);
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
	int T; cin >> T;
	while(T--) {
	    S.clear();
	    lld N, s = 0; int Q; cin >> N >> Q;
	    S.insert({0, 0}); S.insert({LINF, LINF}); /// so we can always decrement in query and increment in update
	    while(Q--) {
	        int type; cin >> type;
	        if(type == 1) {
	            lld x, t; cin >> t;
	            x = t + s;
	            update(x);
	        } else {
	            lld p, q, l, r, rez; cin >> p >> q;
	            l = p+s; r = q+s;
	            pll rezz = *query(r);
	            if(rezz.se < r) rez = r; /// if r is not 0
	            else if(rezz.fi > l) rez = rezz.fi-1; /// largest element not zero
	            else rez = 0; /// if whole subarray is 0
	            s += rez;
	            if(s >= N) s %= N;
	            cout << rez << endl;
	        }
	    }
	}
}
Tester's Solution
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

map<ll, ll> par;

ll getPar(ll v){
	if (!par.count(v))
		par[v] = v;
	return par[v]==v? v: par[v]=getPar(par[v]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		par.clear();
		ll sm = 0;
		ll n; int q; cin >> n >> q;
		while (q--){
			int type; cin >> type;
			if (type == 1){
				ll x; cin >> x; x += sm;
				par[x] = x-1;
			}
			else{
				ll l, r; cin >> l >> r; l += sm, r += sm;
				ll p = getPar(r);
				if (p < l)
					cout << "0\n";
				else {
					cout << p << "\n";
					sm = (sm + p)%n;
				}
			}
		}
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class BURARRAY{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    Treap root = null;
	    long n = nl();
	    long ans = 0, s = 0;
	    for(int qc = 1, qq = ni(); qc <= qq; qc++){
	        int ty = ni();
	        if(ty == 1){
	            long x = nl()+s;
	            if(!contains(root, x))root = insert(root, x);
	        }else{
	            long l = nl()+s, r = nl()+s;
	            long small = smaller(root, l-1);
	            long last = smaller(root, r);
	            if(!contains(root, r))ans = r;
	            else if(r-l+1 == last-small)ans = 0;
	            else{
	                long lo = l, hi = r;
	                while(lo+1<hi){
	                    long mid = lo+(hi-lo)/2;
	                    if(last-smaller(root, mid-1) == r-mid+1)hi = mid;
	                    else lo = mid;
	                }
	                ans = -1;
	                for(long i = hi; i>= lo && ans == -1; i--)
	                    if(last-smaller(root, i-1) < r-i+1)
	                        ans = i;
	            }
	            pn(ans);
	            s = (s+ans)%n;
	        }
	    }
	}
	TreeSet<Long> set = new TreeSet<>();
	class Treap{
	    long val;long pr;
	    int count;
	    Treap left, right;
	    public Treap(long v){
	        val = v;
	        long x;
	        do x = new Random().nextLong();
	        while(set.contains(x));
	        pr = x;
	        set.add(x);
	        count = 1;
	    }
	    void update(){
	        this.count = 1+getCount(left)+getCount(right);
	    }
	}
	int getCount(Treap t){
	    return t==null?0:t.count;
	}
	class TreapPair{
	    Treap left, right;
	    TreapPair(Treap left, Treap right){
	        this.left = left;
	        this.right = right;
	    }
	}
	TreapPair split(Treap root, long minRight){
	    if(root == null)
	        return new TreapPair(null, null);
	    if(root.val >= minRight){
	        TreapPair leftSplit = split(root.left, minRight);
	        root.left = leftSplit.right;
	        root.update();
	        leftSplit.right = root;
	        return leftSplit;
	    }else{
	        TreapPair rightSplit = split(root.right, minRight);
	        root.right = rightSplit.left;
	        root.update();
	        rightSplit.left = root;
	        return rightSplit;
	    }
	}
	Treap merge(Treap left, Treap right){
	    if(left == null)return right;
	    if(right == null)return left;
	    if(left.pr > right.pr){
	        left.right = merge(left.right, right);
	        left.update();
	        return left;
	    }else{
	        right.left = merge(left, right.left);
	        right.update();
	        return right;
	    }
	}
	Treap insert(Treap root, long x){
	    TreapPair split = split(root, x);
	    return merge(merge(split.left, new Treap(x)), split.right);
	}
	int smaller(Treap root, long x){
	    if(root == null)return 0;
	    if(root.val <= x)return getCount(root.left)+1+smaller(root.right, x);
	    else return smaller(root.left, x);
	}
	boolean contains(Treap root, long x){
	    if(root == null)return false;
	    if(root.val == x)return true;
	    if(x < root.val)return contains(root.left, x);
	    else return contains(root.right, x);
	}
	//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 BURARRAY().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:

11 Likes

Is it mandatory ? I used DSU without path compression. (weighted union)
https://www.codechef.com/viewsolution/24995128
And I think complexity with path compression and weighted union is O(log ^*N) according to this tutorial
Here is a good tutorial on DSU :
https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/

2 Likes

just my opinion. I find path compression faster to code than union by rank. :slight_smile:

3 Likes

I used Seg trees and it gave me 20 points :confused: Will it work if I use it with lazy propagation?

what !!
Codes just differ by one line I think :thinking::thinking:

Sometimes round needs to be challenging also.Last time lunchtime was easy

3 Likes

yeah! save every second :smiley: Also, Need extra rank array!

1 Like

https://www.codechef.com/viewsolution/24998486
Answer using unordered map

10 Likes

In worst case, it might have lead to TLE, wasn’t sure though.

so you mean we avoid weighted union and do just path compression right ?

Is this you call challenging, maximum of the majority struggling to even score a perfect score in any of the problems.

solution using path compression:-https://www.codechef.com/viewsolution/24988479

1 Like

I used weighted union and its O(log(n)) in worst case I think :thinking:

https://www.codechef.com/viewsolution/24999166 what is going on this solution . Is he using pbds ?

You can do both do further reduce constant factor(Asymptotically, they all are same. independent or using both at once)

1 Like

using both makes it O(log^*(n)) its different

1 Like

i think lazy is only be helpful if there is a range update !!!but there is a index update only

1 Like

check this.
here its mentioned using both effectively reduce to it constant though asymptotically its still log(n) for all cases.

I like this code, because I used three map and one set.

I think I’m gonna cry now.
I used vectors as a hash to store indices which were set zero.
https://www.codechef.com/viewsolution/24998486
This guy, however, used unordered maps and got AC every test case, whereas I got TLE in all except the first.
Kill me plij. I don’t wanna live anymore.