10051 - Tower of Cubes

[kiha]

Hey

I read that the LIS algorithm is necessary to solve this :/ But you can determine the height of tallest tower with a greedy algorithm, I suppose. I haven't even tried it yet... However, I can't understand the way the LIS algorithm should be used here. Can somebody please explain it to me? Thanks in advance

[platizon]

hi all

i just submitted 10051 (tower of cubes) and got WA... don't know why...

can someone give me the tricky case or maybe some hard test case??

really need help...

please reply

thanks a lot

[skylander]

i tried to solve this problem using dynamic programming (lis)...i am not very sure if my algo is correct or if it is even considered dp, but it works as follows:

i have a 2d array tower(i, j) which is set to true or false, depending on whether i can form a tower of height i, with the color j facing up...

then for every kth cube read from the file, i look for the tallest possible height h that the cube k can be added on, if i can add it on, i will set tower(h+1, color of cube k's upward face) to true,also, i add the cube k, and its upward face to another similar 2D array so that i can print the result l8r...

after i finish going through all the cubes, i look for the highest height that can be reached and print the sequence of cubes...

i tried my program with a several test case that i can think of and the sample input, it produces the correct output....since the judge gives me the WA, i must have made soime mistakes somewhere...below is my c code....hope somebdy can provide some test cases for me to spot my mistakes or point out the problem with my algo....thx for any help

[c]
/* @BEGIN_OF_SOURCE_CODE */
#include <stdio.h>
#include <string.h>

/* @JUDGE_ID: XXXXX 10051 C "" */

#define MAX_CUBES 512
#define CUBE_FACES 6
#define MAX_COLORS 128

int opposite_face(int);
int opposite_color(int, int);
int print_seq(int[MAX_CUBES][MAX_CUBES], int, int);

char cubes[MAX_CUBES][CUBE_FACES];

char face_str[CUBE_FACES][7] = {"front", "back", "left", "right", "top", "bottom"};

int main(void)
{
int n, case_count = 0;

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
while (scanf("%d\n", &n) == 1)
{
int i, j, k;
char found;
char tower[MAX_CUBES][MAX_COLORS];
int sequence[MAX_CUBES][MAX_CUBES];

if (n == 0)
break;

case_count++;
printf("Case #%d\n", case_count);

memset(cubes, 0, sizeof(cubes));
memset(tower, 0, sizeof(tower));
memset(sequence, 0, sizeof(sequence));

for (i=0;i<n;i++)
{
for (j=0;j<CUBE_FACES;j++)
scanf("%d ", (int *)&cubes[j]);
scanf("\n");
}

for (i=0;i<n;i++)
{
0&&printf("trying cube %d...\n", i);
found = 0;
for (j=i-1;j>=0;j--)
{
0&&printf(" taking a look at length %d:\n", j);
for(k=0;k<CUBE_FACES;k++)
{
if (tower[j][(int)cubes[k]] == 1)
{
0&&printf(" found matching color: %d\n", (int)cubes[k]);
tower[j + 1][opposite_color(i, k)] = 1;
sequence[j + 1][opposite_color(i, k)] = i * 1024 + opposite_face(k);
found = 1;
}
}
if (found == 1)
break;
}

if (found == 0)
{
0&&printf(" none found, register as length 0\n");
for(k=0;k<CUBE_FACES;k++)
{
if (tower[0][opposite_color(i, k)] == 0)
{
tower[0][opposite_color(i, k)] = 1;
sequence[0][opposite_color(i, k)] = i * 1024 + opposite_face(k);
}
}
}
}

found = 0;
for (i=n;i>=0;i--)
{
for (j=0;j<MAX_COLORS;j++)
if (tower[j] == 1)
{
print_seq(sequence, i, j);
found = 1;
break;
}

if (found == 1)
break;
}

printf("\n");
}

return 0;
}

int print_seq(int seq[MAX_CUBES][MAX_CUBES], int len, int color)
{
int prev_face, prev_color, prev_cube;
int i, j;
int temp[MAX_CUBES] = {0};

j = 0;

prev_color = color;
prev_cube = seq[len][prev_color] / 1024;
prev_face = seq[len][prev_color] % 1024;
temp[j++] = seq[len][prev_color];

printf("%d\n", len + 1);

0&&printf("len %d cube %d face %d color %d\n", len, prev_cube, prev_face, prev_color);

for (i=len-1;i>=0;i--)
{
prev_color = opposite_color(prev_cube, prev_face);
prev_cube = seq[prev_color] / 1024;
prev_face = seq[prev_color] % 1024;
temp[j++] = seq[prev_color];
}

for (i=j-1;i>=0;i--)
{
prev_cube = temp / 1024;
prev_face = temp % 1024;
printf("%d %s\n", prev_cube + 1, face_str[prev_face], cubes[prev_cube][prev_face], cubes[prev_cube][opposite_face(prev_face)]);
}

return 0;
}

int opposite_face(int face)
{
switch (face)
{
case 0: return 1;
case 1: return 0;
case 2: return 3;
case 3: return 2;
case 4: return 5;
case 5: return 4;
}

return -1;
}

int opposite_color(int cube, int face)
{
return cubes[cube][opposite_face(face)];
}

/* @END_OF_SOURCE_CODE */
[/c]

[jackie]

I use DP algorithm and AC in 0.3 sec.

there is only max 100 colors

memorize the max length for each color (making this color as bottom of the tower sequence)

for the cube new coming
for each top bottom pair
put it after the top color(last cube's bottom color memorize in the array)
see whether we can increase the bottom color's length
if YES
update the length
memorize the cube number and the front face for the ouput
else
ignore this pair

output the max length

output the sequence and front face using the index numbers memorized in the programe

English is not my first language .
Sorry for that.

[kiha]

Oh God

really, now I see
So stupid was I ...
AAAA

Thanks very much!
Kind regards

[milo]

can somebody put some interesting test cases, because i don't realize where is my error and i am desperate , thanks

[jagadish]

Used DP and got WA ..cant see where the catch is .
... someone give me critical I/O please...

Code: Select all

12
4 7 18 16 14 16 
7 13 10 2 3 8 
11 20 4 7 1 7 
13 17 12 9 8 10 
3 11 3 4 8 16 
10 3 3 19 10 8 
14 17 12 3 10 14 
2 20 5 18 19 5 
16 11 14 7 12 1 
17 14 3 11 17 2 
6 6 5 8 17 6 
7 10 14 18 5 16 

6
3 6 15 8 15 5 
4 11 8 9 17 19 
9 5 4 12 15 20 
13 1 17 9 20 13 
7 7 15 20 16 11 
15 19 8 2 18 3 

8
18 13 13 17 2 1 
7 2 6 10 5 20 
1 10 12 18 18 12 
2 16 10 8 8 17 
18 14 7 6 7 4 
20 5 9 12 13 10 
4 20 11 9 9 16 
1 10 17 4 19 6 

9
7 12 2 16 20 9 
5 9 2 11 14 1 
15 5 5 15 8 17 
4 12 8 6 20 17 
13 12 18 9 16 8 
15 2 19 16 10 18 
16 14 19 9 4 12 
9 10 17 5 4 4 
14 19 7 1 5 19 

12
9 9 10 18 18 17 
5 4 11 4 11 20 
13 6 5 11 6 20 
15 7 10 3 3 5 
18 8 16 5 9 12 
3 9 20 4 7 9 
1 3 12 11 6 2 
2 11 19 6 1 17 
5 7 3 6 9 17 
3 19 5 18 3 5 
1 17 13 20 20 11 
9 12 14 12 2 11 

100
14 15 1 4 20 2 
20 17 20 14 14 9 
11 16 7 7 5 1 
11 5 17 3 17 8 
6 17 20 19 8 13 
9 13 20 10 17 11 
3 8 7 2 14 13 
2 16 20 20 2 5 
20 12 1 8 6 9 
8 11 5 19 1 5 
3 10 17 2 11 5 
13 13 13 11 6 6 
3 20 1 3 19 14 
19 11 5 11 10 2 
20 17 13 16 15 5 
20 10 14 17 11 16 
1 3 20 5 14 6 
2 8 5 14 2 15 
7 20 5 3 3 7 
5 2 3 9 9 10 
13 9 19 19 17 9 
14 9 4 14 14 9 
11 15 8 7 9 10 
1 7 9 18 10 11 
4 14 4 18 14 13 
7 6 13 17 16 9 
18 10 17 1 15 2 
1 5 9 8 11 9 
17 3 15 18 20 4 
20 3 9 4 1 2 
8 19 20 12 16 15 
20 13 16 8 5 10 
10 5 6 10 4 16 
18 1 19 12 10 10 
8 9 13 16 4 5 
10 11 3 1 2 10 
7 13 2 3 1 18 
4 2 2 10 11 6 
17 8 18 15 11 7 
5 18 15 9 6 19 
13 7 1 7 7 15 
17 13 19 10 7 11 
8 11 12 1 12 14 
18 8 13 7 15 16 
13 11 13 20 11 10 
10 15 16 2 1 14 
8 9 19 7 11 5 
17 18 7 1 10 18 
6 20 18 19 6 4 
14 19 14 18 10 4 
8 19 18 15 12 10 
1 20 19 19 6 9 
15 14 18 2 14 19 
11 20 18 20 10 4 
3 15 14 8 12 3 
3 11 13 12 18 16 
2 18 15 12 8 12 
12 2 18 1 15 11 
19 6 2 17 17 3 
12 20 17 5 19 1 
19 2 11 3 13 20 
18 6 17 5 17 4 
8 20 18 5 20 12 
8 11 17 1 19 6 
4 10 5 12 6 15 
12 16 16 15 10 9 
14 19 6 3 3 3 
18 11 14 15 7 14 
7 14 4 15 15 14 
20 18 3 16 9 20 
11 13 15 18 7 16 
18 12 14 4 14 9 
6 12 11 19 18 17 
4 16 11 19 11 5 
12 2 14 6 10 14 
5 12 6 11 9 4 
6 7 16 20 10 1 
8 7 4 18 17 2 
6 1 17 16 11 19 
12 3 13 17 20 2 
11 5 13 8 15 1 
4 13 19 11 4 8 
11 11 14 15 20 3 
8 5 3 16 13 5 
15 4 19 7 1 19 
20 3 3 4 2 9 
4 5 13 3 15 16 
2 18 6 8 12 17 
10 19 2 4 14 14 
8 20 9 7 18 1 
5 9 15 19 12 17 
19 16 13 12 10 20 
7 11 17 5 10 20 
1 19 10 14 2 15 
19 10 7 8 8 4 
8 12 13 3 2 16 
11 20 11 15 11 12 
14 18 15 2 2 4 
1 14 3 2 8 16 
17 6 5 3 13 12 

31
18 13 15 2 7 16 
18 9 16 20 3 18 
4 17 15 18 10 8 
13 3 2 7 4 1 
3 12 6 7 6 11 
11 4 15 17 17 1 
13 6 9 20 6 11 
17 1 19 4 18 9 
3 2 11 16 9 6 
16 11 18 14 9 3 
4 11 18 18 8 7 
10 12 12 10 11 9 
20 19 9 11 14 18 
11 17 20 13 12 8 
18 20 18 7 13 18 
2 16 9 19 5 16 
17 6 7 9 15 9 
9 14 19 18 16 13 
15 6 1 6 18 4 
13 8 3 2 14 15 
20 15 2 20 6 18 
15 2 3 13 2 17 
13 11 3 3 20 18 
15 14 16 7 12 5 
11 4 12 13 18 18 
20 9 12 1 8 17 
11 2 11 13 6 12 
10 18 2 4 12 13 
1 7 19 8 5 10 
13 15 5 16 20 2 
13 19 10 17 11 17 

27
5 1 10 15 6 15 
7 7 4 20 10 16 
13 2 14 11 10 10 
12 14 5 16 9 16 
18 14 14 19 10 16 
16 14 9 17 1 14 
4 7 12 19 18 1 
6 2 2 11 4 11 
1 15 16 5 3 5 
20 20 10 5 10 19 
12 17 4 20 14 4 
5 17 2 16 7 12 
8 13 13 10 3 9 
12 3 15 8 19 17 
4 18 8 13 14 18 
3 6 14 18 17 19 
2 14 7 15 1 14 
6 9 6 11 10 20 
19 1 3 5 20 1 
2 3 11 1 7 4 
10 1 9 4 19 18 
14 12 11 1 6 11 
14 12 19 11 2 8 
10 12 1 4 16 20 
5 9 15 7 10 13 
10 11 14 11 14 4 
8 20 15 10 20 12 

7
20 5 3 11 7 16 
10 16 7 2 12 15 
14 8 3 8 14 4 
20 3 15 5 5 20 
20 4 19 14 13 10 
6 5 14 20 15 20 
16 16 8 14 10 11 

3
8 3 18 3 10 11 
6 1 5 12 18 10 
4 17 13 2 3 6 

2
4 20 2 9 19 8 
1 6 3 8 20 12 

41
10 7 14 7 9 15 
17 7 8 13 18 5 
2 1 1 7 15 15 
4 18 14 5 18 13 
12 18 10 6 17 9 
10 6 16 3 12 16 
10 20 2 17 13 12 
1 6 4 13 12 10 
8 7 19 13 11 17 
5 14 14 7 20 11 
15 9 16 2 3 20 
18 4 19 11 20 3 
14 12 9 18 5 12 
7 4 19 6 16 1 
2 13 7 15 19 6 
17 13 6 13 7 20 
12 4 4 2 6 3 
17 20 15 5 17 11 
8 15 14 18 20 1 
11 13 13 17 20 11 
14 16 16 19 8 2 
18 11 17 1 5 2 
4 1 13 10 17 1 
20 4 16 5 14 7 
5 4 12 10 12 11 
20 5 6 7 3 6 
20 12 8 8 5 12 
2 20 12 14 9 8 
15 20 4 2 4 9 
8 20 4 19 9 15 
1 1 19 7 19 13 
4 19 16 11 6 20 
3 7 19 6 13 19 
14 7 18 9 8 13 
17 7 13 20 18 1 
14 18 13 4 16 12 
8 19 10 15 2 7 
15 4 6 5 9 18 
4 14 16 1 2 15 
6 18 1 18 9 10 
10 14 20 15 17 15 

25
6 16 6 7 11 7 
13 17 10 10 13 10 
7 16 16 14 9 17 
8 14 7 1 3 7 
10 4 1 9 18 17 
16 3 5 1 1 7 
19 6 15 20 15 7 
9 14 3 4 7 3 
13 15 8 11 15 10 
17 16 5 17 5 3 
6 12 17 2 4 18 
8 2 3 2 1 9 
20 1 2 14 5 9 
16 9 3 3 11 17 
4 7 12 1 16 8 
15 13 11 11 14 14 
20 1 15 14 14 15 
3 5 16 4 19 12 
12 14 12 6 9 2 
14 4 20 18 16 15 
5 10 7 8 13 12 
1 12 4 8 18 17 
14 20 2 1 15 12 
12 19 17 15 4 5 
8 18 1 8 15 16 

10
14 11 18 13 10 10 
4 11 13 8 10 10 
16 3 1 9 4 16 
20 7 6 17 14 1 
13 1 18 5 8 4 
1 2 7 18 6 8 
19 9 10 11 8 19 
1 4 2 1 4 17 
8 4 3 13 12 16 
14 4 9 3 9 16 

7
19 1 9 17 10 14 
4 8 15 14 18 2 
4 10 17 5 3 1 
13 10 16 8 15 7 
15 20 2 3 14 2 
19 12 14 19 20 3 
5 16 2 11 1 12 

6
4 4 1 1 1 3 
13 13 5 8 20 19 
6 15 18 19 17 11 
1 7 15 14 18 6 
9 2 1 10 4 1 
13 7 5 14 19 17 

3
8 11 9 12 10 9 
2 7 15 19 6 11 
2 6 10 8 11 7 

13
13 19 20 6 1 3 
18 13 9 2 18 8 
10 18 10 19 9 20 
19 11 6 13 1 3 
15 14 8 4 1 11 
2 6 9 1 11 1 
15 8 6 4 2 15 
3 11 12 4 1 1 
15 19 3 13 11 3 
15 6 9 15 1 9 
5 3 6 5 3 8 
6 18 16 3 13 9 
17 7 11 1 10 12 

4
13 17 10 15 9 13 
9 3 18 9 17 18 
18 1 20 15 6 15 
3 3 4 10 17 16 

2
18 5 14 20 5 15 
11 17 11 13 3 19 


500
4 7 18 16 14 16 
7 13 10 2 3 8 
11 20 4 7 1 7 
13 17 12 9 8 10 
3 11 3 4 8 16 
10 3 3 19 10 8 
14 17 12 3 10 14 
2 20 5 18 19 5 
16 11 14 7 12 1 
17 14 3 11 17 2 
6 6 5 8 17 6 
7 10 14 18 5 16 
3 6 15 8 15 5 
4 11 8 9 17 19 
9 5 4 12 15 20 
13 1 17 9 20 13 
7 7 15 20 16 11 
15 19 8 2 18 3 
18 13 13 17 2 1 
7 2 6 10 5 20 
1 10 12 18 18 12 
2 16 10 8 8 17 
18 14 7 6 7 4 
20 5 9 12 13 10 
4 20 11 9 9 16 
1 10 17 4 19 6 
7 12 2 16 20 9 
5 9 2 11 14 1 
15 5 5 15 8 17 
4 12 8 6 20 17 
13 12 18 9 16 8 
15 2 19 16 10 18 
16 14 19 9 4 12 
9 10 17 5 4 4 
14 19 7 1 5 19 
9 9 10 18 18 17 
5 4 11 4 11 20 
13 6 5 11 6 20 
15 7 10 3 3 5 
18 8 16 5 9 12 
3 9 20 4 7 9 
1 3 12 11 6 2 
2 11 19 6 1 17 
5 7 3 6 9 17 
3 19 5 18 3 5 
1 17 13 20 20 11 
9 12 14 12 2 11 
14 15 1 4 20 2 
20 17 20 14 14 9 
11 16 7 7 5 1 
11 5 17 3 17 8 
6 17 20 19 8 13 
9 13 20 10 17 11 
3 8 7 2 14 13 
2 16 20 20 2 5 
20 12 1 8 6 9 
8 11 5 19 1 5 
3 10 17 2 11 5 
13 13 13 11 6 6 
3 20 1 3 19 14 
19 11 5 11 10 2 
20 17 13 16 15 5 
20 10 14 17 11 16 
1 3 20 5 14 6 
2 8 5 14 2 15 
7 20 5 3 3 7 
5 2 3 9 9 10 
13 9 19 19 17 9 
14 9 4 14 14 9 
11 15 8 7 9 10 
1 7 9 18 10 11 
4 14 4 18 14 13 
7 6 13 17 16 9 
18 10 17 1 15 2 
1 5 9 8 11 9 
17 3 15 18 20 4 
20 3 9 4 1 2 
8 19 20 12 16 15 
20 13 16 8 5 10 
10 5 6 10 4 16 
18 1 19 12 10 10 
8 9 13 16 4 5 
10 11 3 1 2 10 
7 13 2 3 1 18 
4 2 2 10 11 6 
17 8 18 15 11 7 
5 18 15 9 6 19 
13 7 1 7 7 15 
17 13 19 10 7 11 
8 11 12 1 12 14 
18 8 13 7 15 16 
13 11 13 20 11 10 
10 15 16 2 1 14 
8 9 19 7 11 5 
17 18 7 1 10 18 
6 20 18 19 6 4 
14 19 14 18 10 4 
8 19 18 15 12 10 
1 20 19 19 6 9 
15 14 18 2 14 19 
11 20 18 20 10 4 
3 15 14 8 12 3 
3 11 13 12 18 16 
2 18 15 12 8 12 
12 2 18 1 15 11 
19 6 2 17 17 3 
12 20 17 5 19 1 
19 2 11 3 13 20 
18 6 17 5 17 4 
8 20 18 5 20 12 
8 11 17 1 19 6 
4 10 5 12 6 15 
12 16 16 15 10 9 
14 19 6 3 3 3 
18 11 14 15 7 14 
7 14 4 15 15 14 
20 18 3 16 9 20 
11 13 15 18 7 16 
18 12 14 4 14 9 
6 12 11 19 18 17 
4 16 11 19 11 5 
12 2 14 6 10 14 
5 12 6 11 9 4 
6 7 16 20 10 1 
8 7 4 18 17 2 
6 1 17 16 11 19 
12 3 13 17 20 2 
11 5 13 8 15 1 
4 13 19 11 4 8 
11 11 14 15 20 3 
8 5 3 16 13 5 
15 4 19 7 1 19 
20 3 3 4 2 9 
4 5 13 3 15 16 
2 18 6 8 12 17 
10 19 2 4 14 14 
8 20 9 7 18 1 
5 9 15 19 12 17 
19 16 13 12 10 20 
7 11 17 5 10 20 
1 19 10 14 2 15 
19 10 7 8 8 4 
8 12 13 3 2 16 
11 20 11 15 11 12 
14 18 15 2 2 4 
1 14 3 2 8 16 
17 6 5 3 13 12 
18 13 15 2 7 16 
18 9 16 20 3 18 
4 17 15 18 10 8 
13 3 2 7 4 1 
3 12 6 7 6 11 
11 4 15 17 17 1 
13 6 9 20 6 11 
17 1 19 4 18 9 
3 2 11 16 9 6 
16 11 18 14 9 3 
4 11 18 18 8 7 
10 12 12 10 11 9 
20 19 9 11 14 18 
11 17 20 13 12 8 
18 20 18 7 13 18 
2 16 9 19 5 16 
17 6 7 9 15 9 
9 14 19 18 16 13 
15 6 1 6 18 4 
13 8 3 2 14 15 
20 15 2 20 6 18 
15 2 3 13 2 17 
13 11 3 3 20 18 
15 14 16 7 12 5 
11 4 12 13 18 18 
20 9 12 1 8 17 
11 2 11 13 6 12 
10 18 2 4 12 13 
1 7 19 8 5 10 
13 15 5 16 20 2 
13 19 10 17 11 17 
5 1 10 15 6 15 
7 7 4 20 10 16 
13 2 14 11 10 10 
12 14 5 16 9 16 
18 14 14 19 10 16 
16 14 9 17 1 14 
4 7 12 19 18 1 
6 2 2 11 4 11 
1 15 16 5 3 5 
20 20 10 5 10 19 
12 17 4 20 14 4 
5 17 2 16 7 12 
8 13 13 10 3 9 
12 3 15 8 19 17 
4 18 8 13 14 18 
3 6 14 18 17 19 
2 14 7 15 1 14 
6 9 6 11 10 20 
19 1 3 5 20 1 
2 3 11 1 7 4 
10 1 9 4 19 18 
14 12 11 1 6 11 
14 12 19 11 2 8 
10 12 1 4 16 20 
5 9 15 7 10 13 
10 11 14 11 14 4 
8 20 15 10 20 12 
20 5 3 11 7 16 
10 16 7 2 12 15 
14 8 3 8 14 4 
20 3 15 5 5 20 
20 4 19 14 13 10 
6 5 14 20 15 20 
16 16 8 14 10 11 
8 3 18 3 10 11 
6 1 5 12 18 10 
4 17 13 2 3 6 
4 20 2 9 19 8 
1 6 3 8 20 12 
10 7 14 7 9 15 
17 7 8 13 18 5 
2 1 1 7 15 15 
4 18 14 5 18 13 
12 18 10 6 17 9 
10 6 16 3 12 16 
10 20 2 17 13 12 
1 6 4 13 12 10 
8 7 19 13 11 17 
5 14 14 7 20 11 
15 9 16 2 3 20 
18 4 19 11 20 3 
14 12 9 18 5 12 
7 4 19 6 16 1 
2 13 7 15 19 6 
17 13 6 13 7 20 
12 4 4 2 6 3 
17 20 15 5 17 11 
8 15 14 18 20 1 
11 13 13 17 20 11 
14 16 16 19 8 2 
18 11 17 1 5 2 
4 1 13 10 17 1 
20 4 16 5 14 7 
5 4 12 10 12 11 
20 5 6 7 3 6 
20 12 8 8 5 12 
2 20 12 14 9 8 
15 20 4 2 4 9 
8 20 4 19 9 15 
1 1 19 7 19 13 
4 19 16 11 6 20 
3 7 19 6 13 19 
14 7 18 9 8 13 
17 7 13 20 18 1 
14 18 13 4 16 12 
8 19 10 15 2 7 
15 4 6 5 9 18 
4 14 16 1 2 15 
6 18 1 18 9 10 
10 14 20 15 17 15 
6 16 6 7 11 7 
13 17 10 10 13 10 
7 16 16 14 9 17 
8 14 7 1 3 7 
10 4 1 9 18 17 
16 3 5 1 1 7 
19 6 15 20 15 7 
9 14 3 4 7 3 
13 15 8 11 15 10 
17 16 5 17 5 3 
6 12 17 2 4 18 
8 2 3 2 1 9 
20 1 2 14 5 9 
16 9 3 3 11 17 
4 7 12 1 16 8 
15 13 11 11 14 14 
20 1 15 14 14 15 
3 5 16 4 19 12 
12 14 12 6 9 2 
14 4 20 18 16 15 
5 10 7 8 13 12 
1 12 4 8 18 17 
14 20 2 1 15 12 
12 19 17 15 4 5 
8 18 1 8 15 16 
14 11 18 13 10 10 
4 11 13 8 10 10 
16 3 1 9 4 16 
20 7 6 17 14 1 
13 1 18 5 8 4 
1 2 7 18 6 8 
19 9 10 11 8 19 
1 4 2 1 4 17 
8 4 3 13 12 16 
14 4 9 3 9 16 
19 1 9 17 10 14 
4 8 15 14 18 2 
4 10 17 5 3 1 
13 10 16 8 15 7 
15 20 2 3 14 2 
19 12 14 19 20 3 
5 16 2 11 1 12 
4 4 1 1 1 3 
13 13 5 8 20 19 
6 15 18 19 17 11 
1 7 15 14 18 6 
9 2 1 10 4 1 
13 7 5 14 19 17 
8 11 9 12 10 9 
2 7 15 19 6 11 
2 6 10 8 11 7 
13 19 20 6 1 3 
18 13 9 2 18 8 
10 18 10 19 9 20 
19 11 6 13 1 3 
15 14 8 4 1 11 
2 6 9 1 11 1 
15 8 6 4 2 15 
3 11 12 4 1 1 
15 19 3 13 11 3 
15 6 9 15 1 9 
5 3 6 5 3 8 
6 18 16 3 13 9 
17 7 11 1 10 12 
13 17 10 15 9 13 
9 3 18 9 17 18 
18 1 20 15 6 15 
3 3 4 10 17 16 
18 5 14 20 5 15 
11 17 11 13 3 19 
5 4 2 2 12 10 
11 1 11 3 16 8 
17 10 2 20 19 18 
7 16 2 12 15 19 
6 18 7 17 10 2 
15 14 17 8 7 20 
18 17 1 20 11 8 
7 7 9 8 18 7 
17 16 14 18 7 20 
8 13 17 15 1 18 
16 15 11 12 3 9 
11 12 6 3 11 8 
2 17 15 10 16 4 
16 12 12 1 1 18 
1 9 2 17 15 2 
15 10 9 17 13 3 
6 3 14 3 18 4 
10 11 12 16 1 7 
20 8 10 3 9 10 
20 9 10 14 17 4 
7 11 5 15 20 17 
17 5 12 10 19 1 
5 20 11 16 16 11 
2 7 11 3 9 19 
5 20 19 14 5 15 
10 12 18 6 18 17 
3 15 13 6 16 11 
6 13 10 8 8 17 
19 2 3 1 4 3 
19 8 15 17 14 19 
11 15 10 8 20 8 
16 2 14 8 19 1 
10 16 13 12 4 13 
8 14 14 3 14 9 
17 12 17 11 20 2 
10 2 16 11 10 15 
10 17 9 3 5 7 
16 14 15 8 5 18 
12 5 11 5 19 4 
14 15 7 2 6 6 
15 7 7 10 17 8 
16 7 5 4 1 1 
3 16 14 9 16 11 
6 7 7 8 4 5 
11 9 11 9 2 16 
14 16 2 12 5 11 
12 12 9 16 8 9 
16 2 17 1 10 12 
3 15 10 1 2 5 
5 4 13 16 12 14 
3 17 1 17 20 17 
19 11 9 7 18 16 
15 5 17 11 6 6 
14 20 12 16 1 5 
20 17 8 5 4 11 
10 7 7 11 15 6 
19 13 9 7 19 6 
14 5 11 2 8 8 
19 1 19 10 8 19 
14 20 8 13 16 11 
3 5 9 1 7 3 
7 6 7 7 4 5 
12 18 2 14 11 9 
13 10 1 12 11 9 
2 17 8 9 9 3 
12 4 19 20 4 6 
15 2 3 13 8 18 
10 12 15 11 5 18 
19 18 7 19 1 9 
7 2 5 6 3 6 
20 14 9 19 5 4 
16 11 6 10 4 5 
7 13 16 14 3 1 
11 1 10 9 11 10 
17 18 3 2 15 5 
19 15 10 19 5 15 
2 20 17 19 1 20 
4 7 4 19 20 6 
11 2 18 12 10 9 
13 7 18 16 20 4 
20 10 18 10 8 14 
16 1 5 12 20 5 
12 15 4 7 5 3 
13 8 17 2 19 6 
2 12 4 11 7 15 
15 18 16 4 19 3 
18 14 16 14 18 15 
19 1 1 2 7 5 
16 19 4 12 13 3 
10 6 6 5 17 4 
12 3 1 7 6 12 
10 15 5 17 9 2 
11 19 2 3 20 9 
19 7 19 3 11 3 
5 20 9 2 16 17 
5 7 19 17 14 16 
8 15 3 5 11 3 
18 13 1 12 7 12 
20 5 10 10 7 20 
5 3 11 13 4 7 
9 20 13 19 17 18 
14 16 4 16 20 6 
10 18 10 10 1 16 
13 12 1 3 1 7 
14 17 10 5 9 5 
11 9 5 15 19 13 
5 13 8 8 20 20 
14 10 9 15 11 9 
11 16 20 11 10 12 
9 3 9 18 7 9 
15 9 10 19 4 8 
11 8 12 10 7 4 
1 12 5 9 7 7 
17 17 2 8 19 3 
20 7 6 20 5 4 
8 19 13 9 9 8 
17 11 15 20 12 13 
3 13 5 7 1 3 
14 10 19 7 9 17 
10 8 3 7 19 19 
10 19 9 2 7 9 
1 15 19 15 15 3 
20 17 15 16 16 15 
18 1 16 8 7 5 
4 16 4 18 14 3 
9 4 1 9 17 7 
10 18 2 20 4 8 
2 3 4 16 18 11 
3 7 11 18 14 18 
2 9 5 18 7 19 
20 7 14 20 7 10 
18 16 7 11 16 3 
18 17 17 14 13 15 
4 7 1 15 4 7 
4 18 15 20 15 13 
10 14 19 3 5 6 
5 14 13 3 5 8 
5 2 17 2 7 9 
8 11 15 20 17 10 
6 12 7 1 3 13 
13 13 18 4 7 2 
1 11 8 13 14 12 
1 18 5 9 11 12 
9 18 14 15 18 2 
4 15 5 3 15 7 
15 20 19 5 3 6 
18 3 8 5 15 1 
16 7 11 1 15 1 
4 3 11 9 17 20 
10 13 14 6 15 9 
12 1 8 3 5 10 
20 3 4 7 7 18 
8 15 17 10 7 11 
10 10 6 12 18 14 
11 19 6 5 4 20 
5 7 13 4 9 17 
13 8 11 8 7 18 
5 14 12 13 15 18 
16 16 19 1 8 8 
14 18 18 20 14 13 
11 18 19 3 1 8 
12 5 7 2 12 13 
19 9 18 2 1 12 
11 8 20 1 8 7 
20 14 4 17 5 10 
9 15 7 20 10 8 
19 1 12 5 14 16 
10 5 4 19 6 16 
3 9 4 2 9 3 
8 1 16 3 17 12 
12 18 19 19 17 8 
18 15 20 1 11 13 

0

skipping the actual sequence i get :

Code: Select all

Case #1
7

Case #2
4

Case #3
4

Case #4
4

Case #5
7

Case #6
47

Case #7
16

Case #8
12

Case #9
4

Case #10
2

Case #11
2

Case #12
22

Case #13
11

Case #14
5

Case #15
4

Case #16
3

Case #17
3

Case #18
7

Case #19
3

Case #20
1

Case #21
230

[qndel]

I got 3 WA befor I changed may array. So I think that limits for this problem are diffrent from those which are given. I got AC when changed limits to 1<N<600 and numbers of colors 1 to 200.

[sclo]

I'm sure that there are at most only 500 cubes, since that's how large my array was. I never cared about how many colors there are in my algorithm. Suppose there are N cubes, then there's a way to do it with a O(N^2) LIS algorithm on 6*N elements.

[luison9999]

ejem...

Case #4
5
3 top
5 top
6 left
7 right
8 front

I cannot got ACC yet, but I have the same answer in all the cases with the exception of the case 4, and case 7(I got 17 in the case #7).

[Riyad]

luison9999 is right . the output for case 4 and case 7 is wrong . the output should be 5 and 17 respectively ...it did make me confused but i submitted before matching these given outputs with mine

[Yaron Wittenstein]

I want to solve this problem by building a graph and running
topological sort on it and then finding the longest path in the graph.

now for a dense graph I get E = V^2

where V <= 6 * 500 right? (6 positions and 500 cubes maximum)
so (6*500)^2 is too much space isn't? (for int array)

there is another option? (I guess they dont expect me to work
in bits level)

please help me here, or tell me another option for solving
this question.

[Jan]

My solution is O((6*n)^2). So, I think you can apply this algorithm.

[soddy]

I am getting WA for this problem but can't find the bug. I use 2 functions. One for the length of LIS and other to print the LIS. Don't know where am I getting it wrong. Here's the code

Code: Select all

#include<iostream>
#include<sstream>
#include<map>
#include<vector>
#include<iomanip>
#define PB push_back
using namespace std;
int a[500][6],dp[505][105];
vector<int> ans;
string side[]={"front", "back", "left", "right", "top", "bottom"};

/*This function finds the maximum length of tower*/
int solve(int pos,int col)
{
	if(pos<0) return 0;
	int& res=dp[pos][col];
	if(res!=-1) return res;
	res=solve(pos-1,col);
	if(col==0){
		for(int i=0;i<6;i++)
			res=max(res,1+solve(pos-1,a[pos][i]));
	}
	else{
		for(int i=0;i<6;i++)
		{
			int j;
			if(col==a[pos][i])
			{
				if(i%2==0) j=i+1; else j=i-1;				
				res=max(res,1+solve(pos-1,a[pos][j]));
			}	
		}
	}	
	return res;
}

/*This function prints the tower*/
void print(int pos,int col,int len)
{
	if(pos<0) return;
	if(len==dp[pos-1][col]){
		print(pos-1,col,len);
		return;
	}	
	if(col==0){
		for(int i=0;i<6;i++)
			if(len==1+dp[pos-1][a[pos][i]]){
				ans.PB(pos);
				ans.PB(i);
				print(pos-1,a[pos][i],len-1);
				return;
			}	
	}
	else{
		for(int i=0;i<6;i++)
		{
			int j;
			if(col==a[pos][i])
			{
				if(i%2==0) j=i+1; else j=i-1;				
				if(dp[pos][col]==1+dp[pos-1][a[pos][j]]){
					ans.PB(pos);
					ans.PB(j);
					print(pos-1,a[pos][j],len-1);
					return;
				}	
			}	
		}
	}	
}

int main()
{
	ios_base::sync_with_stdio(false);
	int n,kase=1;
	bool first=true;
	while(cin>>n && n)
	{	
		if(!first) cout<<endl;
		first=false;
		ans.clear();
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<n;i++)
			for(int j=0;j<6;j++)
				cin>>a[i][j];
		int len=solve(n-1,0);
		print(n-1,0,len);
		cout<<"Case #"<<kase++<<endl;
		cout<<len<<endl;
		for(int i=ans.size()-1;i>=0;i-=2)
			cout<<ans[i-1]+1<<" "<<side[ans[i]]<<endl;
	}		
}

[DD]

I want to solve this problem by building a graph and running
topological sort on it and then finding the longest path in the graph.

now for a dense graph I get E = V^2

where V <= 6 * 500 right? (6 positions and 500 cubes maximum)
so (6*500)^2 is too much space isn't? (for int array)

there is another option? (I guess they dont expect me to work
in bits level)

please help me here, or tell me another option for solving
this question.

I think it is fine to solve this problem by topological sort but you may need to use adjacent lists for graph constructions.