MAKEPALAGAIN - EDITORIAL

PROBLEM LINK:

Contest
Practice

Setter: jeevanjyot
Testers: gamegame
Editorialist: aryanag_adm

DIFFICULTY:

1328

PREREQUISITES:

None

PROBLEM:

You are given a string A consisting of N lowercase Latin characters, where N is even. In one operation, you can swap A_i and A_{i+2}, for any 1 \leq i \leq N-2.

Determine whether it’s possible to convert A into a palindrome by performing operations of the type described above.

EXPLANATION:

Note that by swapping adjacent elements in a list, you can sort the list according to any ordering, by using any common algorithm such as bubble sort.

If i is even then i+2 is also even, else if i is odd then so is i+2. This implies that an element at an even index can never be swapped with an element with an odd index.

Therefore, we can use the operations to sort the even and odd indexed elements independently. Let the multiset of elements at even indices be X and the multiset of elements at odd indices be Y.

A string A is a palindrome if A_i = A_{N-i+1} for all i.

Let’s imagine how we would convert A into a palindrome:

  • We first need to set A_1 = A_N. 1 is odd and N is even. Therefore, we need to pick an element x_1 \in Y, and the same element x_1 from X (assuming it exists), and set A_1 = A_N = x_1. We can do this because we can sort the even and odd indices independently to have x_1 in those positions. We then delete x_1 from both X and Y.
  • We then need to set A_2 = A_{N-1}. 2 is even and N-1 is odd. Therefore, we need to pick x_2 \in X and the same element x_2 from Y (assuming it exists), and set A_2 = A_{N-1} = x_2. We then delete x_2 from both X and Y.
  • This process continues until we finish setting A_\frac{N}{2} and A_{\frac{N}{2} + 1}

Now, this process is successful if and only if we are able to pick x_i for all 1 \leq i \leq \frac{N}{2}. Therefore, we need \frac{N}{2} (not necessarily distinct) elements x_1, \cdots, x_{ \frac{N}{2}} such that both X and Y contain these elements. Since |X| = |Y| = \frac{N}{2}, this is equivalent to the multiset X = Y.

Therefore, if X = Y, we can convert A into a palindrome.

Now, if it is at all possible to convert A into a palindrome, then there must exist some valid sequence x_1, \cdots, x_{ \frac{N}{2}}, which implies X = Y.

Therefore, we can convert A into a palindrome if and only if X = Y.

We can easily check this as shown in the solution below. The idea is to calculate the frequency of each element in X and Y and then compare them.

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
//#define int long long
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int f[26][2];
        for(int i = 0;i<26;i++) f[i][0] = f[i][1] = 0;
        string s;
        cin>>s;
        for(int i = 0;i<n;i++){
            f[(s[i] - 'a')][i%2]++;
        }
        bool poss = true;
        for(int i = 0;i<26;i++) poss = poss && (f[i][0] == f[i][1]);
        if(poss) cout<<"YES\n";
        else cout<<"NO\n";
    }
}