BINBSR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: aryansanghi
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Sets (or segment trees)

PROBLEM:

You are given a binary array A of length N, filled with zeros.
Process Q updates to it, of three types:

  • Set a range of values to 0.
  • Set a range of values to 1.
  • Sort A in non-descending order.

After each update, output the number of passes bubble sort will need to sort the array.

EXPLANATION:

The sorting algorithm mentioned in the statement is simply bubble sort.

We start by figuring out the number of passes bubble sort needs to sort a fixed binary array A.

Note that the final state requires all zeros to be to the left of all ones.
Each 1 in the array can move around a lot in a single pass of bubble sort - but what about the 0ā€™s?

Letā€™s look at a single 0 in the array.
Suppose there are k ones to the left of this zero.
Then,

  • If k = 0, this 0 is already part of a prefix of zeros. It wonā€™t move ever again.
  • If k \gt 0, then this 0 will swap with exactly one 1 to its left, and nothing else.
    This is because the k-th 1 will cross this 0, while all previous 1ā€™s wouldā€™ve been blocked by the k-th 1 and so wouldā€™ve stopped moving already.

So, since this 0 needs to end up to the left of all ones, it will certainly require at least k passes for that to happen; since each pass can take it past only a single occurrence.
Every pass will send it past one 1 if itā€™s possible, so it will in fact take exactly k passes for this occurrence of 0 to end up to the left of all the ones.

This immediately gives us a lower bound on the answer: consider the rightmost occurrence of 0, and suppose there are m ones before it.
Then m passes are needed for it to go past all ones.
Clearly, m passes will suffice since everything else is also moving.
Thus, the answer is just m+1 (since we also have a final ā€˜checkā€™ pass after the array is sorted.)

From above, we know that the data we need to maintain is the number of ones present before the last occurrence of 0.

Note that this is equivalent to just the total number of ones minus the number of ones present in the suffix of A.
Weā€™ll need to maintain these two quantities across updates.

Our updates are to set a range of values to 0/1, or to sort A in ascending order.
Note that sorting A in ascending order is in fact equivalent to just doing a couple of range set operations: after counting the number of zeros in the array, we can range set the prefix of that length to full 0ā€™s and range set the remaining suffix to full 1ā€™s.
So, it suffices to work with just range set operations.

To handle this, there are a couple of different ways.
Perhaps the simplest is to use segment trees: counting the number of ones in the array is equivalent to summing up values since this is a binary array; so we need to be able to handle ā€œset value to rangeā€ and ā€œfind sum of rangeā€, which a segment tree can do in \mathcal{O}(\log N) with lazy propagation.

If you donā€™t know how to use segment trees, there are alternate data structures that can work too - for example sets.
The idea here is to represent the ones in the array via a set of disjoint intervals - for example A = [1, 0, 1, 1, 0, 0, 1] becomes the set \{[1, 1], [3, 4], [7, 7]\}.

When updating a range [L, R] of the array,

  • If setting the range to 0, all intervals contained fully within [L, R] will be deleted.
    Further, there will be (at most) one range that intersects [L, R] on the left and similarly (at most) one range that intersects [L, R] on the right; these intervals need to be clamped to L/R respectively.
  • If setting the range to 1, all intervals contained fully within [L, R] will merge into a single one, along with the at most two intervals intersecting the borders of [L, R].
    This corresponds to deleting all internal intervals as well as the two border intervals, and inserting their union into the set instead.

In either case, finding the appropriate intervals to delete quickly can be done using binary search, as long as the intervals are stored in a sorted set (such as std::set in C++)
Note that in each operation, we may end up deleting several intervals but we insert at most two new intervals (setting to 1 involves inserting one interval, setting to 0 can have two insertions - one for each border.)

This means the total number of intervals ever created is \le 2N.
Since we can only delete intervals that already exist, the total number of deletions across all operations also cannot exceed 2N.
Thus the complexity is \mathcal{O}(N\log N) overall.

This method of maintaining ā€˜activeā€™ elements using a set of intervals is quite handy to have around.
For a reference implementation, you can look at kactl.

TIME COMPLEXITY:

\mathcal{O}(N + Q\log N) per testcase.

CODE:

Tester's code (C++) 
#include<bits/stdc++.h>
#define int long long
using namespace std;

int tot = 0;

set<pair<int,int>>::iterator addInterval(set<pair<int,int>>& is, int L, int R) {
    if (L == R) return is.end();
    auto it = is.lower_bound({L, R}), before = it;
    while (it != is.end() && it->first <= R) {
        R = max(R, it->second);
        tot -= it->second - it->first;
        before = it = is.erase(it);
    }
    if (it != is.begin() && (--it)->second >= L) {
        L = min(L, it->first);
        R = max(R, it->second);
        tot -= it->second - it->first;
        is.erase(it);
    }
    tot += R - L;
    return is.insert(before, {L, R});
}

void removeInterval(set<pair<int,int>>& is, int L, int R) {
    if (L == R) return;
    auto it = addInterval(is, L, R);
    int l2 = it->first;
    int r2 = it->second;
    tot -= r2 - l2;
    is.erase(it);
    if (l2 < L) {
        is.emplace(l2, L);
        tot += L - l2;
    }
    if (R < r2) {
        is.emplace(R, r2);
        tot += r2 - R;
    }
}
 
void solve(){
    int n, q; cin >> n >> q;
    tot = 0;
    set<pair<int,int>> ones;
    
    while(q--){
        int op; cin >> op;
        if(op == 0){
            int l, r; cin >> l >> r;
            removeInterval(ones,l,r+1);
        }
        else if(op == 1){
            int l, r; cin >> l >> r;
            addInterval(ones,l,r+1);
        }
        else{
            int temp = tot;
            removeInterval(ones,1,n+1);
            addInterval(ones,n+1-temp,n+1);
        }
        int suf = 0;
        if(ones.size()){
            auto it = ones.end();it--;
            if(it->second == n+1)suf = it->second - it->first;
        }
        cout << tot - suf + 1 << "\n";
        
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    while(t--)
        solve();
    return 0;
}
2 Likes
2

Thank you so much for the editorial and mentioning my proposed solution in it too!