10073  Constrained Exchange Sort
Moderator: Board moderators
10073  Constrained Exchange Sort
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.
2
LKJIHGFEDCBA
KLJIHGFEDCBA
My output is:
Permutation #1
FCBAGJKFIBAGDKFEGHEICGHDJFICBADJKICBADJK
Permutation #2
HGABEHGECIKGJDBCIFGJDACIFKJDABIFKJDABCF
I want to know if my output sequence is the shortest.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
10073 pls explain
what does the "~" symbol mean?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).
10073 Constrained Exchange Sort
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 misput letters, gives me TLE all the time.
P.S.2. This "sorting method" looks like a variant of 15puzzles....
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 misput letters, gives me TLE all the time.
P.S.2. This "sorting method" looks like a variant of 15puzzles....
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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 statespace 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.
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.
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???
I tried to use some sort of Manhattan distance as my heuristic function. Still, TLE..... Any help plz???
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.
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.
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.... )
(Btw: I've spent >1 hr on a stupid bug  forgetting to put things in my stack which checks if a state is repeated.... )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
The problem can be interpreded as a threedimensional version of the 15 Puzzle.
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 reused the solution from 10181, added the third dimension and changed the grid limits.
Adding a heuristics enhancement analogous to the 15Puzzle's "Last Move" reduced runtime to ~3 seconds.
Code: Select all
AD
/ /
BE 
/ G/J
CF /
 HK
/ /
I
Adding a heuristics enhancement analogous to the 15Puzzle's "Last Move" reduced runtime to ~3 seconds.
Last edited by Christian Schuster on Tue Feb 22, 2005 1:46 pm, edited 1 time in total.
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
 gradientcurl
 New poster
 Posts: 16
 Joined: Mon Jun 26, 2006 9:33 am
 Contact:
something to clarify
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 8puzzle, 15puzzle and knights in FEN.
"... 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 8puzzle, 15puzzle and knights in FEN.
Absolute difference of the two numbers. (link)I am not sure of what the symbol ~ suppose to mean
Try these problems:On a sidenote, are there any more problems on the UVa site that requires by A* or IDA*?
529 Addition Chains
851 Maze
10798 Be wary of Roses
10833 Lunar Forest
11163 Jaguar King
 gradientcurl
 New poster
 Posts: 16
 Joined: Mon Jun 26, 2006 9:33 am
 Contact: