How to solve this problem?

Правка en1, от aviroop123, 2019-01-31 09:22:53

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 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский aviroop123 2019-01-31 09:27:51 67 (published)
en1 Английский aviroop123 2019-01-31 09:22:53 594 Initial revision (saved to drafts)