10003  Cutting Sticks
Moderator: Board moderators

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
you used O(L^2*n), L can be 1000 at most, and n only 50
L*L*n = 1000*1000*50 = 50000000 and
n*n*n = 50 * 50 * 50 = 125000
the original matrix chain multiplication algorithm takes only O(n^3) time, that should be used for this problem
L*L*n = 1000*1000*50 = 50000000 and
n*n*n = 50 * 50 * 50 = 125000
the original matrix chain multiplication algorithm takes only O(n^3) time, that should be used for this problem
ishtiak zaman

the world is nothing but a good program, and we are all some instances of the program

the world is nothing but a good program, and we are all some instances of the program
10003 Cutting Sticks, why TLE?
I am using a straightforward recursion+memoization based attack at this problem. Worked for all DP problems I've tried before, but I'm getting TLE on this one. My recurrrence relation is
where k is a cut. Is there a better/faster way?
Code: Select all
cost(start, end)=min(cost(start,k)+cost(k,end)+(endstart))
hopeless
i was looking for a solution.
amazingl thing is that i have tried as the same method like you and found wrong answer.
if you get any help would u please forward me?
debajyoti
debajyoti_mondal_cse@yahoo.com
amazingl thing is that i have tried as the same method like you and found wrong answer.
if you get any help would u please forward me?
debajyoti
debajyoti_mondal_cse@yahoo.com
I use DP method to solve the problem,but still got WA.
Who can give me test data to test my program?
Thanks in advance!
Who can give me test data to test my program?
Thanks in advance!
Code: Select all
#include <stdio.h>
#include <limits.h>
int table[100][100]={0};
int profit[100][100]={0};
int data[100];
int n;
int len;
void process(){
int i,j,k,min=INT_MAX;
for(i=n1;i>=1;i)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=ji;k++){
if( table[i][jk]+table[j+1k][j]<min )
min=table[i][jk]+table[j+1k][j];
}
table[i][j]=min;
}
}
void profit_process(){
int i,j,k,min=INT_MAX;
for(i=n1;i>=1;i)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=ji;k++){
if( i==jk && j+1k==j ){
if( table[i][jk]+table[j+1k][j]<min )
min=table[i][jk]+table[j+1k][j];
}else{
if( i==jk ){
if( profit[j+1k][j]+table[i][j]<min )
min=profit[j+1k][j]+table[i][j];
}else if( j+1k==j ){
if( profit[i][jk]+table[i][j]<min )
min=profit[i][jk]+table[i][j];
}else{
if( profit[i][jk]+profit[j+1k][j]+table[i][j]<min )
min=profit[i][jk]+profit[j+1k][j]+table[i][j];
}
}
}
profit[i][j]=min;
}
printf("The minimum cutting is %d.\n",profit[1][n]);
}
int main(){
int i,pre,temp;
while( scanf("%d",&len)==1 && len ){
scanf("%d",&n);
n=n+1;
pre=0;
for(i=1;i<n;i++){
scanf("%d",&temp);
profit[i][i]=table[i][i]=temppre;
pre=temp;
}
profit[i][i]=table[i][i]=lenpre;
process();
profit_process();
}
return 0;
}

 New poster
 Posts: 19
 Joined: Sun Jun 18, 2006 4:07 pm
 Contact:
10003 TLE
This problem is based upon Matrix Multiplication .
I wrote a top down DP solution to it .which is being timed out. Can't we have top down solution to this problem get accepted ??
Or if there is any mistake in optimization in solution then plz point it out. My code goes as follows.
I wrote a top down DP solution to it .which is being timed out. Can't we have top down solution to this problem get accepted ??
Or if there is any mistake in optimization in solution then plz point it out. My code goes as follows.
Code: Select all
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int a[1001];
int data[1001][1001];
class sumant
{
public:
int count;
int input()
{
int l,x,n;
cin>>l;
while(l!=0)
{
count=0;
for(int i=0;i<=l;i++)
for(int j=0;j<=l;j++)
data[i][j]=1;
cin>>n;
for(int i=0;i<=l;i++)
a[i]=0;
for(int i=0;i<n;i++)
{
cin>>x;
a[x]=1;
}
int z=memo(0,l);
cout<<"The minimum cutting is "<<z<<".\n";
//cout<<count<<"\n";
cin>>l;
}
}
int memo(int p,int q)
{
if(data[p][q]==1)
{
int z=doit(p,q);
data[p][q]=z;
return z;
}
else
{
return data[p][q];
}
}
int doit(int p,int q)
{
int min=100000000,m;
bool flag=false;
for(int i=p+1;i<q;i++)
{
if(a[i]!=0)
{
flag=true;break;
}
}
if(!flag)
return 0;
for(int i=p+1;i<q;i++)
{
if(a[i]==1)
{
//cout<<"madar";
m=qp+memo(p,i)+memo(i,q);
if(min>m)
min=m;
flag=true;
}
}
return min;
}
};
int main()
{
sumant s;
s.input();
return 0;
}
Top  down DP is enough to solve this problem.
Your implementation has too waste.
Instead of
Find a way with
ADD : Don't open a new thread if it already exists for the problem.
Your implementation has too waste.
Instead of
Code: Select all
int a[1001];
int data[1001][1001];
Code: Select all
int a[51];
int data[51][51];
Hello all,
I'm a dynamic programming newbie.
I'm trying to solve this problem with a recursive function with memoization. However, I'm getting Time limit exceeded. I calculate the cost of cutting stick which starts at position i and ends and position j by finding the minimum cost of summing (ji) plus the cost of cutting the stick from i to P[k] and from P[k] to j, where P[k] is a given partition point.
I read there's a faster algorithm, but I can't understand it.
Any advice?
Thanks for helping a newbie!
If you are interested, here's my (slow) code:
Thanks again!
I'm a dynamic programming newbie.
I'm trying to solve this problem with a recursive function with memoization. However, I'm getting Time limit exceeded. I calculate the cost of cutting stick which starts at position i and ends and position j by finding the minimum cost of summing (ji) plus the cost of cutting the stick from i to P[k] and from P[k] to j, where P[k] is a given partition point.
I read there's a faster algorithm, but I can't understand it.
Any advice?
Thanks for helping a newbie!
If you are interested, here's my (slow) code:
Code: Select all
I got accepted thanks to the help of emotional blind.
Last edited by andmej on Wed Mar 12, 2008 4:32 pm, edited 1 time in total.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Code: Select all
memset(cache, 1, sizeof(cache));
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
Another approach:
remove memset part
and
insert
after this block
remove memset part
and
insert
Code: Select all
for(int i=0;i<=n+1;++i){
for(int j=i;j<=n+1;++j){
cache[p[i]][p[j]]=1;
}
}
Code: Select all
for (int i=1; i<=n; ++i){
cin >> p[i];
}
Thanks a lot, emotional blind. That made the trick and got my program accepted.
I thought memset was the fastest way to initialize a block of memory. However, you made my notice that I'm wasting a lot of space when using a matrix of 1001 * 1001 integers. I think it's possible to solve it using a 52 * 52 integers matrix, I will try to do it.
Thanks again, emotional blind!
I thought memset was the fastest way to initialize a block of memory. However, you made my notice that I'm wasting a lot of space when using a matrix of 1001 * 1001 integers. I think it's possible to solve it using a 52 * 52 integers matrix, I will try to do it.
Thanks again, emotional blind!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
10003  Cutting Sticks
why Runtime error?
Code: Select all
#include<iostream>
using namespace std;
#define INF 4294967295
int num,l;
int length;
bool cut[100000];
unsigned long s[2005][2005] = {0};
// will print the ordering of cutting
//this part is optional to UVA 10003 problem
void print(int i,int j)
{
if( s[i][j] != 0)
printf("%d ",s[i][j]);
else return;
print(i,s[i][j]);
print(s[i][j],j);
}
void matrix_chain()
{
unsigned long m[500][500] = {0};
//int **m;
unsigned int q;
int l,j,i,k;
int check = 0;
memset(s,0,sizeof(s));
//memset(m,0,sizeof(m));
for( l = 2; l <= length; l++)
{
for( i = 0; i <= lengthl; i++)
{
j = i+l;
m[i][j] = INF;
for( k = i + 1; k < j;k++)
{
if( cut[k] == true )
{
check = 1;
q = m[i][k] + m[k][j] + (j  i);
if( q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
if( check == 0)
{
m[i][j] = 0;
}
check = 0;
}
}
cout << m[0][length] << ".\n" ;
print(0,length);
cout << endl;
}
int main(void)
{
int size,i,k,m,n,c = 1;
int p[2010] = {0};
while(1)
{
cin >> l;
length = l;
if(!l) break;
cin >> n;
memset(cut,false,sizeof(cut));
for(i = 1; i <= n; i++)
{
cin >> m;
cut[m] = true;
}
cout << "The minimum cutting is ";
matrix_chain();
}
return 0;
}

 New poster
 Posts: 18
 Joined: Sat Nov 20, 2010 7:44 pm
Re: 10003  Cutting Sticks
libreiries...you need "string.h" to memset,,,too "stdio.h"
Re: 10003  Cutting Sticks
Try to find a O(n*n) algorithm...O(n*n*l) fails.
You tried your best and you failed miserably. The lesson is 'never try'. Homer Simpson
Re: 10003  Cutting Sticks
HELPPP... i really don't get to understand the meaning of this problem +_+
can someone please give a short explanation please?
i'm already see http://www.algorithmist.com/index.php/U ... xplanation
but still don't get the problem meaning, very stressed +_+
Thanks in advande
can someone please give a short explanation please?
i'm already see http://www.algorithmist.com/index.php/U ... xplanation
but still don't get the problem meaning, very stressed +_+
Thanks in advande