## 734 - The Programmer's Hex

Moderator: Board moderators

New poster
Posts: 2
Joined: Tue Oct 15, 2002 7:08 pm

### 734 - The Programmer's Hex

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!

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

### Programmers' Hex

This question is a real challenge...It is quite hard.

Can anybody suggest a good algorithm for this problem?

Thanks
:: HanWorks ::

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

### 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.
:: HanWorks ::

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
I think there are only 6^7= 279936 combinations, so brute force is ok.
There are probably many ways to minimize the amount of combinations you check, but I think that none of them will actually lead to polynomial time.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

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.

rammestain
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.

rammestain
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.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
If you look at hex F in the example, it only has two valid rotations, so you shouldn't try all six for it.

Also, think about which hex you want to put down first.
I'm always willing to help, if you do the same.

rammestain
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.