Binary Editorial - Unofficial

infinitepro · May 13, 2019, 12:53pm

PROBLEM LINK:

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]

EXPLANATION:

^1 Here S[x] \to S[k] determines the sub-array S[x], S[x + 1], S[x + 2], ..., S[k]
^2 The number of moves after which a given zero is right in front of a particular 1, allowing for it to be swapped with the 1 in the next move

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]. So the solution requires us to determine S[k] before determining 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 (x refers to the index of that 1 after the k^{th} move). 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 at the index x is k + 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 swapped with the prev 1, it cant be swapped with the next 1(constraint on Z), so delete it
    
    if(S[i] == 0){
        contiZero++;
        if(contiZero + M.size() > Z)
            M.pop_front(); //Since max number of 0's that can be pushed by any 1 is Z, we remove the front-most zero from the list 
    }else{
        contiZero = max(contiZero, Z); //Maximum number of zero's that can be swapped by a 1 is Z, so this check is made
        //Now I insert the values of all the zero's from contiZero i.e. the number of moves these zero's needs to be accessible be the 1 at index i(current index), Refer Part 1 if confused  
        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, since every element in M requires < Z moves to be accessible be the current 1

        //Now, this part corresponds to the number of moves it will take the zero's present in M to be accessible by the next 1(if any) Recall part 1 and 2 
        M.back()++;   
        for(int x = M.size() - 1; x >= 0; x--){
            if(M[x] <= M[x + 1]) M[x] = M[x + 1] + 1; //The zero corresponding to M[x] can be accessed only after the zero corresponding to M[x + 1] has been push back(Trivial verification, to be done by the reader)
            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.

Ping me in the comments section for any further clarifications.

anon55659401 · May 23, 2019, 12:58pm

This is a super hard problem. Thanks for the editorial God bless

jawa2code · May 25, 2019, 10:20am

Hello, please let me know the failed case

https://www.codechef.com/viewsolution/24264422

infinitepro · May 25, 2019, 10:23am

Did you try the debugging values I attached above?
Run your code against the random test case file, and compare it with the solutions attached. If still in doubt, I’ll be ready to help

avi141 · June 19, 2019, 12:43pm

Thank you for such a detailed editorial. After this post , i saw your submissions for JUNE challenge, your solutions are so simple and precise, learnt a lot, Thanks!!

The authors solutions , in case any one is interested BINARY

Intuition behind the solution LINK ,credit to @alei .