PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Nishank Suresh
Testers: Utkarsh Gupta, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
2779
PREREQUISITES:
Counting inversions in a permutation
PROBLEM:
You are given N strings, all of length M. In one move, you swap swap the i-th character of two adjacent strings. Find the minimum number of moves to make every string a palindrome.
EXPLANATION:
For a string S of length M to be a palindrome, we must have S_i = S_{M+1-i} for each 1 \leq i \leq M.
In particular, for N strings to all be palindromes, the following must hold:
- Let C_i denote the string formed by the i-th characters of all the strings. That is, C_i = S_{1, i}S_{2, i}\ldots S_{N, i}. C_i is essentially the string formed by the i-th ‘column’ of the strings.
- Then, it must hold that C_i = C_{M+1-i} for every 1 \leq i \leq M.
Note that the given operation only allows us to move a character within its own column — it cannot be moved to a different column.
So, we only really need to compute the following:
- For each 1 \leq i \leq M, compute the minimum number of adjacent swaps required to make C_i = C_{M+1-i}, when swaps can be performed on both strings.
- Then, add this answer up for all pairs of columns.
- If any pair of columns cannot be made equal, the answer is -1.
Thus, we are left with a subproblem: given two strings S and T, find the minimum number of moves to make S = T, given that you can make adjacent swaps on either of them.
This can be solved with the help of an interesting observation: it is enough to only perform the swaps on one string, and not change the other!
Proof
Suppose we make swaps on both S and T, and they are equal in the end.
Let the last swap on T be (i, i+1).
Then, we can instead not perform this swap on T, and perform it as the last operation on S.
This still keeps S = T, while performing one less operation on T.
Repeatedly applying this will bring us to a state where S = T but no operations have been made on T, as required.
So, let’s keep T constant, and find the minimum number of swaps on S needed to make S = T.
This is a rather well-known problem, and you can find a tutorial here for example.
The basic idea is as follows:
- For each position i, compute the position where S_i should end up. Denote this by pos_i.
- This can be done somewhat easily as follows:
- Let’s look at each character individually.
- The first occurrence of ‘a’ in S should end up as the first occurrence of ‘a’ in T, the second occurrence in S should end up as the second occurrence in T, and so on.
- This applies to each character.
- Finding this can be done by simply knowing the positions of the characters in S and T.
- Once we know the positions where each character ends up, the problem essentially asks for the minimum number of swaps to reach this configuration.
- This is simply the number of inversions in the pos array, which can be computed in \mathcal{O}(N\log N) in a variety of ways.
A related problem you can try is 1430E.
TIME COMPLEXITY
\mathcal{O}(MN\log N) per test case.
CODE:
Setter's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#include <bits/extc++.h>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
auto invcount = [&] (const auto &v) {
Tree<int> T;
ll ret = 0;
for (int x : v) {
ret += T.size() - T.order_of_key(x);
T.insert(x);
}
return ret;
};
auto calc = [&] (const string &s, const string &t) {
int n = s.size();
vector<vector<int>> pos(26);
for (int i = 0; i < n; ++i) {
pos[s[i] - 'a'].push_back(i);
}
vector<int> ptr(26), reach(n);
for (int i = 0; i < n; ++i) {
int c = t[i] - 'a';
if (ptr[c] == (int)pos[c].size()) return -1LL; // Not possible
reach[i] = pos[c][ptr[c]];
++ptr[c];
}
return invcount(reach);
};
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<string> v(n);
for (auto &s : v) cin >> s;
ll ans = 0;
for (int i = 0; i < m-1-i; ++i) {
string a = "", b = "";
for (int j = 0; j < n; ++j) {
a += v[j][i];
b += v[j][m-1-i];
}
ll res = calc(a, b);
if (res == -1) {
ans = -1;
break;
}
ans += res;
}
cout << ans << '\n';
}
}
Tester (utkarsh_25dec)'s code (C++)
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
ll sumMN=0;
ll moves(string a,string b)
{
string c=a;
string d=b;
sort(all(c));
sort(all(d));
if(c!=d)
return -1;
vector <int> pos[30];
for(int i=0;i<b.length();i++)
pos[b[i]-'a'].pb(i);
int curr[30]={0};
vector <int> v;
for(int i=0;i<a.length();i++)
{
v.pb(pos[a[i]-'a'][curr[a[i]-'a']]);
curr[a[i]-'a']++;
}
ordered_set s;
int fun=0;
ll ans=0;
for(int i=0;i<v.size();i++)
{
ans+=(s.size()-s.order_of_key(mp(v[i],mod)));
s.insert(mp(v[i],fun++));
}
return ans;
}
void solve()
{
int n,m;
n=readInt(1,500000,' ');
m=readInt(1,500000,'\n');
sumMN+=(m*n);
assert(sumMN<=500000);
string arr[n+1];
for(int i=1;i<=n;i++)
{
arr[i]=readString(m,m,'\n');
for(int j=0;j<m;j++)
assert(arr[i][j]>='a' && arr[i][j]<='z');
}
int l=0,r=m-1;
ll ans=0;
while(l<r)
{
string a="",b="";
for(int i=1;i<=n;i++)
{
a+=arr[i][l];
b+=arr[i][r];
}
ll tmp=moves(a,b);
if(tmp==-1)
{
cout<<-1<<'\n';
return;
}
ans+=tmp;
l++;
r--;
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,500000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester (rivalq)'s code (C++)
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
template<typename T>
struct Fenwick{
vector<T> tree;
Fenwick(int n){
tree.resize(n);
}
T query(int i){
int sum=0;
while(i){
sum+=tree[i];
i-=i&(-i);
}
return sum;
}
void update(int i,int n,T val){
while(i<=n){
tree[i]+=val;
i+=i&(-i);
}
}
};
int solve(){
static int sum_n = 0;
int n = readIntSp(1,5e5);
int m = readIntLn(1,5e5);
sum_n += n*m;
vector<string> vec(n);
for(auto &i:vec){
i = readStringLn(m,m);
for(auto j:i)assert(j >= 'a' and j <= 'z');
}
assert(sum_n <= 5e5);
int ans = 0;
auto solve = [&](string s,string t){
string t1 = s,t2 = t;
sort(all(t1));
sort(all(t2));
if(t1 != t2)return false;
int n = s.length();
Fenwick<int> fn(n + 1);
set<int> st[26];
for(int i = 0; i < n; i++){
st[s[i] - 97].insert(i + 1);
fn.update(i + 1,n,1);
}
for(int i = 0; i < n; i++){
auto itr = *st[t[i] - 97].begin();
ans += fn.query(itr - 1);
fn.update(itr,n,-1);
st[t[i] - 97].erase(itr);
}
return true;
};
for(int i = 0; i < m/2; i++){
string s,t;
for(int j = 0; j < n; j++)s.push_back(vec[j][i]),t.push_back(vec[j][m - i - 1]);
if(!solve(s,t)){
cout << -1 << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t = readIntLn(1,5e5);
while(t--){
solve();
}
return 0;
}