HELP IN SORTVS

help
1

PROBLEM
APPROACH 1
APPROACH 2
In the first approach, I wrote a brute force solution with complexity of O(mn^2), which is enough for the problem. For every i, if the i-th element is equal to i, I ignore it. Or else I search the whole vector for i and when it is found, I check if there is an unordered pair (i, j). If there exists such a pair, the cost is 0. Or else I increment it by 1.

In the second approach, I assumed (x, y) to be the nodes of a graph that are connected. After testing with a few cases, I came to a conclusion that the answer is simply the number of connected components minus 1.

I understand that the second approach may be wrong but I found no flaw in the first one. Please tell me what went wrong.

2

I also tried the approach 1, but the problem with that is two free swaps(done by robots) can be used to create a new swap which will also have cost 0. So there is a possibility to perform better than approach 1.

1 Like
3

How can a new swap be created?

4

for example (x1,y1) = (1,2) and (x2,y2) = (1,3)

then we can swap (2,3) by using following swaps -
swap(2,3) = swap(1,3), swap(1,2), swap(1,3)

2 Likes
5

CodeChef: Practical coding for everyone Can anybody check my answer and tell where i have done the mistakes.