XOR_PAL-Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Setter: Shanu Singroha
Tester: Manan Grover, Lavish Gupta
Editorialist: Devendra Singh

DIFFICULTY:

1129

PREREQUISITES:

bitwise XOR operation

PROBLEM:

You are given a binary string A of length N.

You can perform the following type of operation on the string A:

  • Choose two different indices i and j (1\leq i,j\leq N);
  • Change A_i and A_j to A_i \oplus A_j. Here \oplus represents the bitwise XOR operation.

Find the minimum number of operations required to convert the given string into a palindrome.

EXPLANATION:

A palindrome is a string that reads the same forwards and backwards. If N is the length of the string A, then for each i from 1 to ceil(N/2), \:\:S_i = S_{N-i+1}
Let the count of indices i from i=1 to i=ceil(N/2) such that S_i != S_{N-i+1} be equal to cnt, then the answer is ceil(cnt/2) as each operation can decrease the count of such indices by at most 2.
Decrease count of such indices by 2
Let S_{j_1} ! = S_{N+1-j_1} this means that exactly one of these two values is 1, pick another similar pair where S_{j_2}! = S_{N+1-j_2}. Take the bitwise\: XOR of the two (out of these four) values which are equal to 1 and set each of them to 0.
Decrease count of such indices by 1
Let S_{j_1} ! = S_{N+1-j_1} this means that exactly one of these two values is 1. Take the bitwise\: XOR of these two values (S_{j_1}, S_{N+1-j_1}) and set each of them to 1.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
int main() {
  int t;
  cin >> t;
  assert( t <= 1000);
  while (t--) {
    int n ;
    cin >> n;
    assert(n <= N);
    string str;
    cin >> str;
    for (int i = 0 ; i  <  n ; i++) {
      assert(str[i] == '0' || str[i] == '1');
    }
    int diff = 0 ;
    // n --> 6  2  |||| n--> 7 2
    for (int i = 0 ; i  <  n / 2; i++ ) {
      if (str[i] != str[n - 1 - i])
        diff++;
    }
    cout << (diff + 1) / 2 << "\n";
  }
  return 0;
}
Editorialist's Solution 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define pll pair<ll, ll> 
#define vll vector<ll>
const int N=1e5+11,mod=1e9+7;
ll max(ll a,ll b) {return ((a>b)?a:b);}
ll min(ll a,ll b) {return ((a>b)?b:a);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n,ans=0;
cin>>n;
string s;
cin>>s;
for(int i=0;i<n/2;i++)
{
    if(s[i]!=s[n-1-i])
    ans++;
}
cout<<(ans+1)/2<<'\n';
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int test=1;
    cin>>test;
    while(test--) sol();
}
1 Like