## 10304 - Optimal Binary Search Tree

Moderator: Board moderators

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: Limit of running time - 10304

htl wrote: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?
It seems that when they change the time limit, there is no rejudgement.

Saludos,
HoraPe

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 10304 WA

I got WA, even though it works with my test cases. Can someone give me some more test data, especially where it is wrong?

[cpp]
/* @JUDGE_ID: xxxxxx 10304 C++ */
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int buildTree(vector<int> &freqs, int start, int end, int depth)
{
if (start == end)
return 0;
int max = start;
for (int i = max+1; i < end; i++)
if (freqs > freqs[max])
max = i;
int cost = depth * freqs[max];
int minCost = buildTree(freqs, start, max, depth+1) +
buildTree(freqs, max+1, end, depth+1);
for (int j = max+1; j < end && freqs[j] == freqs[max]; j++)
{
int c = buildTree(freqs, start, j, depth+1) +
buildTree(freqs, j+1, end, depth+1);
if (c < minCost)
minCost = c;
}
return cost + minCost;
}

int main(int argc, char *argv[])
{
int n;
while (cin >> n)
{
vector<int> f;
int freq;
while (n--)
{
cin >> freq;
f.push_back(freq);
}
cout << buildTree(f, 0, f.size(), 0) << endl;
}
return 0;
}
[/cpp]

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

### 10304 OBST

I tried this with a O(n^3) DP approach. But it times out. Later i came to know there exists a Knuth's O(n^2) algorithm for finding OBST. Could someone please explain what it is? Thanks in advance.
I am signing an important document!

lcftc0203
New poster
Posts: 1
Joined: Thu Oct 12, 2006 11:57 am
DP in O(n^3) can also accept, my program use 18.x seconds.
and DP in O(n^2) use 1.5 seconds.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Joe Smith wrote: 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.
I can see why that is intuitive to believe in, but it is still not clear to me that it is true for all cases. can you explain some more please?

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10304 - Optimal Binary Search Tree

Naani wrote:I tried this with a O(n^3) DP approach. But it times out. Later i came to know there exists a Knuth's O(n^2) algorithm for finding OBST. Could someone please explain what it is? Thanks in advance.
Maybe you can check the optimal binary search tree section on CLRS. The O(n^2) DP is very similar to that one except that you need to change the cost function.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### Re: 10304 - Optimal Binary Search Tree

I will take a look. Thank You!

sikder1588
New poster
Posts: 5
Joined: Thu Jun 21, 2012 9:11 am

### Re: 10304 - Optimal Binary Search Tree

Hello,

I maybe be asking for a lot, but can anyone please explain me the O(n^2) algorithm in high level language?
That would be a great help.

Keep Going
Bristy Sikder

Marcus43
New poster
Posts: 3
Joined: Fri Jan 11, 2013 7:19 am

### Re: 10304 - Optimal Binary Search Tree

Getting WA.
Anybody knows what could be wrong here?

Code: Select all

Never mind.
Was using low value as infinity.

ryx
New poster
Posts: 4
Joined: Fri Jul 10, 2015 2:52 am

### Re:

Larry wrote:You need to use Knuth's algorithm, it runs in O(n^2) instead of O(n^3)..
Could you explain what Knuth's algorithm is?
Thank you so much.