Page 3 of 4
Posted: Fri Jun 23, 2006 11:22 am
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

Posted: Fri Jun 23, 2006 5:30 pm
Thanx a lt. I took too much redaundant states. Now, i've changed my soln. and got AC. Thanx again.

-Shihab

### 10003 Cutting Sticks, why TLE?

Posted: Sat Jul 01, 2006 9:34 am
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

Code: Select all

``cost(start, end)=min(cost(start,k)+cost(k,end)+(end-start))``
where k is a cut. Is there a better/faster way?

### hopeless

Posted: Sat Dec 02, 2006 11:48 am
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

Posted: Thu Jan 25, 2007 7:24 pm
I use DP method to solve the problem,but still got WA.
Who can give me test data to test my program?

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=n-1;i>=1;i--)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=j-i;k++){
if( table[i][j-k]+table[j+1-k][j]<min )
min=table[i][j-k]+table[j+1-k][j];
}
table[i][j]=min;
}

}

void profit_process(){
int i,j,k,min=INT_MAX;
for(i=n-1;i>=1;i--)
for(j=i+1;j<=n;j++){
min=INT_MAX;
for(k=1;k<=j-i;k++){
if( i==j-k && j+1-k==j ){
if( table[i][j-k]+table[j+1-k][j]<min )
min=table[i][j-k]+table[j+1-k][j];
}else{
if( i==j-k ){
if( profit[j+1-k][j]+table[i][j]<min )
min=profit[j+1-k][j]+table[i][j];

}else if( j+1-k==j ){
if( profit[i][j-k]+table[i][j]<min )
min=profit[i][j-k]+table[i][j];
}else{
if( profit[i][j-k]+profit[j+1-k][j]+table[i][j]<min )
min=profit[i][j-k]+profit[j+1-k][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]=temp-pre;
pre=temp;
}
profit[i][i]=table[i][i]=len-pre;
process();
profit_process();
}
return 0;
}``````

### 10003 TLE

Posted: Mon Feb 05, 2007 8:08 am
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.

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)
{
m=q-p+memo(p,i)+memo(i,q);
if(min>m)
min=m;
flag=true;
}
}

return min;
}
};
int main()
{
sumant s;
s.input();
return 0;
}
``````

Posted: Tue Feb 06, 2007 3:36 pm
Top - down DP is enough to solve this problem.

Code: Select all

``````int a[1001];
int data[1001][1001];
``````
Find a way with

Code: Select all

``````int a[51];
int data[51][51];
``````

Posted: Wed Mar 12, 2008 6:28 am
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 (j-i) 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.

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.
``````
Thanks again!

Posted: Wed Mar 12, 2008 12:08 pm

Code: Select all

``memset(cache, -1, sizeof(cache));``
This part is costly. Try using O(n^2) memory. Here n<50, which is much smaller.

Posted: Wed Mar 12, 2008 12:12 pm
Another approach:

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;
}
}``````
after this block

Code: Select all

``````for (int i=1; i<=n; ++i){
cin >> p[i];
} ``````

Posted: Wed Mar 12, 2008 4:13 pm
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!

### 10003 - Cutting Sticks

Posted: Thu Dec 23, 2010 12:05 pm
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 <= length-l; 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;
}
``````

### Re: 10003 - Cutting Sticks

Posted: Sun Dec 26, 2010 11:40 am
libreiries...you need "string.h" to memset,,,too "stdio.h"

### Re: 10003 - Cutting Sticks

Posted: Sun Jun 17, 2012 2:09 pm
Try to find a O(n*n) algorithm...O(n*n*l) fails.

### Re: 10003 - Cutting Sticks

Posted: Mon Jun 03, 2013 1:09 pm
HELPPP... i really don't get to understand the meaning of this problem +_+