437 - The Tower of Babylon

[Dejarik]

I have solved the problem, but without succeeding it in the time limit allowed. That's this because I tried to find any algorithmic method, like divide and conquer, to avoid using an exhaustive backtracking way that tries all the cases of the input.

Finally, i didn't found any good idea, and my problem solves correctly the problem but spending a very large amount of time iterating all the possible ways of the backtracking (the only idea i got is to ignore blocks that have been used three times). But this is not enough to avoid Time Limit.

What strategy did you use when solving this problem?

Thanks in advance, Joan

[titid_gede]

it's a variation of Longest Increasing Subsequence (LIS) problem. try to find it. hope it helps.

regards,
titid

[Dejarik]

I think i'm really near from the Accepted solution for this "easy" problem, but still Wrong Answer...

Can anybody with correct answer please check this input and output returned by my code?

Thanks in advance!

Joan, SPAIN

My input is:

Code: Select all

5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
20
10 19 18
18 19 22
23 33 34
19 21 22
32 32 31
10 90 10
10 80 10
22 22 29
29 28 27
26 25 24
19 80  1
22 21 31
29 28 55
58 42 39
48 78 32
2   2 90
3  99 33
54 44 44
57 13 33
10 29 80
5
1  1  1
1  2  1
1  3  1
1  4  1 
1  5  1
5
2  3 100
3  4 200
4  6  50
6  8 100
5  5  75
1
80 90 100
6
15 19 3
44 33 21
88 33 57
31 29 20
99 88 1
52 26 5
2
100 100 100
102  98 100
10
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
8
10 16 1
5  8  2
20 32 2
10 16 2
16 10 2
32 20 2
8  5  2
16 10 1
0

And my output is

Code: Select all

Case 1: maximum height = 342
Case 2: maximum height = 488
Case 3: maximum height = 5
Case 4: maximum height = 475
Case 5: maximum height = 180
Case 6: maximum height = 273
Case 7: maximum height = 200
Case 8: maximum height = 310
Case 9: maximum height = 50

[/code]

[Aleksandrs Saveljevs]

Joan, hi.

This is my output:

Code: Select all

Case 1: maximum height = 342
Case 2: maximum height = 588
Case 3: maximum height = 5
Case 4: maximum height = 481
Case 5: maximum height = 180
Case 6: maximum height = 273
Case 7: maximum height = 200
Case 8: maximum height = 310
Case 9: maximum height = 50

Hope that helps. Good luck!

[sohel]

I actually solved this problem using backtracking.

For all the blocks I found out the three orientations and for a total of 30 blocks there could be 90 different types...

.. I sort all this in the descending order of the base and apply backtrack...
... so there are 2^90 combinations in total but with some major pruning I managed to get AC in 0.057 seconds.

[Zyaad Jaunnoo]

You can solve using Floyd's 0(n^3) algo.. but with major modification so that it caters for the longest path rather than the shortest path. I got accepted using this algo but nearly 2 seconds

[kasparov]

hello everybody,

i solved it but WA (in 0.010 seconds).
my solution is memonized backtracking.
Can u tell me wether this output's correct or not ?

Code: Select all

5
31 41 59 
26 53 58 
97 93 23 
84 62 64 
33 83 27 
20 
10 19 18 
18 19 22 
23 33 34 
19 21 22 
32 32 31 
10 90 10 
10 80 10 
22 22 29 
29 28 27 
26 25 24 
19 80  1 
22 21 31 
29 28 55 
58 42 39 
48 78 32 
2   2 90 
3  99 33 
54 44 44 
57 13 33 
10 29 80 
5 
1  1  1 
1  2  1 
1  3  1 
1  4  1 
1  5  1
5 
2  3 100 
3  4 200 
4  6  50 
6  8 100 
5  5  75 
1 
80 90 100 
6 
15 19 3 
44 33 21 
88 33 57 
31 29 20 
99 88 1 
52 26 5 
2 
100 100 100 
102  98 100 
8 
10 16 1 
5  8  2 
20 32 2 
10 16 2 
16 10 2 
32 20 2 
8  5  2 
16 10 1 
10 
1 2 3 
4 5 6 
7 8 9 
10 11 12 
13 14 15 
16 17 18 
19 20 21 
22 23 24 
25 26 27 
28 29 30
30
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8
9 9 9
10 10 10
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8
9 9 9
10 10 10
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8
9 9 9
10 10 10
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

My output is :

Code: Select all

342
588
5
481
180
273
200
50
310
55
40
21
28
342

if this is correct, plz send me some (tricky) input.
i can send the code if anyone wishs to look at.

byeeeeeeeeeee

[SRX]

I use LIS

and pass the above test data

but still wa

Code: Select all

#include <iostream>
#include <algorithm>
//#include <fstream>
using namespace std ;
//ifstream fin ("437.in") ; 
//ofstream fout ("437.txt") ;
int n , inx , cases = 0 ; 
struct box {
 int sta [3] ;     
} Box [100] ;     
int mysort ( box& Box ){
 int i , j ; 
  for ( i=0 ; i<3 ; i++ )   
     for ( j=0 ; j<2 ; j++ )
            if ( Box.sta[j]>Box.sta[j+1] )
                               swap ( Box.sta[j] , Box.sta[j+1] ) ; 
}    
int Input () {
 int i , a , b , c , mymax , mymin , mymid ; 
  for ( i=0 , inx = -1  ; i<n ; i++ ){
    cin >> Box[++inx].sta[0] >> Box[inx].sta[1] >> Box[inx].sta[2] ; 
    mysort ( Box[inx] ) ; 
    a = Box[inx].sta[0] , b = Box[inx].sta[1] , c = Box[inx].sta[2] ; 
    Box[++inx].sta[0]=b , Box[inx].sta[1]=c , Box[inx].sta[2]=a ;   
    Box[++inx].sta[0]=a , Box[inx].sta[1]=c , Box[inx].sta[2]=b ;  
  }
}
int Sort  () {
 int i , j , k ; 
  for ( i=0 ; i<=inx ; i++ )
    for ( j=0 ; j<inx ; j++ ) {
   for ( k=0 ; Box[j].sta[k]==Box[j+1].sta[k] && k<3 ; k++ ) ; 
    if ( k==3 ) continue ; 
    if ( Box[j].sta[k]>Box[j+1].sta[k] )
                             swap ( Box[j] , Box[j+1] ) ; 
  }
}
int LIS () {
 int table [100] = { 0  } , i = 1 , j , mymax = 0 , ans = 0  ; 
 table [0] = Box[0].sta[2] ;  
  for ( ; i<=inx ; i++ ){
   for ( j=i-1 , mymax = 0 ; j+1 ; j-- )
                 if ( Box[i].sta[0]>Box[j].sta[0] && Box[i].sta[1]>Box[j].sta[1] && table[j]>mymax )
                                                                       mymax = table[j] ; 
   table[i] = mymax + Box[i].sta[2] ; 
   ans = max ( ans , table[i] ) ; 
 }
 cout << "Case " << ++cases << ": maximum height = " << ans << endl  ; 
}
int main () {
 while ( cin >> n && n ){   
  Input () ;   
  Sort  () ;   
  LIS   () ;
 }    
}    

[kasparov]

I'm got AC finally.

i forgot to put the format "Case #: maximum height = #"
but my solution was gr8 0.01 seconds (i hope it's gr8 )

if anybody wanna test some test cases, tell me

[roticv]

Can someone tell me how you guys prune or memorise? This question is driving me nuts. When I tried to memorise, I end up getting wrong answer.

[rezaeeEE]

my code returns the wrong answer with the testcases that exist in this post.
but i cant find my buge.
can any body help me?

Code: Select all

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int bob[30][3];
int h[30][3][3];
int n;

int height(int id, int i, int j)		
{
	int a[3] = {0};
	a[i] = 1, a[j] = 1;		 // return height of the tower 
	for(int k = 0;k < 3;k++) // with base of bob[id][i] and bob[id][j]
		if(!a[k])
			return bob[id][k];
}

bool chek(int id1, int r1, int w1, int id2, int r2, int w2)
{
	// cheking tower with base of bob[r2][w2]
	// can placed up on top of the tower 
	// with base of bob[r1][w1]
	return bob[id1][r1] > bob[id2][r2] && bob[id1][w1] > bob[id2][w2];
}

int maxheight( int id, int r1, int r2 )
{
	// calculating maxheight of the tower that its base is the
	// bob[id] wiht the dimesnsion bob[r1] and bob[r2] 
                // with memo DP
	if(!h[id][r1][r2])
	{
		int mx = 0;
		for( int i = 0;i < n;i++ ){
			if(chek(id, r1, r2, i, 1, 2) && mx < maxheight(i, 1, 2))
				mx = maxheight(i, 1, 2);
			else
			if(chek(id, r1, r2, i, 0, 2) && mx < maxheight(i, 0, 2))
				mx = maxheight(i, 0, 2);
			else
			if(chek(id, r1, r2, i, 0, 1) && mx < maxheight(i, 0, 1))
				mx = maxheight(i, 0, 1);
		}
		h[id][r1][r2] = height(id, r1, r2) + mx;
	}
	return h[id][r1][r2];
}


int main()
{
	int test = 1;
	while(cin >> n, n){
		for(int i = 0;i < n;i++){
			cin >> bob[i][0] >> bob[i][1] >> bob[i][2];
			sort(bob[i], bob[i] + 3);
		}
		memset(h, 0, sizeof h);
		for(int i = 0;i < n;i++)
			maxheight(i, 1, 2);
		int mx = 0;
		for(int i = 0;i < n;i++)
			if(mx < h[i][1][2])
				mx = h[i][1][2];
		cout << "Case "<<test++<<": maximum height = "<<mx<<endl;
	}
	return 0;
}

sorry with my poor english

[Jan]

Check the third case and debug your code. I haven't understood your algorithm.

[roticv]

I finally realised that there is a linear solution to the problem - solving longest path on a DAG.

[Shafaet_du]

My solution was like this:
F(R,C,H)=H+max( all other valid combinations that can placed over R,C,H sized block)
if no more blocks can be placed it will return just H as max will be 0.

At 1st i assumed R,C,H<=200 and used an array dp[200][200][200] but it gave me RTE. Then i changed it to a 3d map like this: map<int, map<int, map<int,int> > >dp and got ac in .016 sec.

[achan8501]

I finally realised that there is a linear solution to the problem - solving longest path on a DAG.

That's what I did too. The only problem is that building the graph is not linear time, I believe. Still, it was fast enough to get it accepted in 0.012s.