734 - The Programmer's Hex

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

734 - The Programmer's Hex

Post by Gadalada » Tue Oct 15, 2002 7:11 pm

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!

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

Programmers' Hex

Post by Ming Han » Tue Feb 25, 2003 10:56 am

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

Can anybody suggest a good algorithm for this problem?

Thanks
:: HanWorks ::

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

734

Post by Ming Han » Mon Mar 10, 2003 12:58 pm

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

Post by makbet » Mon Mar 10, 2003 6:11 pm

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:

Post by Ryan Pai » Fri Aug 27, 2004 3:06 pm

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.
I'm always willing to help, if you do the same.

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain » Fri Jun 02, 2006 12:08 pm

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

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain » Fri Jun 02, 2006 12:09 pm

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

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

Post by Ryan Pai » Fri Jun 02, 2006 4:52 pm

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

Post by rammestain » Fri Jun 02, 2006 5:46 pm

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

Post Reply

Return to “Volume 7 (700-799)”