Hey,
Are there any catches in this problem? Mine runs fine for the test inputs (except that D and E are exchanged), as well as a few other test cases I tried...
Still, I get WA... Anything to watch out for?
Thanks!
734  The Programmer's Hex
Moderator: Board moderators
Programmers' Hex
This question is a real challenge...It is quite hard.
Can anybody suggest a good algorithm for this problem?
Thanks
Can anybody suggest a good algorithm for this problem?
Thanks
:: HanWorks ::
734
Question: ACM 734 (The Programmer's Hex)
http://acm.uva.es/p/v7/734.html
I need help on how to solve ACM 734. This question is very tough.
Can anyone please tell me a good algorithm/method for solving this problem?
I posted a request on http://acm.uva.es/board/viewtopic.php?t=1525, but no one replied.
Does anyone have a good solution for ACM 734?
If so, please share with the programming community.
Thank You. Your help is appreciated.
http://acm.uva.es/p/v7/734.html
I need help on how to solve ACM 734. This question is very tough.
Can anyone please tell me a good algorithm/method for solving this problem?
I posted a request on http://acm.uva.es/board/viewtopic.php?t=1525, but no one replied.
Does anyone have a good solution for ACM 734?
If so, please share with the programming community.
Thank You. Your help is appreciated.
:: HanWorks ::
Gadalada,
Nope, there are no catches. Mine swapped D & E also, but got AC.
Ming,
What I did was basically try each permutation of hexagons on every peg and each rotation of all the hexagons. Of course if you just do this then you'll time out. Luckily there are a lot of configurations that don't work, so you can prune the search quite easily.
You'll also have to prune some configurations that are "sufficiently similar." For example, in the first input, hexagon B doesn't change if you rotate it. So it doesn't pay to check all of its rotations.
Nope, there are no catches. Mine swapped D & E also, but got AC.
Ming,
What I did was basically try each permutation of hexagons on every peg and each rotation of all the hexagons. Of course if you just do this then you'll time out. Luckily there are a lot of configurations that don't work, so you can prune the search quite easily.
You'll also have to prune some configurations that are "sufficiently similar." For example, in the first input, hexagon B doesn't change if you rotate it. So it doesn't pay to check all of its rotations.
I'm always willing to help, if you do the same.

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am
I use backtrack for solving this problem , but I got TLE,
In my backtrack soloution I check all permution of Hexs, and for each of this permutation I try to rotate hexs to get a right configuration and prune when I can't find a good rotation of a hex.
and if I see that a rotation of a hex is equal to itself then I don't rotate it.
please help me and give me a good prune
In my backtrack soloution I check all permution of Hexs, and for each of this permutation I try to rotate hexs to get a right configuration and prune when I can't find a good rotation of a hex.
and if I see that a rotation of a hex is equal to itself then I don't rotate it.
please help me and give me a good prune

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am
I use backtrack for solving this problem , but I got TLE,
In my backtrack soloution I check all permution of Hexs, and for each of this permutation I try to rotate hexs to get a right configuration and prune when I can't find a good rotation of a hex.
and if I see that a rotation of a hex is equal to itself then I don't rotate it.
please help me and give me a good prune
In my backtrack soloution I check all permution of Hexs, and for each of this permutation I try to rotate hexs to get a right configuration and prune when I can't find a good rotation of a hex.
and if I see that a rotation of a hex is equal to itself then I don't rotate it.
please help me and give me a good prune

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am
I used your hint , but still I'm getting TLE
for the first pig, I choose a hex that have at least one commen number with all other hexs,
and I store the pervious rotation of a hex, and every time I check the new rotation of a hex with pervious rotation of that, if it is same with one of them I break.
help me please
for the first pig, I choose a hex that have at least one commen number with all other hexs,
and I store the pervious rotation of a hex, and every time I check the new rotation of a hex with pervious rotation of that, if it is same with one of them I break.
help me please