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:
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();
}