SPOJ question IITKWPCI wrong answer

general
, , ,
1

I am getting WA in this question → SPOJ.com - Problem IITKWPCI

Here is my solution → mJsLSq - Online C++0x Compiler & Debugging Tool - Ideone.com

My algorithm creates an undirected graph having n vertices and positions i,j which are ‘good’ are connected with an edge. Then it finds connected components in this graph, sort data on the positions in each component separately and print out the resulting array. It would be helpful if anyone can give a case on which this algorithm fails, because I have tried many corner cases myself. Thanks in advance :slight_smile:

PS: I have assumed we can do multiple swaps between same pair of good positions. For example, if 1,2 is a good position pair, we can swap data at positions 1 and 2 multiple times. Please tell if this assumption is incorrect as well.

1 Like
2

Consider this test case.
Array Size : 5
[ 2 4 3 1 5]
No of swaps : 2
[1 3] and [2 3]
Your Programs gives o/p : [2 4 3 1 5]
However correct answer would be : [2 3 4 1 5]