BINBASBASIC - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: S.Manuj Nanthan
Tester: Tejas Pandey
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given a binary string S and an integer K. In one operation, you can pick any bit and flip it, i.e turn 0 to 1 or 1 to 0. Can you make the string S a palindrome using exactly K operations?

QUICK EXPLANATION:

  • Let Z be the minimum number of operations required to convert the string into a palindrome.
  • The answer is NO if Z>K.
  • If Z \leq K and N is odd, the answer is YES.
  • If Z \leq K and N is even, the answer is YES if K-Z is even. Otherwise, the answer is NO.

EXPLANATION:

What is a palindrome?

A binary string S of length N is said to be a palindrome if S_i = S_{N-i+1} for 1 \leq i \leq N.

Minimum operations required

Let us find the minimum number of operations required to convert S into a palindrome.

While traversing the string, we check if S_i \neq S_{N-i+1}. In this case, we can flip S_i using one operation and increment the count of operations.

The final count of operations is the minimum number of operations required.

Note that you do not need to traverse the whole string. You can find the count by traversing the first half of the string.

If the minimum number of operations required is greater than K, we can never make the string palindrome and the answer is NO.

Handling extra operations

We know that we need to apply exactly K operations on the string.

Suppose that we convert the string into a palindrome using minimum operations and we still have X operations left (X>0). There are two possible cases:

  • String is of odd length: We apply all the X operations on the middle character of the string. Since the string is of odd length, it would remain a palindrome, no matter how many times we flip the middle character. Thus, the answer is YES in this case.
  • String is of even length: If we flip a character, we need to flip it back so that the string remains a palindrome. This means that, to keep it a palindrome, we can only apply an even number of operations on the string. Thus, the answer is YES if X is even and NO otherwise.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
for _ in range(int(input())):
    n,k=map(int,input().split())
    s=input()
    need=0
    for i in range(n//2):
        if(s[i]!=s[n-i-1]):
            need+=1
    if(need > k):
        print("NO")
    else:
        if(n%2 or (n%2==0 and ( (k-need)%2==0))):
            print("YES")
        else:
            print("NO")
Tester's Solution
#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		int cnt = 0;
	    for(int i = 0; i < n/2; i++)
	        cnt += (s[i] != s[n - 1 - i]);
	    if(k < cnt) cout << "NO\n";
	    else {
	        if(n&1) cout << "YES\n";
	        else {
	            if((k - cnt)&1) cout << "NO\n";
	            else cout << "YES\n";
	        }
	    }
	}
	return 0;
}
Editorialist's Solution
#include <iostream>
#include <string.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n, k;
	    cin>>n>>k;
	    string s;
	    cin>>s;
	    int reqd = 0;
	    for(int i = 0; i<n/2; i++){
	        if(s[i]!=s[n-1-i]){
	            reqd++;
	        }
	    }
	    if(reqd>k){
	        cout<<"NO";
	    }
	    else if(n%2 || (n%2==0 && (k-reqd)%2==0)){
	        cout<<"YES";
	    }
	    else{
	        cout<<"NO";
	    }
	    cout<<endl;
	}
	return 0;
}

In the question it should be mentioned that we can flip single bit multiple times

1 Like

It is mentioned that you can pick any bit in an operation. This implies that the bits which have been flipped before can also be picked.

why (k-need)%2==0 we have to consider , I didn’t understand why you wrote

1 Like

After applying Z operations we are still left with (K-Z) operations. Now 2 cases arise from it.

Case 1: When (K-Z) is even. Let’s say it is 4. So we need to apply 4 more operations to the string which after Z operations had already become a palindrome. So we keep changing the starting and ending string until the 4 operations are exhausted. this way the string will remain palindrome.

Case 2: When (K-Z) is odd. let’s say 1. then we can change only one bit in the already palindrome string. After 1 operation the string can’t remain palindrome.( If n was odd then it can be possible but in this case, n is even).

Hence when (K-N) is odd then it’s NO else it’s YES.

1 Like
import java.io.*;
import java.lang.Math;


class BINBASBASIC{

	public static void main (String args[]) throws  IOException
	{
		
			BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 	
			int t = Integer.parseInt(in.readLine());
			
			while(t>0)
			{			
				int n = Integer.parseInt(in.readLine());
				int k = Integer.parseInt(in.readLine());
				String s = in.readLine();
				int c=0;
				
				for(int i=0, j=n-1; i<n && j>0; i++,j--){
					if(s.charAt(i)!=s.charAt(j)){
						c++;
					}
					
				}
				
				if(c<=k)
				{
					System.out.println("YES");
				}
				else{
					System.out.println("NO");
				}
				
				t--;
			}
		} 
}

// https://www.codechef.com/FEB221C/problems/BINBASBASIC```


Can someone tell me why I am getting runtime error in this solution?

Ok got it , thank you

because if we flip any element twice it will be same as the initial value, subtracting need so that we string is palindrome

consider,
string = 1000 , k =3
now . need = 1
1001 becomes palindrome
if we now toggle a single digit twice the number will remain the same
for example : 1001 → 1011 → 1001

Thank you

1 Like