10304 - Optimal Binary Search Tree

[Joe Smith]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

and:
free()
free()

so not all memory is being deallocated

[Battery]

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

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

[DJYA]

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]

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]

THX a lot !!
I miss something