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.

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]

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.

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?

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?