## 10003 - Cutting Sticks

Moderator: Board moderators

bnbolo
New poster
Posts: 2
Joined: Mon Nov 03, 2003 9:21 am

### I don't really understand your mean.

THX!
Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

### Re: I don't really understand your mean.

THX!
Bad news: No, I can't paste or post my code here
Good news: I have made a page explaining my solution

It was hard for me to think about a complete solution untill I wrote this in a piece of paper:

For more images and my complete explanation, have a look at:
http://200.167.46.219/ACM/10003.htm
Fell free to correct me if I wrote something wrong.
czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

### 10003 Cutting Sticks

I was wondering if anyone had any suggestions on speeding this program up keeping the top down structure of the solution (It gets accepted but takes 9 secs on the test cases).

[cpp]
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

typedef vector<int> VI; typedef vector<vector<int> > VVI;
typedef vector<string> VS; typedef vector<vector<string> > VVS;
typedef pair<int, int> PII;

VVI memo;

int doit(int len, const VI &cuts, int bin, int ein, int sl, int el) {

int ret = INT_MAX;

if(memo[bin][ein]) return memo[bin][ein];

if(bin >= ein) return 0;

for(int i = bin; i < ein; i++) {

int l = doit(cuts-sl, cuts, bin, i, 0, cuts);
int r = doit(el-cuts, cuts, i+1, ein, cuts, el);
ret = min( ret, l+r+len );

}

return memo[bin][ein] = ret;

}

int main() {

int len;

while(cin>>len) {

if(len == 0) break;

cin.ignore();

int ncuts, cut;
VI cuts;

cin>>ncuts; cin.ignore();
memo = VVI(ncuts+1, VI(ncuts+1));

for(int i = 0; i < ncuts; i++) {

cin>>cut; cin.ignore();
cuts.push_back(cut);

}

cout<<"The minimum cutting is "<<doit(len, cuts, 0, ncuts, 0, len)<<"."<<endl;

}

return 0;

}
[/cpp]
Faiz_Buet
New poster
Posts: 1
Joined: Mon Apr 19, 2004 9:20 am

### 10003

can we give me a way of solving the prob. 10003 'CUTTING STICK PROBLEM'
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### MCM

This problem is very similar to matrix chain multiplication.

Maintain an array m[][] and update it dynamically.

Suppose you are given a stick of length N and c cuts are to be made. Then, at first a cut is to be made at k ( k<c+1) such that
m[1][k] + m[k+1][c+1] is minimum. And by the prinicple of optimality
m[1][k] and m[k+1][c] has got to be optimal.

and finally m[1][c+1] is the reqd answer.
Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

### 10003 Cutting Sticks TLE, shouldn't it be O(n^3)?

Hi there, I have written 10003 using nearly the same algo as Matrix Chain Multiplication and submit it, but it gives me TLE.
I wonder if I have made anything wrong or there exists a better Algorithm.
Here comes my Code:

Code: Select all

``````Accepted, NO SPOILING!
``````
I hope someone can answer my question...

btw, DP is very difficult too...

Thanks a lot.
Last edited by Hackson on Tue Jul 19, 2005 5:37 pm, edited 1 time in total.
Solving problem is a no easy task...
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Code: Select all

``````for i := 0 to 2000 do
for j := 0 to 2000 do
dp[i, j] := 99999;``````
You only need to initialize the variable as needed. No need to always perform 2000*2000 loop as above.
Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am
angga888 wrote:

Code: Select all

``````for i := 0 to 2000 do
for j := 0 to 2000 do
dp[i, j] := 99999;``````
You only need to initialize the variable as needed. No need to always perform 2000*2000 loop as above.
I 've got AC, thank you!!! [I have declared too large array size ]
Solving problem is a no easy task...
I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
hello all......
i amm not sure how DP logic works here...
let's say we to cut at 2,4,7 and the stick is up to 10.
when considering the calculation of 0 to 7
we have the following sub-chains...
0 2, 2 7,
0 4, 4 7,
0 7, 0 2, 2 7
0 7, 0 4,
for the first two rows the calculations are fine(using previous values)
for the 3rd and 4th 0 7, and 0 2, are easy to know but what abot 2 7 and 0 4 ???
since while i calculated 2 7 the stick was up to 8(10-2 = but now it's up to 5
(7-2 = 5). so how to get the value with pre-calculation?
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
pigwoley
New poster
Posts: 3
Joined: Sat Jun 25, 2005 2:06 am

### 10003 - Cutting Sticks (TLE)

Hey, I implemented a solution similar to matrix-chain multiplication. Because it is an O(n^3) algorithm, and n is at most 51, I shouldn't have to worry about anything else, right? I have no idea what is wrong. Here is my code:

Code: Select all

``````// Headers, etc...

#define in cin

using namespace std;

vector<int> CutSpots;
int length, cuts;
vector< vector<int> > memo;
int MV = 1<<15;

int BestWay(int a, int b)
{
if(memo[a][b] != -1)
return memo[a][b];

if(b-a == 1)
return memo[a][b] = 0;

int minv = MV;
for(int i = a+1; i < b; ++i)
{
//cut here
minv = min(minv, (CutSpots[i]-CutSpots[a]) + (CutSpots[b]-CutSpots[i])
+ BestWay(a,i) + BestWay(i, b) );

}
return memo[a][b] = minv;
}

int main()
{
//ifstream in("in.txt");
while(1)
{
in >> length;
if(length == 0)
break;

in >> cuts;

CutSpots = vector<int>(cuts);

CutSpots.push_back(0);

//given in increasing order
for(int i = 0; i < cuts; ++i)
in >> CutSpots[i+1];

CutSpots.push_back(length);

memo = vector< vector<int> >(cuts+2, vector<int>(cuts+2,-1));

cout << "The minimum cutting is " << BestWay(0, cuts+1) << "." << endl;
}
return 0;
}

``````
What did I do wrong?
pigwoley
New poster
Posts: 3
Joined: Sat Jun 25, 2005 2:06 am
Problem solved. Used arrays rather than vectors.
jambon
New poster
Posts: 1
Joined: Tue Oct 08, 2002 7:31 pm

### 10003 - Java code - Need help

Hi all,

I am new in Java and this is one of my first Java programs. I submited and got "Compile Error". Please help me. I tested in my computer and it worked fine. At least it compiled.

Here is my code. Please take a look.

Code: Select all

``````import java.io.*;
import java.util.*;

class p10003
{
public static void main(String args[]) throws IOException
{

while (m != 0)
{
a = new int[n];
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(sp[i]);

d = new int[m + 1][m + 1];
for (int i = 0; i <= m; i++)
for (int j = 0; j <= m; j++) d[i][j] = -1;

System.out.println("The minimum cutting is " + C(0, m) + ".");

}
}

static int[][] d;
static int[] a;

static int C(int left, int right)
{
if (d[left][right] != -1) return d[left][right];

int ret = 10000;
for (int i = 0; i < a.length; i++)
if (a[i] > left && a[i] < right)
{
ret = Math.min(ret, C(left, a[i]) + C(a[i], right));
}
if (ret == 10000) ret = 0;
else ret += right - left;
d[left][right] = ret;
return ret;
}
}
``````
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
http://online-judge.uva.es/board/viewtopic.php?t=7429

Online judge uses Java 1.1 sans useful stuff.

Darko
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
As Darko said, check out the HowTOs. BufferedReader, for some reason is now allowed in this online judge.
shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 10003 TLE

I've solved this problems with a simillar approach to matrix chain multiplication. i think its complexity is O(L^2*n) where L is the length of the stick and n is the number of cut points. Since n is small this should run in time. But, i'm gettin TLE. Can someone help me plz

Code: Select all

``````
//removed after AC

``````
Plz hlp.

-Shihab
Last edited by shihabrc on Fri Jun 23, 2006 5:31 pm, edited 1 time in total.
Shihab
CSE,BUET