10304 - Optimal Binary Search Tree

[horape]

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]

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]

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.

[lcftc0203]

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]

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]

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.

[yiuyuho]

I will take a look. Thank You!

[sikder1588]

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.

[Marcus43]

Getting WA.
Anybody knows what could be wrong here?

Code: Select all

Never mind.
Was using low value as infinity.

[ryx]

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.