Binary Editorial - Unofficial

unofficial

#1

PROBLEM LINK:

Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Observational Skills

PROBLEM:

Given an integer Z and an array S with N elements where 0 \le S_i \le 1, determine S after Z moves, where each move represents simultaneous swapping of every S[i], S[i + 1], when S[i] < S[i + 1]

QUICK EXPLANATION:

For every position i (0 \le i < N) in S, determine the number of moves required for every S[x] = 0 (x \le 0 < i) to reach index i. Based on this, determine the number of steps a particular 1 in S can move forward.

EXPLANATION:

^1 Here S[x] \to S[k] determines the array from S[x], S[x + 1], S[x + 2], ..., S[k]
^2 The number of moves it takes for a given zero to be right in front of a particular 1

Observations:

Notice that, if S is divided into two sub-arrays S[0] \to S[k] ^1 for some k and S[k + 1] \to S[N - 1], The second sub-array is dependent on the first sub-array, whereas the first sub-array isn’t dependent on the second sub-array. So, the solution of S[0] \to S[k] has to be determined before determining the solution of S[0] \to S[k + 1].

PART 1:

Imagine it takes k moves for a particular 0 to be accessible ^2 by a particular 1 at index x. So in the k + 1 move, the 0 is swapped with the 1. So now, it took that 0, \, k + 1 moves to reach the position x.
So, the inference from this is, the number of moves it takes for any 0 to be behind a particular 1 is number\, of\, moves\, it\, takes\, to\, be\, in\, front\, of\, it\, +1

PART 2:

Take a look at this test case. S = 0\,1\,0\,0\,0\,1. Before you start reading this, pen down how the array looks after every move.

The first 0 needs 0 moves to be accessible ^2 by the First 1(since it already is right in front of the 1), and after the 1st move, it is right behind that 1.
Now, the first 0 can be accessed by the second 1 only after all other zeros between this 0 and that 1 have been pushed back by that particular 1.
3 moves are needed for the second 1 to go in front of the 3 consecutive 0's. So that would mean the second 0 would be pushed back in the 3rd move.
The first 0 was pushed back in the first move, while the second 0 was pushed back in the 3rd move. That would mean that the first 0 would be pushed back again only in the 4th move.

PART 3:

From the above explanations, you would be able to infer the solution. Lets summarise it up now.
We have a deque<int> NoOfMovesReqd, in which each element represents the number of moves required for a 0 to to be pushed back by the last 1 that we have come across(Remember, we are iterating from index 0 to index N - 1 of input array S).
The value of a more recent 0 is later in the deque than a previous 0 (Reason left as exercise to the reader). Here is how the code goes

deque<int> M; //This is the deque NoOfMovesReqd
bool Ans[N] = {};
int contiZero = 0; //This represents the number of continuous 0's in S 
for(int i = 0; i < N; i++){
    if(M.front() >= Z) M.pop_front(); //If a zero takes >= Z moves to be pushed back by the prev 1, the next 1 can't use it, so delete it
    
    if(S[i] == 0){
        contiZero++;
        if(contiZero >= Z)
            M.clear(); //If there are more than Z continuous zero's, none of the previous zero's could be accessed(trivial verification)
        if(contiZero + M.size() > Z)
            M.pop_front(); //Since max number of 0's that can be pushed by a 1 is Z, we pop the front zeros from the list 
    }else{
        contiZero = max(contiZero, Z); //Explanation same as above
        //Now I insert all these 0's with their values(The last zero has value zero, from part 1)
        for(int q = contiZero - 1; q >= 0; q--)
            M.push_back(q);

        Ans[i - M.size()] = 1; //The number of zero's the current 1 can push back is equal to the size of M (because every zero M represents, requires less than Z moves to be pushed by the current 1(directly from above))

        M.back()++; //From part 1 above, this is going to be done with the entire deque,  
        for(int x = M.size() - 1; x >= 0; x--){
            if(M[x] <= M[x + 1]) M[x] = M[x + 1] + 1; //Part 2 above
            else M[x]++; //This is directly understandable, from part 1        
        }
        contiZero = 0;
    }
}

SUMMARY

This is the entire logic of the question. But guess what, this code will still give TLE! This needs to be optimised using deque of pairs, which i leave the reader to implement. It follows the similar logic, just notice that the values in the deque form blocks of continuous numbers.

DEBUGGING TOOLS

Brute Force for testing
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
    
#define INF 999999999
#define MOD 1000000007
    
using namespace std;
    
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T; cin >> T;
    while(T--){
        int N, Z; cin >> N >> Z;
        bool A[N] = {};

        for(int i = 0; i < N; i++)
            cin >> A[i];
        
        while(Z--)
            for(int x = 0; x < N - 1; x++)
                if(A[x] == 0 and A[x + 1] == 1) swap(A[x], A[x + 1]), x++;
        
        for(bool i : A)
            cout << i << " ";
        
        cout << endl;

    }


return 0;
}
TestCases
100
6 3
0 0 0 1 0 1 
14 5
1 1 1 1 1 1 1 1 0 1 1 1 0 0 
9 4
0 1 0 0 1 0 1 1 0 
9 5
0 0 1 1 0 1 0 1 0 
13 4
0 1 1 1 1 0 0 1 0 1 0 0 0 
12 5
1 0 1 1 1 1 1 0 0 0 0 1 
13 3
1 0 1 1 0 1 0 0 0 1 0 1 0 
9 4
1 0 1 1 0 1 1 0 1 
12 2
0 1 0 1 1 1 1 0 1 1 1 0 
6 5
1 0 0 0 1 1 
12 4
1 0 0 0 1 0 0 1 1 1 1 0 
6 2
0 0 1 1 0 0 
13 3
1 1 1 1 1 1 1 1 0 0 0 1 0 
11 4
1 1 1 0 1 0 0 1 0 1 0 
8 5
1 1 0 1 1 0 0 1 
12 5
0 1 1 1 1 1 0 1 1 1 1 0 
9 5
1 0 0 0 0 0 0 0 1 
13 3
0 1 1 0 1 0 0 1 1 1 1 1 0 
10 3
1 1 1 1 0 1 1 1 1 0 
14 5
1 0 0 0 1 0 1 0 1 0 0 0 1 1 
10 5
1 0 1 0 1 1 1 1 1 0 
14 3
1 1 1 0 1 1 0 1 0 1 0 1 0 1 
6 5
0 1 0 0 0 0 
14 5
1 1 0 1 0 0 0 1 1 1 0 0 1 1 
7 2
0 0 0 0 0 1 1 
11 5
1 0 1 0 0 1 0 1 0 0 0 
11 4
0 1 1 0 0 0 1 1 0 1 1 
12 4
0 0 1 0 0 0 0 0 1 0 1 0 
9 4
1 0 1 1 0 0 1 1 1 
9 4
0 1 0 0 0 1 0 1 0 
8 2
0 1 0 1 0 0 1 0 
14 4
0 0 0 1 1 1 1 0 1 0 0 1 1 1 
13 2
1 1 0 0 0 0 1 1 0 0 0 0 0 
10 5
0 0 1 0 0 1 1 0 0 1 
9 5
1 1 1 0 1 1 1 0 0 
12 3
0 1 0 0 1 1 1 0 1 1 1 1 
14 2
0 0 0 1 1 0 1 1 1 1 1 1 1 1 
13 4
1 0 1 1 1 0 0 1 1 0 0 1 1 
13 4
1 0 0 1 0 0 0 1 0 0 1 0 1 
9 4
1 0 0 0 0 0 1 0 1 
13 2
1 1 0 1 0 0 0 0 1 1 1 1 1 
12 5
0 1 1 0 1 1 0 0 1 0 1 1 
14 2
0 1 0 1 0 1 0 1 1 0 0 1 1 1 
11 2
0 0 0 1 1 1 1 1 1 0 1 
12 4
1 0 1 0 1 0 1 0 1 0 0 1 
10 5
1 1 1 1 0 1 1 1 1 1 
7 3
1 1 0 0 1 0 1 
11 3
1 0 1 1 0 1 1 0 1 1 0 
14 4
0 1 0 1 0 1 1 1 0 1 0 0 1 1 
11 3
1 0 0 1 1 0 1 1 1 0 1 
11 4
0 1 0 1 0 1 0 1 0 0 0 
8 2
1 0 1 1 1 1 1 0 
10 2
1 0 1 1 1 1 1 1 0 1 
13 3
0 0 0 0 1 0 1 0 1 0 1 0 1 
7 2
0 1 0 1 1 0 0 
11 5
0 0 1 0 1 0 1 1 0 1 1 
14 5
1 0 1 1 1 0 1 1 1 1 1 0 1 0 
7 3
1 0 1 1 1 0 1 
11 3
0 0 0 1 1 1 1 1 0 0 1 
11 2
0 0 0 0 1 0 1 1 1 0 1 
6 2
0 1 1 0 1 1 
12 4
0 0 0 0 0 0 1 1 0 1 0 0 
11 5
1 0 1 1 1 1 1 0 0 1 1 
6 4
1 1 0 1 0 1 
12 5
0 1 1 0 0 1 0 0 0 1 1 0 
13 2
1 1 1 1 1 0 0 1 0 0 0 1 1 
8 5
1 1 1 0 0 1 0 1 
11 4
1 1 0 0 0 1 1 1 1 0 1 
6 5
0 0 0 0 1 1 
8 2
1 0 0 1 0 0 0 0 
10 3
0 0 0 1 0 1 0 1 0 1 
10 4
0 0 0 0 0 0 1 0 0 0 
8 5
0 0 0 0 0 1 0 1 
13 3
0 1 0 0 0 0 1 0 0 1 1 1 1 
7 4
0 0 0 0 0 0 1 
12 3
0 1 1 1 1 1 1 1 0 1 0 1 
8 3
0 0 0 0 0 1 1 1 
13 3
0 0 1 1 0 0 0 0 0 1 1 1 0 
13 5
0 0 1 0 0 0 0 1 1 1 1 0 0 
14 3
0 1 0 1 1 0 0 1 1 0 1 0 1 0 
10 4
1 0 1 0 0 0 0 0 1 0 
9 4
0 0 1 0 1 0 0 0 1 
11 4
1 1 1 1 0 1 1 0 1 1 1 
6 2
1 0 1 1 0 1 
14 4
0 0 1 1 1 0 0 1 0 1 0 1 0 0 
9 4
1 0 0 0 1 1 0 0 0 
10 3
1 1 1 1 1 0 0 1 0 0 
12 2
1 0 0 0 0 1 0 1 0 1 1 1 
10 4
1 1 1 0 0 1 0 0 1 0 
10 3
0 0 0 1 0 0 1 0 0 1 
6 5
1 1 1 1 1 0 
14 4
1 0 0 0 0 1 1 1 0 0 0 1 1 1 
13 3
0 1 0 1 1 1 1 0 0 0 0 1 1 
8 2
0 0 0 0 0 1 1 1 
8 3
0 0 1 0 1 1 0 1 
11 5
1 0 0 1 1 1 0 1 1 1 1 
12 2
0 0 0 1 0 1 0 0 0 0 0 1 
11 4
0 1 1 1 1 0 0 1 1 1 1 
7 3
0 1 0 1 0 0 0 
8 2
0 0 0 1 0 1 1 0 
Expected Solution for the given Testcases
1 0 1 0 0 0 
1 1 1 1 1 1 1 1 1 1 1 0 0 0 
1 1 1 0 1 0 0 0 0 
1 1 1 1 0 0 0 0 0 
1 1 1 1 0 1 1 0 0 0 0 0 0 
1 1 1 1 1 1 0 1 0 0 0 0 
1 1 1 1 0 0 1 0 1 0 0 0 0 
1 1 1 1 1 0 1 0 0 
1 1 0 1 0 1 1 1 1 0 1 0 
1 1 1 0 0 0 
1 1 0 1 0 1 0 1 0 1 0 0 
1 0 1 0 0 0 
1 1 1 1 1 1 1 1 1 0 0 0 0 
1 1 1 1 1 1 0 0 0 0 0 
1 1 1 1 1 0 0 0 
1 1 1 1 1 0 1 1 1 1 0 0 
1 0 0 1 0 0 0 0 0 
1 1 1 0 1 0 1 0 1 0 1 1 0 
1 1 1 1 1 1 1 0 1 0 
1 1 1 1 0 0 0 1 0 1 0 0 0 0 
1 1 1 1 1 1 0 1 0 0 
1 1 1 1 1 1 0 1 1 0 1 0 0 0 
1 0 0 0 0 0 
1 1 1 1 1 0 1 0 1 0 1 0 0 0 
0 0 0 1 0 1 0 
1 1 1 1 0 0 0 0 0 0 0 
1 1 1 0 1 0 1 0 1 0 0 
1 0 0 0 1 0 1 0 0 0 0 0 
1 1 1 1 1 0 1 0 0 
1 1 0 1 0 0 0 0 0 
1 1 0 0 1 0 0 0 
1 1 0 1 0 1 0 1 1 1 0 1 0 0 
1 1 0 0 1 0 1 0 0 0 0 0 0 
1 1 1 0 1 0 0 0 0 0 
1 1 1 1 1 1 0 0 0 
1 1 0 1 0 1 0 1 1 1 0 1 
0 1 0 1 0 1 1 0 1 1 1 1 1 1 
1 1 1 1 1 0 1 1 0 1 0 0 0 
1 1 0 1 0 0 1 0 1 0 0 0 0 
1 0 1 0 1 0 0 0 0 
1 1 1 0 0 0 1 0 1 0 1 1 1 
1 1 1 1 1 0 1 1 0 0 0 0 
1 1 0 1 0 1 0 1 0 1 0 1 0 1 
0 1 0 1 0 1 1 1 1 1 0 
1 1 1 1 1 0 0 1 0 0 0 0 
1 1 1 1 1 1 1 1 1 0 
1 1 1 1 0 0 0 
1 1 1 1 0 1 1 0 1 0 0 
1 1 1 1 0 1 0 1 0 1 1 0 0 0 
1 1 1 0 1 0 1 1 0 1 0 
1 1 1 1 0 0 0 0 0 0 0 
1 1 1 0 1 1 1 0 
1 1 1 0 1 1 1 1 1 0 
0 1 0 1 0 1 0 1 0 1 0 0 0 
1 1 0 1 0 0 0 
1 1 1 1 0 1 0 1 0 0 0 
1 1 1 1 1 1 0 1 1 1 0 1 0 0 
1 1 1 1 0 1 0 
1 0 1 0 1 0 1 1 1 0 0 
0 0 1 0 1 0 1 0 1 1 0 
1 1 0 1 1 0 
0 0 1 0 1 0 1 0 0 0 0 0 
1 1 1 1 1 1 0 1 1 0 0 
1 1 1 1 0 0 
1 1 1 0 1 0 1 0 0 0 0 0 
1 1 1 1 1 1 0 0 0 1 0 1 0 
1 1 1 1 1 0 0 0 
1 1 1 1 0 1 0 1 0 1 0 
1 1 0 0 0 0 
1 1 0 0 0 0 0 0 
1 0 1 0 1 0 1 0 0 0 
0 0 1 0 0 0 0 0 0 0 
1 0 1 0 0 0 0 0 
1 0 0 1 0 0 1 0 1 0 1 0 1 
0 0 1 0 0 0 0 
1 1 1 0 1 1 1 1 1 1 0 0 
0 0 1 0 1 0 1 0 
1 1 0 0 0 0 1 0 1 0 1 0 0 
1 0 1 0 1 0 1 0 1 0 0 0 0 
1 1 1 0 1 0 1 0 1 0 1 0 0 0 
1 1 0 0 1 0 0 0 0 0 
1 1 0 0 1 0 0 0 0 
1 1 1 1 1 1 1 1 0 1 0 
1 1 1 0 1 0 
1 1 1 0 1 0 1 1 0 0 0 0 0 0 
1 1 1 0 0 0 0 0 0 
1 1 1 1 1 1 0 0 0 0 
1 0 0 1 0 1 0 1 0 1 0 1 
1 1 1 1 1 0 0 0 0 0 
1 0 0 1 0 0 1 0 0 0 
1 1 1 1 1 0 
1 1 0 1 0 1 0 1 0 1 0 1 0 0 
1 1 1 0 1 0 1 0 1 0 1 0 0 
0 0 0 1 0 1 0 1 
1 1 0 1 0 1 0 0 
1 1 1 1 1 0 1 0 1 1 0 
0 1 0 1 0 0 0 0 0 1 0 0 
1 1 1 1 0 1 1 1 0 1 0 
1 1 0 0 0 0 0 
0 1 0 1 0 1 0 0 

SOLUTION

My solution can be found here.