Page 1 of 1
437 - The Tower of Babylon
Posted: Fri Mar 12, 2004 4:15 pm
by 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
Posted: Fri Mar 12, 2004 4:58 pm
by titid_gede
it's a variation of Longest Increasing Subsequence (LIS) problem. try to find it. hope it helps.
regards,
titid
Posted: Sat Mar 20, 2004 1:32 pm
by 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]
Posted: Mon Mar 22, 2004 3:01 pm
by 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!
Posted: Tue Jul 13, 2004 3:17 pm
by 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.
Posted: Fri Apr 01, 2005 8:05 am
by 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
Posted: Fri Aug 12, 2005 7:21 am
by 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
Posted: Fri Aug 12, 2005 7:28 pm
by 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 () ;
}
}
Posted: Sun Aug 14, 2005 8:57 am
by 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
Posted: Sun Sep 04, 2005 11:03 am
by 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.
help
Posted: Sat Oct 06, 2007 9:14 pm
by 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
Posted: Sat Oct 06, 2007 10:30 pm
by Jan
Check the third case and debug your code. I haven't understood your algorithm.
Re: 437 - Any good idea for Towers of Babylonia?
Posted: Mon Jun 01, 2009 10:26 am
by roticv
I finally realised that there is a linear solution to the problem - solving longest path on a DAG.
Re: 437 - Any good idea for Towers of Babylonia?
Posted: Tue May 31, 2011 6:18 am
by 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.
Re: 437 - Any good idea for Towers of Babylonia?
Posted: Mon Dec 10, 2012 10:46 am
by achan8501
roticv wrote: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.