Hi, beautiful people of Codeforces!
I've been stuck on this problem for quite a long time: https://stackoverflow.com/questions/51796237/minimum-number-of-swaps-to-convert-a-string-to-palindrome
The question is pretty straightforward in the sense that we just need to make some character swaps to make the given string palindrome, if possible, with the catch that we can swap any two characters which need not be adjacent (unlike the problem: https://www.codechef.com/problems/ENCD12)
I've thought deeply into the possibility of applying concepts from permutation graph and cycle decomposition but it's all been in vain for now :( Yet another possibility is to run a BFS from the starting word exploring all possible swap states but this would be too slow.
I would greatly appreciate if any of you geniuses can provide me with some more hints as to how can I approach this problem in a more efficient manner.
Thank you so much for your time!
Consider the ends of the current string let's say current string is a???b in the optimal solution either both of these ends are a or both of these ends are b, and we have to place the character at the ends which has least cost at that instant so it's a greedy algorithm choose the character to be placed at the end which has least cost and then our string length decreases by 2 , I don't have a proof for this though.
I am stuck on the same problem. Is your cycle decomposition too slow ?
*is it Nots0fast ?
I think the accepted answer of the stackoverflow question provides some good intuition.
Let's consider even $$$n$$$. For all pairs of positions $$$(i, n-i-1)$$$ for which $$$s_i \neq s_{n-i-1}$$$ add an undirected edge in $$$G$$$ from $$$s_i$$$ to $$$s_{n-i-1}$$$. This ultimately forms a multigraph $$$G$$$ of $$$\Sigma$$$ nodes. Now, it seems that solving the problem corresponds to decomposing this multigraph into as many edge-disjoint cycles as possible.
It seems that the discussion here suggests that this problem is NP-complete (although I can't verify the source). However, this only says that one can't expect a solution polynomial in $$$\Sigma$$$; maybe there are solutions polynomial in the string's length but exponential in $$$\Sigma$$$.
Please correct me if I'm wrong.
Thank you for your answer. Yes, I got to the part of "decomposing this multigraph into as many edge-disjoint cycles as possible". But i am not very sure how to proceed from there. I do not think there is a solution polynomial in string's length. I think I came across multiple sources saying that the problem is APX hard while surfing the net. Also note that https://www.researchgate.net/publication/309543777_A_Dynamic_Programming_Approach_for_the_Max-Min_Cycle_Packing_Problem_in_Even_Graphs this paper gives a solution to the exact problem, but as far as I understood their algorithm is not polynomial, and also seems too slow (I have not implemented it tho).