FLIPPAL - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1173

PREREQUISITES:

None

PROBLEM:

Given a binary string S, in one move you can pick two indices and flip their values. Is it possible to make the final string a palindrome?

EXPLANATION:

You might notice that performing an operation on two indices with two different values essentially swaps the values at these indices. This is already enough to make S into a palindrome whenever:

  • N is odd; or
  • N is even and contains both an even number of 0's and 1's
Proof

When N is even, for S to be a palindrome both the 0's and the 1's must occur an even number of times, since each 0/1 is paired with another 0/1.

It’s fairly easy to see that if this condition holds, then just swapping 0's with 1's can make S into a palindrome. For example, if there are x occurrences of 0 and y of 1, then make the first x/2 and last x/2 characters of S 0 using swaps. This is a palindrome.

Further, any odd-length string can always be made a palindrome.
Either the 0's or the 1's must occur an odd number of times in an odd-length string; suppose it’s the 0's.
Use one swap to make a 0 the middle character. Now, the remaining part of the string needs to be an even palindrome, and we satisfy the condition above so we’re done.

As it turns out, these conditions are both necessary and sufficient.

Proof

Note that the given operation doesn’t actually change the parities of the 0's and 1's.
Let c_0 and c_1 be the respective counts. Then, one operation can change them as follows:

  • c_0 \to c_0 + 2 and c_1 \to c_1 - 2 (flipping two 1's to 0)
  • c_0 \to c_0 - 2 and c_1 \to c_1 + 2 (flipping two 0's to 1)
  • Leave c_0 and c_1 unchanged (swapping a 0 and a 1)

All three cases don’t change the parities. However, our earlier conditions only depended on the parities of c_0 and c_1. So, those cases are both necessary and sufficient.

Thus, the final solution is as follows: compute c_0 and c_1, the counts of 0 and 1 in the string. Then,

  • If both c_0 and c_1 are odd, the answer is “No”.
  • Otherwise, the answer is “Yes”.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    z, o = s.count('0'), s.count('1')
    if z%2 == 1 and o%2 == 1:
        print('NO')
    else:
        print('YES')
1 Like
2

Can anyone tell me what mistake I made in the code pasted below:

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n;
	    string s;
	    cin >> n >> s;
	    if(n == 2 && s[0] != s[1])   cout << "NO" << endl;
	    else    cout << "YES" << endl;
	}
	return 0;
}
3

You need to count number of swaps necessary for making the string a palindrome if n is even.
If the count is even then answer is yes else it is no.
I think you can try proving that yourself why it works.
However if n is odd, it is always possible to make the string a palindrome

1 Like
4

Can anyone tell me what mistake I made in this code ?
Its giving Wrong Answer.

#include <bits/stdc++.h>
using namespace std;
int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        char a[n];

        long long int i, c1 = 0, c0 = 0;

        cin >> a;

        for (i = 0; i < n; i++)
            (a[i] == '1') ? (c1++) : (c0++);

        // cout<<c1<<" "<<c0<<endl;
        
        if((c1%2==0 && c0%2==0)||(c1%2==0 && c0%2==1)||(c1%2==1 && c0%2==0))
        cout<<"YES\n";
        else
        cout<<"NO\n";
        
    }

    return 0;
}
5

how you can say that if n is odd it will be palindrome.

6

You need to choose two indices and swap them.
So you can pick one of these indices to be (n+1)/2 th index(1 indexing) and other index which u want to swap…it doesnt matter if (n+1)/2 th index is 1 or 0 if n is odd.
So whichever index you want to change from 0 to 1 or 1 to 0, you can always swap it with the (n+1)/2 th index.