Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя fakeacc007

Автор fakeacc007, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

I am stuck on the same problem. Is your cycle decomposition too slow ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.