PERMPAL - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

Given a string s[1\sim n], does there exist a permutation p of 1,2,\dots,n such that, if we let t[i]=s[p[i]], then t is palindrome?

EXPLANATION:

This problem is equivalent to: can we rearrange the characters of s into a permutation?

Let’s count the number of occurrences of every characters in a-z. For a char c, let cnt[c] be the number of times c occur in s.

If there are two chars c_1,c_2(c_1\ne c_2) such that both cnt[c_1] and cnt[c_2] is odd, then the answer is no.

  • To see this, consider any palindromic string t and any char c. Suppose t[i]=c.
  • If the length n of t is even, then t[n-i+1]=c. Since n is even, n-i+1 and i has different parity and hence i\ne n-i+1. Also n-(n-i+1)+1=i, so we say i and n-i+1 is a pair. Any pair must use the same character, so any character must occur an even number of times.
  • If the length n of t is odd, the above argument holds, too, except that the central char(t[\frac{n+1}{2}]) is matched with itself. In this case, this char appears an odd number of times, and is the only char that appears an odd number of times.
  • See figure below. n=7, pairs are (1,7),(2,6),(3,5), and t[4] is matched with itself, and hence appears an odd number of times.

image 1

  • In conclusion, if C is the number of chars c that cnt[c] is odd, and s can be arranged into a palindrome, then C\le 1.

The converse is also true: if there are at most 1 characters c with cnt[c] odd, then the answer is yes. Here is one of the constructions.

  • Let’s construct the permutation char-by-char. Let c iterate from a to z.
    • If cnt[c] is odd, we ignore c(that is, we consider c later). At most one such c exists.
    • We maintain two pointers l and r. Initially l=0,r=n+1. The permutation p[1\sim l] and p[r\sim n] is already filled.
    • We scan s. Each time we meet a c, say t[i]=c,
      1. if this is the 1,3,5,\dots,(odd) time we meet c, we assign it to the left: l\gets l+1 and p[l]\gets i;
      2. otherwise (this is the 2,4,6,\dots time we meet c), we assign it to the right: r\gets r-1 and p[r]\gets i.
      3. The picture below shows how we fill p when s=abdacbabdccba, i=b.

image 2

  • At last, in case that n is odd, we need to deal with the c where cnt[c] is odd. That’s easy: p[l+1\sim r-1] is unfilled, and we fill them by char c.
  • This is a valid answer. Time complexity: O(\sigma\cdot n). (\sigma=26)

ALTERNATIVE SOLUTIONS

This is a constructive problem. I think there’ll be many solutions. Please feel free to share your solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

Here is my solution CodeChef: Practical coding for everyone. please help me finding my mistake i am unable to find it.

Can someone please help me in finding the problem in my code. Here is the link CodeChef: Practical coding for everyone
Thanks in advance.

CodeChef: Practical coding for everyone Can anyone tell me what was wrong with my solution??

This is my solution https://www.codechef.com/viewsolution/17360282. It works only for subtask #1. can anyone please tell me what went wrong with my solution?

this is my solution CodeChef: Practical coding for everyone .
getting wrong answer

You are not outputting a correct permutation. The string generated by your permutation is not a palindrome.

Check your solution on the following test cases.

10
ggxggvvxpp
szzsbbhkhk
sjkxkjxsoo
oppdooopoo
ialilpijpp
efefxecxe
ppxuouxpp
vyuvvvyuh
ggwgzzzeg
ggywwwgwg

thank you so much. found the mistake :slight_smile:

My solution got 80/100 points. I don’t find my mistake, please help me.

Link: CodeChef: Practical coding for everyone

did you got AC?.. i have tried many TC’s but didnt got any where program fails.

Here is my solution CodeChef: Practical coding for everyone please help me find the error.

I got correct answers for the given test cases but still wrong answer, please help !!

https://www.codechef.com/viewsolution/50611192

My Solution: CodeChef: Practical coding for everyone

4th subtask is failing, can somebody tell me what’s wrong, I have tried various ways to test including fuzzing, I was not able to find any problem with my code.

Can anybody provide any pointers or testcases if possible to check.

Thank you.

My logic seems to be correct but it is not even passing subtask 1.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define int long long int
#define ll long long
#define double long double
#define f(i,a,b) for(int i=a;i<b;i++)
#define fm(i,a,b) for(int i=b-1;i>=a;i--)
#define input(a) for(auto &x:a) cin>>x
#define all(x) x.begin(),x.end()
#define rsort(c) sort(all(c)); reverse(all(c))
#define sz(c) (int)c.size()
#define print_v(a) for(auto x : a) cout << x << " "; cout << endl
#define print_p(a) for(auto x : a) cout << x.first << " " << x.second << endl
#define print_vij(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define print_mat(a) for(auto x:a){ print_v(x); } cout<<endl
#define fil(ar, val) memset(ar, val, sizeof(ar))  // 0x3f for inf, 0x80 for -INF can also use with pairs
#define max3(a,b,c) max(max((a),(b)),(c))
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
#define min3(a,b,c) min(min((a),(b)),(c))
#define min4(a,b,c,d) min(min((a),(b)),min((c),(d)))
#define ashutosh main
#define PY cout << "YES\n"
#define PN cout << "NO\n"
#define Py cout << "Yes\n"
#define Pn cout << "No\n"
#define se second
#define fe first
#define lc "\n"
 
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vc> vvc;
typedef map<int, int> mi;
 
const int mod = 1e9 + 7;
const int inf  = 1e18;
const int minf = - inf;
 
// ================================== take ip/op like vector,pairs directly!==================================
template<typename typC, typename typD> istream &operator>>(istream &cin, pair<typC, typD> &a) { return cin >> a.first >> a.second; }
template<typename typC> istream &operator>>(istream &cin, vector<typC> &a) { for (auto &x : a) cin >> x; return cin; }
template<typename typC, typename typD> ostream &operator<<(ostream &cout, const pair<typC, typD> &a) { return cout << a.first << ' ' << a.second; }
template<typename typC, typename typD> ostream &operator<<(ostream &cout, const vector<pair<typC, typD>> &a) { for (auto &x : a) cout << x << '\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout, const vector<typC> &a) { int n = a.size(); if (!n) return cout; cout << a[0]; for (int i = 1; i < n; i++) cout << ' ' << a[i]; return cout; }
template<typename T> using PQ = priority_queue<T>;
template<typename T> using QP = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// ===================================END Of the input module ==========================================
 
void codeInEditor() {
#ifndef ONLINE_JUDGE
	freopen("./Input.txt", "r", stdin);
	freopen("./Output.txt", "w", stdout);
	freopen("./Error.txt", "w", stderr);
#endif
}
 
// ............Solution starts here.............. //

 
void solve() {
		string s; cin>>s;
		int n=s.size();
		
		unordered_map<char,int>m;
		unordered_map<char,vector<int>>c_ind;
		for(int i=0;i<n;i++){
		    m[s[i]]++;
		    c_ind[s[i]].push_back(i);
		}
		bool odd=false;char odd_ele;
		for(auto i:m){
		    if(i.second%2){
		        if(!odd){
		            odd=true;
		            odd_ele=i.first;
		        }else{
		            cout<<-1<<endl;
		            return;
		        }
		    }
		}
		if (odd && n % 2 == 0) { cout<<-1<<endl;
		            return;}
	    if (!odd && n % 2 == 1) { cout<<-1<<endl;
		            return;}
		int l=1,h=n;
		vector<int>ans(n,0);
		if(odd){
		   int odd_ele_ind=c_ind[odd_ele][c_ind[odd_ele].size()-1];
	        ans[odd_ele_ind]=(n+1)/2;
	        c_ind[odd_ele].pop_back();
		}
		for(auto i:c_ind){
		    bool flag=true;
		   for(auto j:i.second){
		       if(flag)ans[j]=l++;
		       else ans[j]=h--;
		       flag=!flag;
		   }
		}
		cout<<ans<<endl;
 }
 
// ............ Code by ashutosh ................ //
 
signed ashutosh() {
	codeInEditor();
 
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
 
	while (t--) {
		solve();
	} 
 
	return 0;
}
 

I also checked my solution for these testcases and it works:
10
ggxggvvxpp
szzsbbhkhk
sjkxkjxsoo
oppdooopoo
ialilpijpp
efefxecxe
ppxuouxpp
vyuvvvyuh
ggwgzzzeg
ggywwwgwg