10304 - Optimal Binary Search Tree
Moderator: Board moderators
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.
-
- 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...
(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...
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 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.
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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.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.
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][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]
[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]
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]
[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]
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?
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[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]
[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]
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[1][n];
}
void out()
{
printf("%d\n",solution);
}[/c]
I don't know what is wrong -_-;
Help me~~
#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~~
10304
I'm confused for the 3rd sample input
and it's output is 20
I don't know why and I think it should be 15.
because
Why the answer is 20 ?
Code: Select all
3 5 10 20
I don't know why and I think it should be 15.
because
Code: Select all
20
/ \
10 5
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
So your tree isn't a binary search tree.
The optimal binary search tree is
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).
For input 5, 10, 20
Code: Select all
20 e3
/ \ <=> / \
5 10 e1 e2
The optimal binary search tree is
Code: Select all
20 e3
/ /
10 <=> e2
/ /
5 e1