10073 - Constrained Exchange Sort

[dh3014]

May anybody provide the correct answer for following test data?:

2
LKJIHGFEDCBA
KLJIHGFEDCBA

My output is:
Permutation #1
FCBAGJKFIBAGDKFEGHEICGHDJFICBADJKICBADJK

Permutation #2
HGABEHGECIKGJDBCIFGJDACIFKJDABIFKJDABCF

I want to know if my output sequence is the shortest.

[Caesum]

Is there some trick to this ? My attempts at a scoring function and some recursive look ahead dont seem to work very well.......

[junjieliang]

The letter 'L' at location l1 can be swapped with the letter at location l2 provided l1 ~ l2 = di and floor((l1 - 1) / di + 1) = floor((l2 - 1) / di + 1)for i = 1 | 2 | 3, where (d1, d2, d3, d4) = (1, 3, 6, 12).

what does the "~" symbol mean?

[Observer]

The memory limit for this problem is tight (~16 MB), so I don't think hashing is possible here. Instead, I believe A* is the only way to conquer this problem.

Now the problem is: how can I set up a good heuristic function? I have absolutely no idea. Can anyone give me some hints? Thanks in advance.

P.S. My own function, which deals with mis-put letters, gives me TLE all the time.

P.S.2. This "sorting method" looks like a variant of 15-puzzles....

[little joey]

I haven't solved this yet, but my idea on this is a 'man in the middle' approach (I don't know if that is the official name for it). This kind of approach kan be used for problems in which both the start and the target state are known (Rubick's Cube, Fifteen puzzle, Solitair, etc.). The idea is to simultaniously expand state-space from the start state (using regular moves) and from the target state (using backward moves) until you find a state that is in both expansions.

Say the problem has a fanning factor of 3 (every state leads on avg. to 3 new states) and you have a storage capacity of about a milion states, you can only go to about 13 moves deep before you run out of storage. But if you simultaniously expand from both sides, you can go about 12 moves deep for every side for a total of 24 or 25 moves within the same storage.

Of course the success of this approach leans heavily on the implementation details: the way you encode the states and store them, checking if you already visited a particular state, etc.

But again, I haven't solved this problem yet, so I'm not sure if this approach is feasible in this situation. I know of a Rubic's Cube solver that uses about 10Megs of memory taking only seconds to solve any scrambled cube using this approach.

[Observer]

Thanks joey (though I don't know how to implement it Bidirectional A*/BFS? Let me think about it....)

I tried to use some sort of Manhattan distance as my heuristic function. Still, TLE..... Any help plz???

[little joey]

Hmm. Forget it. Tried to implement it, but its definitly too slow...

[Adrian Kuegel]

Here some things that might interest you:
I know from my program, that there is at least one test case where you need 35 moves, but you will never need more than 38 for cases of the judge input.
I had to use a lot of tricks to avoid TLE in this problem, like I have stored the result of all permutations that are reachable from "AB...L" in at most 13 steps. My solution is definitely not nice, so perhaps someone with a better runtime can give better hints.

[Observer]

Thanks for your hint! Now I'm able to get Accepted in ~4 sec. Thx a lot !!!

(Btw: I've spent >1 hr on a stupid bug - forgetting to put things in my stack which checks if a state is repeated.... )

[Christian Schuster]

The problem can be interpreded as a three-dimensional version of the 15 Puzzle.

Code: Select all

    A---D
   /|  /|
  B---E |
 /| G/|-J
C---F |/
| H-|-K
|/  |/
I---

Possible exchanges are nothing but movements of letters to the (empty) "L" field. Using an IDA* search with the manhattan heuristics for the 15 Puzzle, my solution got AC in ~7 seconds without precalculating permutations. I basically re-used the solution from 10181, added the third dimension and changed the grid limits.

Adding a heuristics enhancement analogous to the 15-Puzzle's "Last Move" reduced runtime to ~3 seconds.

[Christian Schuster]

Ermmm... "0:00.1000" seems to be a quite strange time.

[ayon]

after more than 3 years you are being informed that ~ means difference, so l1 ~ l2 is equivalent to abs(l1-l2)

[gradientcurl]

Referring to the problem statement, the 3rd constraint on the swapping procedure:

"... can be swapped with the letter at location l2 provided l1 ~ l2 = di "

I am not sure of what the symbol ~ suppose to mean. Checked the wikipedia, it just says that it is a shorthand to say that there is a binary relation between l1 and l2. But why would l1~l2 be equated to di?

On a sidenote, are there any more problems on the UVa site that requires by A* or IDA*? I am solving all problems of this class in one go as I've learnt this algorithm recently. So far I've tried the 8-puzzle, 15-puzzle and knights in FEN.

[mf]

I am not sure of what the symbol ~ suppose to mean

Absolute difference of the two numbers. (link)

On a sidenote, are there any more problems on the UVa site that requires by A* or IDA*?

Try these problems:
529 Addition Chains
851 Maze
10798 Be wary of Roses
10833 Lunar Forest
11163 Jaguar King

[gradientcurl]

thanks mf, the info is useful