10003 - Cutting Sticks

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

I don't really understand your mean.

Post by bnbolo » Sun Nov 16, 2003 9:36 am

:o could you please paste your code out , or give your algorithm in pseudocode?

THX!

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

Re: I don't really understand your mean.

Post by Algoritmo » Mon Nov 17, 2003 9:45 am

bnbolo wrote::o 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:
Image
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

Post by czar » 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]

Faiz_Buet
New poster
Posts: 1
Joined: Mon Apr 19, 2004 9:20 am

10003

Post by Faiz_Buet » Mon Apr 19, 2004 9:44 am

can we give me a way of solving the prob. 10003 'CUTTING STICK PROBLEM'

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

MCM

Post by sohel » 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[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)?

Post by Hackson » 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.
Last edited by Hackson on Tue Jul 19, 2005 5:37 pm, edited 1 time in total.
Solving problem is a no easy task...

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » 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. :wink:

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson » 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. :wink:
I 've got AC, thank you!!! [I have declared too large array size :oops: ]
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:

Post by I LIKE GN » Mon Aug 01, 2005 5:42 pm

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 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 = 8) 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)

Post by pigwoley » 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?

pigwoley
New poster
Posts: 3
Joined: Sat Jun 25, 2005 2:06 am

Post by pigwoley » Mon Sep 19, 2005 1:48 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

Post by jambon » 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. :D

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;
	}
}

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Mar 22, 2006 1:58 am

Check this link:
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

Post by chunyi81 » 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.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10003 TLE

Post by shihabrc » 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
Last edited by shihabrc on Fri Jun 23, 2006 5:31 pm, edited 1 time in total.
Shihab
CSE,BUET

Post Reply

Return to “Volume 100 (10000-10099)”