NONADJFLIP Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You are given a binary string S of length N. You can perform the following operation on S:

Pick any set of indices such that no two picked indices are adjacent.
Flip the values at the picked indices (i.e. change 0 to 1 and 1 to 0).

For example, consider the string S = 1101101.
Pick the indices \{1,3,6\}.
Flipping the values at picked indices, we get \underline{1}1\underline{0}11\underline{0}1→0111111.
Note that we cannot pick the set \{2,3,5\} since 2 and 3 are adjacent indices.

Find the minimum number of operations required to convert all the characters of S to 0.

EXPLANATION:

For each test case we have a binary string of length N.

Now as no adjacent bits can be flipped together. Three cases are possible:

  • When the string is already 0, then the number of minimum operations will be zero.
  • When no two adjacent bits are set. In this case all the set bits can be converted to 0 in 1 operation.
  • When the string contains adjacent set bits. In this case it can be shown that the answer will be 2 since all the odd-indexed set bits and even-indexed set bits can be identified as two different sets.

Evaluating all the above possibilities gives us the result.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

Time complexity should be O(N) since we have to iterate over the string.

2 Likes

Can anyone suggest me where my code went wrong:

#include<bits/stdc++.h>
using namespace std;

int main()   
{
	int t;
	cin>>t;      
	while(t--){
		int n;
		string str;
		cin>>n;
		cin>>str;
		int count = 0;
		for(int i=0;i<str.length();i++){
			if( str[i] == '1'){
				for(int j=i+1;j<str.length();j++){
					if( str[j] == '1' and abs(i-j) >= 2){
						str[j] = '0';
					}
				}
				count = count+1;
				str[i] = '0';
			}
		}
		cout<<count<<endl;
	}
	return 0;       
}

Can anyone help where I am getting wrong. I got 3AC out of 4. but Unable to find where I am getting wrong.

#include<bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
string str;
cin>>str;
bool flag1=false,flag2=false;
for(int i=0;i<N-1;++i){
if(str[i]==‘1’ || str[i+1]==‘1’){
flag1=true;
}
if(str[i]==‘1’ and str[i]==str[i+1]){
flag2=true;
}
}
if(!flag1){
cout<<“0”<<"\n";
return;
}
if(!flag2){
cout<<“1”<<"\n";
return;
}
if(flag2){
cout<<“2”<<"\n";
return;
}
}
int main() {
// your code goes here
int T;
cin>>T;
while(T–){
solve();
}
return 0;
}

Corrected in the editorial. Thank you for pointing it out.

1 Like

You are checking the number of 1s only for N-1 characters which fail the test case where we have 1 at the last
eg : 0000001,
Your code will give an output of 0.
Try Debugging this.

Thanks bro.