## 10051 - Tower of Cubes

Moderator: Board moderators

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

### 10051 - Tower of Cubes

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
kiha

platizon
New poster
Posts: 1
Joined: Mon Apr 26, 2004 3:43 pm

### 10051 - tower of cubes, help please!!

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

thanks a lot

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

### 10051 Tower of Cubes

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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm
Oh God

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

Thanks very much!
Kind regards
kiha

milo
New poster
Posts: 3
Joined: Tue Oct 26, 2004 6:05 pm
Location: Latin America
can somebody put some interesting test cases, because i don't realize where is my error and i am desperate , thanks

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
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

``````
if u can think of it .. u can do it in software.

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

### To people he have WA.

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.
NOthing special

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
New poster
Posts: 3
Joined: Sat Apr 09, 2005 12:19 am
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).

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:
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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

### 10051

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)

this question.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My solution is O((6*n)^2). So, I think you can apply this algorithm.
Ami ekhono shopno dekhi...
HomePage

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

### WA

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;
}
}
``````
I am not selfish, I just want everything.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10051 - Tower of Cubes

Yaron Wittenstein wrote: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)