317 - Hexagon

[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]

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]

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

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