317 - Hexagon

All about problems in Volume 3. 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
ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

317 - Hexagon

Post by ec3_limz »

Can anyone suggest an algorithm for this problem? It appears that brute force will take too much time, and I can't find an efficient algorithm yet....

Thanks.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Post by ec3_limz »

In the end, because I could not formulate an aglorithm, I tried brute force.

[cpp]#include <stdio.h>
#include <string.h>

const int rowsz[15] = {3, 4, 5, 4, 3, 3, 4, 5, 4, 3, 3, 4, 5, 4, 3};
const int pos[19][3] = {
{2, 5, 10},
{1, 5, 11},
{3, 6, 10},
{0, 5, 12},
{2, 6, 11},
{4, 7, 10},
{1, 6, 12},
{3, 7, 11},
{0, 6, 13},
{2, 7, 12},
{4, 8, 11},
{1, 7, 13},
{3, 8, 12},
{0, 7, 14},
{2, 8, 13},
{4, 9, 12},
{1, 8, 14},
{3, 9, 13},
{2, 9, 14}
};
int comb[27][3], rownum[15], rowblk[15], max;
bool used[27];

void input() {
int score[3][3], i, j, k;

for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
scanf("%d", &score[j]);

for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++) {
comb[i * 9 + j * 3 + k][0] = score[0];
comb[i * 9 + j * 3 + k][1] = score[1][j];
comb[i * 9 + j * 3 + k][2] = score[2][k];
}
}

void check() {
int sum, i;

sum = 0;
for (i = 0; i < 15; i++)
sum += rownum * rowsz;

if (sum > max)
max = sum;
}

void recur(int idx) {
int i;

if (idx >= 19) {
check();
return;
}

for (i = 0; i < 27; i++)
if (!used)
if ((rownum[pos[idx][0]] == -1 || comb[0] == rownum[pos[idx][0]])
&& (rownum[pos[idx][1]] == -1 || comb[1] == rownum[pos[idx][1]])
&& (rownum[pos[idx][2]] == -1 || comb[2] == rownum[pos[idx][2]]))
{
used = true;
rowblk[pos[idx][0]]++;
rownum[pos[idx][0]] = comb[0];
rowblk[pos[idx][1]]++;
rownum[pos[idx][1]] = comb[i][1];
rowblk[pos[idx][2]]++;
rownum[pos[idx][2]] = comb[i][2];
recur(idx + 1);
if (rowblk[pos[idx][0]]-- <= 1)
rownum[pos[idx][0]] = -1;
if (rowblk[pos[idx][1]]-- <= 1)
rownum[pos[idx][1]] = -1;
if (rowblk[pos[idx][2]]-- <= 1)
rownum[pos[idx][2]] = -1;
used[i] = false;
}
}

void process() {
memset(used, 0, sizeof(used));
memset(rownum, -1, sizeof(rownum));
memset(rowblk, 0, sizeof(rowblk));
max = 0;

recur(0);
printf("%d\n\n", max);
}

int main() {
int ncase, i;

#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

scanf("%d", &ncase);
for (i = 1; i <= ncase; i++) {
printf("Test #%d\n", i);
input();
process();
}

return 0;
}[/cpp]

As expected, I got TLE. I would appreciate any help.

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

Same Problem

Post by jandujar »

ec3_limz I have the same problem as you. I don't know the algorithm

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

some hints:
Using standard backtracking, you should be able to find 1296 solutions.
Actually, there are only 162 distinct solutions.
For each input cases, just check the 162 distinct solutions and find the maximum among them.

The trick is to know how to generate the 162 distinct solutions.
Notice that each number can contribute at most 9 times to the score.
Therefore, a base 10 system can uniquely represent each solution with a different score.

So if we run the backtrack on this testcase:
1 10 100
1000 10000 100000
1000000 10000000 100000000

Each distinct solution will guarantee to give a distinct score.

Actually, if you use that testcase, the answer will be 865775775.
We can actually derive a closed form solution form that number.

Post Reply

Return to “Volume 3 (300-399)”