10003  Cutting Sticks
Moderator: Board moderators
I don't really understand your mean.
could you please paste your code out , or give your algorithm in pseudocode?
THX!
THX!
Re: I don't really understand your mean.
Bad news: No, I can't paste or post my code herebnbolo wrote: could you please paste your code out , or give your algorithm in pseudocode?
THX!
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
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(cutssl, cuts, bin, i, 0, cuts);
int r = doit(elcuts, 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]
[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(cutssl, cuts, bin, i, 0, cuts);
int r = doit(elcuts, 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]
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.
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.
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:
I hope someone can answer my question...
btw, DP is very difficult too...
Thanks a lot.
I wonder if I have made anything wrong or there exists a better Algorithm.
Here comes my Code:
Code: Select all
Accepted, NO SPOILING!
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...
Code: Select all
for i := 0 to 2000 do
for j := 0 to 2000 do
dp[i, j] := 99999;
I 've got AC, thank you!!! [I have declared too large array size ]angga888 wrote:You only need to initialize the variable as needed. No need to always perform 2000*2000 loop as above.Code: Select all
for i := 0 to 2000 do for j := 0 to 2000 do dp[i, j] := 99999;
Solving problem is a no easy task...

 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...
please help me understand...
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 subchains...
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(102 = but now it's up to 5
(72 = 5). so how to get the value with precalculation?
i amm not sure how DP logic works here...
please help me understand...
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 subchains...
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(102 = but now it's up to 5
(72 = 5). so how to get the value with precalculation?
There are two tragedies in life one is to lose your hearts' desire and another is to gain it  GBS.
10003  Cutting Sticks (TLE)
Hey, I implemented a solution similar to matrixchain 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:
What did I do wrong?
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(ba == 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;
}
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.
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
{
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(stdin.readLine());
while (m != 0)
{
int n = Integer.parseInt(stdin.readLine());
String[] sp = stdin.readLine().split(" ");
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) + ".");
m = Integer.parseInt(stdin.readLine());
}
}
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;
}
}
Check this link:
http://onlinejudge.uva.es/board/viewtopic.php?t=7429
Online judge uses Java 1.1 sans useful stuff.
Darko
http://onlinejudge.uva.es/board/viewtopic.php?t=7429
Online judge uses Java 1.1 sans useful stuff.
Darko
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
Plz hlp.
Shihab
Code: Select all
//removed after AC
Shihab
Last edited by shihabrc on Fri Jun 23, 2006 5:31 pm, edited 1 time in total.
Shihab
CSE,BUET
CSE,BUET