Page 2 of 4

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

Posted: Sun Nov 16, 2003 9:36 am could you please paste your code out , or give your algorithm in pseudocode?

THX!

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

Posted: Mon Nov 17, 2003 9:45 am
bnbolo wrote: could you please paste your code out , or give your algorithm in pseudocode?

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.

### 10003 Cutting Sticks

Posted: Thu Dec 18, 2003 12:43 am
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]

### 10003

Posted: Mon Apr 19, 2004 9:44 am
can we give me a way of solving the prob. 10003 'CUTTING STICK PROBLEM'

### MCM

Posted: Mon Apr 19, 2004 11:21 am
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[k] + m[k+1][c+1] is minimum. And by the prinicple of optimality
m[k] and m[k+1][c] has got to be optimal.

and finally m[c+1] is the reqd answer.

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

Posted: Sun Jul 17, 2005 10:52 am
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.

Posted: Tue Jul 19, 2005 11:18 am

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. Posted: Tue Jul 19, 2005 5:36 pm
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 ]

Posted: Mon Aug 01, 2005 5:42 pm
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?

### 10003 - Cutting Sticks (TLE)

Posted: Sat Sep 17, 2005 7:57 pm
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?

Posted: Mon Sep 19, 2005 1:48 am
Problem solved. Used arrays rather than vectors.

### 10003 - Java code - Need help

Posted: Wed Mar 22, 2006 1:42 am
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;
}
}
``````

Posted: Wed Mar 22, 2006 1:58 am
http://online-judge.uva.es/board/viewtopic.php?t=7429

Online judge uses Java 1.1 sans useful stuff.

Darko

Posted: Wed Mar 22, 2006 4:15 am
As Darko said, check out the HowTOs. BufferedReader, for some reason is now allowed in this online judge.

### 10003 TLE

Posted: Thu Jun 22, 2006 8:57 pm
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