10304 - Optimal Binary Search Tree

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

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

10304 - Optimal Binary Search Tree

Post by Joe Smith » Mon Jun 17, 2002 6:36 pm

How did people get their solutions to run so fast? I used the obvious O(n^3) dynamic programming algorithm; is there something better? My first two attempts used memoization and were too slow, so I switched to iterating over the array, eliminating all function calls, and my submission just barely ran in time, 27s.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Tue Jun 18, 2002 4:46 am

Can anybody explain exercise 15.5-4 of CLRS to me? I don't ask for a solution, I just can't understand the first sentence. This "always" and "for all" and stuff is weirdly mixed...

(Later the same day) Found it out myself. The hint means that in order to find root[i,j] you only have to try all nodes from root[i,j-1] to root[i+1,j], not all nodes from i to j.

I still believe that the wording in the book is quite confusing...

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » Tue Jun 18, 2002 5:42 am

Stefan Pochmann wrote:Can anybody explain exercise 15.5-4 of CLRS to me? I don't ask for a solution, I just can't understand the first sentence. This "always" and "for all" and stuff is weirdly mixed...

(Later the same day) Found it out myself. The hint means that in order to find root[i,j] you only have to try all nodes from root[i,j-1] to root[i+1,j], not all nodes from i to j.
Ah... of course. If there's a subproblem where a node isn't the root, it's clearly not going to be the root of the original problem either. I am humbled once again! (sigh)

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Tue Jun 18, 2002 6:42 am

I think that's a wrong interpretation. For example, let i=3 and j=7 and let root[3,6]=4 and root[4,7]=6. Then we try 4 to 6 as root[3,7]. We might end up with 5, even though it is not the root of any of the two subproblems.

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » Wed Jun 19, 2002 6:21 pm

Stefan Pochmann wrote:I think that's a wrong interpretation. For example, let i=3 and j=7 and let root[3,6]=4 and root[4,7]=6. Then we try 4 to 6 as root[3,7]. We might end up with 5, even though it is not the root of any of the two subproblems.
I wasn't very specific; what I meant was the nodes to the left of root[3,6] and to the right of root[4,7], not the ones in-between. If node k is to the left of root[a,b] then it must be to the left of root[a,b+1] as well. It's sort of like balancing the tree... if all the weight you're adding is to the right, your root couldn't possibly shift to the left, it could only shift to the right (or stay the same) to compensate.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10304

Post by htl » Tue Nov 19, 2002 6:22 pm

I use DP with time complexity O(n^3), and I got TLE. It's so strange that so many people got AC though they run over 10s. I try to use the memory as less as possible but the result shows that I use over 50000k bytes of memory. How can I improve my code?
[c]
#include<stdio.h>
#define MAX 2147483647
void main(void)
{
int n,x,y,r;
long **obst,**w,min,a,b;
while(scanf("%d",&n)!=EOF)
{
obst=(long **)malloc(sizeof(long *)*n);
w=(long **)malloc(sizeof(long *)*n);
for(x=0;x<n;x++)
{
obst[x]=(long *)malloc(sizeof(long)*(n-x));
w[x]=(long *)malloc(sizeof(long)*(n-x));
}
for(x=0;x<n;x++)
scanf("%ld",&w[x][0]),obst[x][0]=0;
if(n==1)
{
printf("0\n");
continue;
}
for(x=0;x<n;x++)
for(y=x+1;y<n;y++)
{
w[x][y-x]=w[x][y-1-x]+w[y][0];
for(min=MAX,r=x;r<=y;r++)
{
if(r==0)
a=0;
else
a=obst[x][r-1-x];
if(r==y)
b=0;
else
b=obst[r+1][y-(r+1)];
if(a+b+w[x][y-x]-w[r][0]<min)
min=a+b+w[x][y-x]-w[r][0];
}
obst[x][y-x]=min;
}
printf("%ld\n",obst[0][n-1]);
free(obst);
free(w);
}
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Wed Nov 20, 2002 5:19 pm

Here's my newest code. But it still got TLE.
[c]
#include<stdio.h>
#define MAX 2147483647
void main(void)
{
int n,x,y,r,z;
long **obst,f[250],w[250],min,a,b,c;
while(scanf("%d",&n)!=EOF)
{
obst=(long **)malloc(sizeof(long *)*n);
for(x=0;x<n;x++)
obst[x]=(long *)malloc(sizeof(long)*n);
for(x=0;x<n;x++)
scanf("%ld",&f[x]),obst[x][x]=0,w[x]=f[x];
if(n==1)
{
printf("0\n");
continue;
}
for(x=1;x<n;x++)
w[x]+=w[x-1];
for(x=1;x<n;x++)
for(y=0,z=x;z<n;y++,z++)
{
for(min=MAX,r=y;r<=z;r++)
{
if(r==0)
a=0;
else
a=obst[y][r-1];
if(r==z)
b=0;
else
b=obst[r+1][z];
if(y==0)
c=w[z];
else
c=w[z]-w[y-1];
if(a+b+c-f[r]<min)
min=a+b+c-f[r];
}
obst[y][z]=min;
}
printf("%ld\n",obst[0][n-1]);
free(obst);
}
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Limit of running time - 10304

Post by htl » Wed Nov 20, 2002 6:02 pm

Recently the running time on almost all the problems is 10s. When I solve problem 10304, I found out that some people got AC though their programs ran over 10s. I'm so confused that why they didn't get TLE when their programs got rejudged?

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10304

Post by htl » Sun Nov 24, 2002 7:48 am

I improve my code by Knuth's theorem. But it got Memory Limit Exceed. Can someone give some suggetions?
[c]
#include<stdio.h>
#define MAX 2147483647
void main(void)
{
int n,x,y,r,z,**obst,**root,y1,z1;
long f[250],w[250],min,a,b,c;
while(scanf("%d",&n)!=EOF)
{
obst=(int **)malloc(sizeof(int *)*n);
root=(int **)malloc(sizeof(int *)*n);
for(x=0;x<n;x++)
{
obst[x]=(int *)malloc(sizeof(int)*(n-x));
root[x]=(int *)malloc(sizeof(int)*(n-x));
}
for(x=0;x<n;x++)
scanf("%ld",&f[x]),obst[x][0]=0,root[x][0]=x,w[x]=f[x];
if(n==1)
{
printf("0\n");
continue;
}
for(x=1;x<n;x++)
w[x]+=w[x-1];
for(x=1;x<n;x++)
for(y=0,z=x;z<n;y++,z++)
{
y1=root[y][z-1-y];
z1=root[y+1][z-(y+1)];
for(min=MAX,r=y1;r<=z1;r++)
{
if(r==0)
a=0;
else
a=obst[y][r-1-y];
if(r==z)
b=0;
else
b=obst[r+1][z-(r+1)];
if(y==0)
c=w[z];
else
c=w[z]-w[y-1];
if(a+b+c-f[r]<min)
min=a+b+c-f[r],root[y][z-y]=r;
}
obst[y][z-y]=min;
}
printf("%ld\n",obst[0][n-1]);
free(obst);
free(root);
}
}
[/c]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Mon Dec 23, 2002 6:53 pm

you have:
malloc()
malloc()
for x=... malloc() malloc()

and:
free()
free()

so not all memory is being deallocated

Battery
New poster
Posts: 1
Joined: Tue Jul 29, 2003 11:46 am
Location: South Korea, Asia
Contact:

10304 OBST TIME LIMIT

Post by Battery » Tue Jul 29, 2003 11:52 am

[c]#include <stdio.h>
#define MAXN 250 + 1
int n, solution;
int board[MAXN];
int sum[MAXN][MAXN];
int dynamic[MAXN][MAXN];
void in();
void sol();
void out();
void main()
{
while (scanf("%d",&n)!=EOF)
{
in();
sol();
out();
}
}

void in()
{
int i;
for (i=1;i<=n;i++) scanf("%d",&board);
}

void sol()
{
int i, j, k, p, q, Sum;
for (i=1;i<=n;i++)
{
Sum = 0;
for (j=i;j<=n;j++)
{
Sum += board[j];
sum[j] = Sum;
}
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n-i+1;j++)
{
p = j;
q = i + j - 1;
dynamic[p][q] = dynamic[p][q-1] + sum[p][q-1];
if (dynamic[p][q] > dynamic[p+1][q] + sum[p+1][q])
dynamic[p][q] = dynamic[p+1][q] + sum[p+1][q];
for (k=p+1;k<q;k++)
if (dynamic[p][q] > dynamic[p][k-1] + sum[p][k-1] + dynamic[k+1][q] + sum[k+1][q])
{
dynamic[p][q] = dynamic[p][k-1] + sum[p][k-1] + dynamic[k+1][q] + sum[k+1][q];
}
}
}
solution = dynamic[1][n];
}

void out()
{
printf("%d\n",solution);
}[/c]

I don't know what is wrong -_-;

Help me~~ :-?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 20, 2003 7:30 am

You need to use Knuth's algorithm, it runs in O(n^2) instead of O(n^3)..

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

10304

Post by DJYA » Tue Jan 27, 2004 7:37 pm

I'm confused for the 3rd sample input

Code: Select all

3 5 10 20
and it's output is 20

I don't know why and I think it should be 15.
because

Code: Select all

            20
           /   \
         10     5
Why the answer is 20 ?

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Jan 28, 2004 5:41 am

Recall that the order of the elements is the same as the order of the given frequencies and the tree must be a binary search tree.

For input 5, 10, 20

Code: Select all

  20               e3
 /   \      <=>   /   \
5    10          e1    e2
So your tree isn't a binary search tree.

The optimal binary search tree is

Code: Select all

    20           e3
    /            /
  10    <=>    e2
 /             /
5            e1
since the access costs is 2 * 5 + 1 * 10 + 0 * 20 = 20. (And any tree where 20 is not at the root automatically has cost at least 20).

DJYA
New poster
Posts: 7
Joined: Sat Jan 10, 2004 10:18 pm

Post by DJYA » Fri Jan 30, 2004 6:49 pm

THX a lot !!
I miss something

Post Reply

Return to “Volume 103 (10300-10399)”