Contest

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.

9 Likes

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

1 Like

Hello, please let me know the failed case

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

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

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 .

1 Like