aviroop123's blog

By aviroop123, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aviroop123 (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.