Minimum number of swaps to change permutation to identity permutation

Revision en2, by aviroop123, 2019-01-31 09:27:51

Brief problem description : Given a permutation of length n <= 12 and a list of m <= n*(n-1)/2 possible swaps, what is the minimum number of swap operations required to change the permutation to an identity permutation ( i.e p_1 = 1, p_2 = 2, ... p_n = n). Here's the problem link : https://wcipeg.com/problem/coci092p5.

The editorial uses A* algorithm with heuristics to solve this problem. I was only able to come up with a 90 pts (here's the code) solution using A*. Can anyone share any idea on how to get 100 pts efficiently ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English aviroop123 2019-01-31 09:27:51 67 (published)
en1 English aviroop123 2019-01-31 09:22:53 594 Initial revision (saved to drafts)