10051 - Tower of Cubes

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10051 - Tower of Cubes

Post by kiha » Wed Feb 11, 2004 9:46 pm

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

Post by platizon » Mon Apr 26, 2004 4:09 pm

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
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

10051 Tower of Cubes

Post by skylander » Sun Jun 06, 2004 8:52 am

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

Post by jackie » Sat Jul 24, 2004 4:03 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

Post by kiha » Wed Jul 28, 2004 10:05 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

Post by milo » Tue Oct 26, 2004 6:15 pm

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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sat Aug 20, 2005 12:17 pm

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.

Post by qndel » Fri Jan 27, 2006 11:38 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 10:47 pm

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

Post by luison9999 » Mon May 01, 2006 2:30 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).

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Tue Sep 05, 2006 4:32 pm

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 :wink: but i submitted before matching these given outputs with mine :P
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

Post by Yaron Wittenstein » Tue Oct 03, 2006 5:34 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 30, 2006 9:00 pm

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

Post by soddy » Sat Feb 23, 2008 10:17 am

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

Post by DD » Sat Nov 15, 2008 10:22 am

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)

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.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 100 (10000-10099)”