## 317 - Hexagon

Moderator: Board moderators

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

### 317 - Hexagon

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
In the end, because I could not formulate an aglorithm, I tried brute force.

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

const int rowsz = {3, 4, 5, 4, 3, 3, 4, 5, 4, 3, 3, 4, 5, 4, 3};
const int pos = {
{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, rownum, rowblk, max;
bool used;

void input() {
int score, 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] = score;
comb[i * 9 + j * 3 + k] = score[j];
comb[i * 9 + j * 3 + k] = score[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]] == -1 || comb == rownum[pos[idx]])
&& (rownum[pos[idx]] == -1 || comb == rownum[pos[idx]])
&& (rownum[pos[idx]] == -1 || comb == rownum[pos[idx]]))
{
used = true;
rowblk[pos[idx]]++;
rownum[pos[idx]] = comb;
rowblk[pos[idx]]++;
rownum[pos[idx]] = comb[i];
rowblk[pos[idx]]++;
rownum[pos[idx]] = comb[i];
recur(idx + 1);
if (rowblk[pos[idx]]-- <= 1)
rownum[pos[idx]] = -1;
if (rowblk[pos[idx]]-- <= 1)
rownum[pos[idx]] = -1;
if (rowblk[pos[idx]]-- <= 1)
rownum[pos[idx]] = -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

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
Contact:
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.