10304 - Optimal Binary Search Tree

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: Limit of running time - 10304

Post by horape » Sun Feb 08, 2004 6:41 pm

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

Post by dpitts » Tue Mar 16, 2004 4:15 am

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

Post by Naani » Thu Sep 28, 2006 12:37 pm

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

Post by lcftc0203 » Thu Oct 12, 2006 12:01 pm

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:

Post by yiuyuho » Mon Jun 18, 2007 6:24 pm

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

Post by DD » Thu Mar 31, 2011 5:52 pm

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

Post by yiuyuho » Wed Nov 16, 2011 9:39 am

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

Post by sikder1588 » Thu Jun 28, 2012 4:40 pm

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

Post by Marcus43 » Sat Jan 19, 2013 3:00 pm

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:

Post by ryx » Thu Oct 01, 2015 3:16 am

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.

Post Reply

Return to “Volume 103 (10300-10399)”