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 ?
Auto comment: topic has been updated by aviroop123 (previous revision, new revision, compare).
https://codeforces.me/problemset/problem/441/D
What I would do is encode permutations as 48-bit integers in base $$$16$$$. This allows all checks and transitions to be done in $$$O(1)$$$ time, it’s a lot more memory efficient, and it would probably work ~10x faster.