Help Needed [!Important]

help
, ,
1

Problem Statement:

There are N students in a class, numbered from 1 to N. You are given M pairs of the form (A, B), for each such pair, students A and B are friends to each other.

Given a permutation of integers from 1 to N denoting the fashion in which students are currently arranged, you can perform the following operation any number of times (possibly 0):

  • Swap the positions of two students who are friends with each other.

Determine the minimum number of swaps to arrange the students in ascending order (i^{th} student at i^{th} position from start) or determine it is impossible to arrange.

So, this is the problem for which I had no solution. I have no approaches to solve the problem. Can anyone share the approach/solution (if there is any) to this problem?

I will provide samples if needed.

1 Like
2

@cubefreak777 , @iceknight1093 any ideas?

3

can u please provide some sample test cases

4

Sure. Here you go.

Consider this input format.

The First line of input contains two space-separated integers N and M denoting the number of students and number of pairs. The next line contains N space-separated integers denoting the fashion in which Students are currently seated. The next M lines contain a pair of integers each.

Sample Input 0:

5 2
5 4 3 2 1
1 5
2 4

Sample Output 0:

2

Explanation 0

\text{You can swap 1 with 5 and 2 with 4 to sort the sequence. Hence, 2 operations}

Sample Input 1:

4 2
1 3 2 4
1 2
3 4

Sample Output 1:

-1

Explanation 1

\text{There is no way to sort the sequence by performing the swaps in any order. Hence -1}.

I know these are obvious test cases. I can provide slightly more complex tests if needed.

5

Constraints on N and M ?

7

As of now, N,M \le 10^6. We’ll reduce them if we cannot arrive at an optimal solution for these limits.

8

Hey, what’s the time complexity of this?

I am providing another test case. Can you show how your approach works on this?

Sample Input 2:

5 5
5 4 3 2 1
1 2
1 5
2 3
3 4
4 5

Sample Output 2:

4

Explanation 2:

Swap (1, 5)
Arr: 1 4 3 2 5

Swap (2, 3)
Arr: 1 4 2 3 5

Swap (3, 4)
Arr: 1 3 2 4 5

Swap (2, 3)
Arr: 1 2 3 4 5
9

Unfortunately, this paper says that the problem is NP-complete.

The problem of token swapping on graphs was proved NP-complete and in fact APX-
hard [30], and further hardness results have appeared since then [8]. There are polynomial time algorithms for paths, cliques [11], cycles [23], and stars [2, 35, 33], and some other special cases, as discussed in more detail below.

2 Likes
10

FWIW, there was a somewhat similar problem in a recent AtCoder contest and the editorial for it is available: D - 8 Puzzle on Graph (the main difference is that only an “empty space” can be swapped, rather than any token with any other token).

11

I don’t immediately see a way to solve this for such huge constraints, I’m assuming you’re not looking for an \mathcal{O}(N!+M) time solution.
Also, may I ask for the problem link?

12

This problem was my idea. I submitted it to Codechef and it was rejected. I didn’t know it was NP-Complete so I mentioned I don’t know what the solution was.

The reason for rejection wasn’t mentioned so I wanted to know if there is any solution.

1 Like