There was a problem which I encountered in an OT which reads as follows,“Given two strings A and B,its always possible to transform string B to string A by doing some (possibly zero) swap operations in string B,find the minimum number of swap operations required to transform the string B to string A”.I saw the editorial and it was dealt using some cycles in graph concept,it’ll be very helpful if someone can share the approach how to tackle this problem…
Ex:A=“aabc”
B=“aacb”
o/p:1
Could you provide the original problem and editorial? Because the problem you’ve stated can be NP-hard which I don’t think is the case since they are using cycles.
The constraint that has to hold is that for every mismatch in two strings at position i there is no position j such that s_j = s_i \lor t_j = t_i, so in case this is not fulfilled it becomes an NP-hard and it’s probably going to be wasted time solving it (chances of this appearing in any major contest are very low, so you’d be better off solving some polynomial problems).
In case the first condition holds, it’s a simple problem and can be translated to the following:
Given permutation P what is the minimum number of swaps to transform it into P'?
This problem can be solved as follows:
For every number at position i create a directed edge from P_i to P'_i. The final answer is the number of the length of permutation minus number of connected components. How do we conclude this?
Notice that each of the connected components is a cycle. How to prove it? Let’s sup$pose there is a component that is not a cycle, that would mean that either one of the two holds:
- Some vertex in a component has an indegree > 1
- Some vertex in a component has an indegree < 1
All of these are impossible to happen due to the restriction of uniqueness and the way we constructed the graph. So if the first was true that would mean that there are i and j such that P_i and P_j both point to the same element, which further means that P'_i = P'_j. Contradiction.
Similarly if the second holds, we arrive that for some i and j the first holds, since we have proven that indegree of some other vertex can’t be > 1, the indegree of this vertex can’t be < 1. You can work this one out on your own, it’s not tough.
So we leave out the cases such as:
X_1 - X_2 - X_3 or X_1 - X_2 - X_3 - X_4 - X_2, since clearly in the first case X_1 has an indegree 0, while in the second one X_2 has an indegree 2.
So we end up with a couple components of the following cyclic form:
X_1 - X_2 - X_3 - ... - X_n - X_1
This expression is the same as saying take indices i_1, i_2, ..., i_n and saying for each of these indices P_i = X_i and P'_i = X_{(i + 1)}. Ofc there is a special case for P'_n = X_1, because it’s cyclic.
So how many swaps does it take to transform X_1, X_2, ..., X_n into X_2, X_3, ..., X_1? The same number of steps as transforming the permutation 1, 2, ..., n into its (n - 1)_{th} cyclic shift which is (n - 1).
If you think that we can do better than this we would have to swap elements between two components. So if you do swap i and j which belong to different components, none of them will end up in correct places so the answer for both still remains the same, but you’ve done an extra step. What’s more they’ll both have to return to their starting components in the final arrangement, so you need to do at least one extra swap, so the total answer increases by at least 2 which is obviously not optimal. So in conclusion this idea doesn’t help.
So in total if we say we have k connected components, with sizes sz_i for every 1 \leq i \leq k. Then the answer is \sum_{i=1}^{k}(sz_i - 1) = \sum_{i = 1}^{k}(sz_i) - k = N - k.
I hope this helps you understand the general idea.
1 Like