## 10304 - Optimal Binary Search Tree

Moderator: Board moderators

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

### 10304 - Optimal Binary Search Tree

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

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]),obst[x]=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];
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]<min)
min=a+b+w[x][y-x]-w[r];
}
obst[x][y-x]=min;
}
printf("%ld\n",obst[n-1]);
free(obst);
free(w);
}
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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,w,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[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

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

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,w,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,root[x]=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[n-1]);
free(obst);
free(root);
}
}
[/c]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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

[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[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:
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

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 ?

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
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
THX a lot !!
I miss something