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

otavio
New poster
Posts: 2
Joined: Wed Oct 16, 2002 4:13 pm
Location: Brazil

10003 - Cutting Sticks

Post by otavio » Sat Oct 19, 2002 9:52 pm

I have written a program for the 10003 problem, but Jugde tells me that it uses more time than allowed.

I can't understand, because I have generated a long test set (over 160 entries with 50 cutting points each) and my program runs for less than 1 second in a Pentium 200.

What's wrong?

Ot

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Sun Nov 10, 2002 8:06 am

Hi,

Did u notice that this is a simple example of "Matrix Chain Mutiplcation" dp

algorithm? In case u have used that and still getting TLE...u may find this

code helpful :)

Code: Select all

#include<stdio.h>
#include<values.h>

#define MAX 60
#define inf MAXLONG

int main()
{
 long L,N,i,j,n,x,y,q,l,k,t,sum,m[MAX][MAX],p[MAX];

 while(scanf("%ld",&L)==1 && L)
 {
   scanf("%ld",&N);

   y = 0;

   for(i=1;i<=N;i++)
       {
	scanf("%ld",&x);
	p[i] = x - y;
	y = x;
       }
   p[i] = L - y;

   n = i;

   for(i=0;i<=n;i++)
       m[i][i] = 0;

   for(l=2;l<=n;l++)
      {
	for(i=1;i<=n-l+1;i++)
	   {
	    j = i + l - 1;
	    m[i][j] = inf;


	    for(k=i;k<=j-1;k++)
	       {
		q = m[i][k] + m[k+1][j] ;

		sum = 0;

		for(t=i;t<=j;t++)
		    sum += p[t];

		q += sum;

		if(q<m[i][j])
		   m[i][j] = q;
	       }
	   }
      }

    printf("The minimum cutting is %ld.\n",m[1][n]);
 }
 return 0;
}


ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

10003

Post by ec3_limz » Wed Dec 25, 2002 7:35 am

How do I solve #10003: Cutting Sticks using Dynamic Programming (DP)? I have seen others' source code, but I don't understand how and why they work.

Please tell me.

DP is so complicated :(

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Dec 25, 2002 6:13 pm

It's a similar problem to matrix multiplication, so if you're familiar with that DP (which is in most intro texts) problem, then maybe you can think that way.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10003 (after New Judgement)

Post by hank » Mon Jan 20, 2003 2:51 pm

after New Judgement I got wrong answer.
but I don't know why.
Anyone can help me? :(
[c]#include "stdio.h"
int dim[50],cost[50][50],cut;
int Min(int a,int b)
{
if(a>b) return b;
return a;
}
void clear_var()
{
int i,j;
for(i=0;i<=cut;i++)
for(j=0;j<=cut;j++)
cost[j]=0;
for(i=0;i<50;i++)
dim=0;
}
void DP()
{
int i,j,k;
for( j=2 ; j<=cut; j++)
{
for(i=cut ; i>=0 ; i--)
{
for(k= i+1 ; k<=cut ; k++ )
{
if( i<k && i<j && k<j )
{
if( k==i+1 ){
cost[j]= cost[k] + cost[k][j] +dim[j]-dim;
}else{
cost[j]= Min(cost[j],cost[k]+cost[k][j]+dim[j]-dim);
}
}
}
}
}
}
void main()
{
int len,i,j;
while( scanf("%d",&len) == 1)
{
if(len==0) break;
clear_var();
scanf("%d",&cut);
cut++;
dim[0]=0;
for(i=1;i<cut;i++)
scanf("%d",&dim);
dim[cut]=len;
DP();
printf("The minimum cutting is %d.\n",cost[0][cut]);
}
}

[/c]

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden

Post by Astrakan » Tue Jan 21, 2003 11:29 am

Try this case:

Code: Select all

1000
49
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
Output should be 1279.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Thu Jan 30, 2003 10:48 am

I can't understand what the problem said.
Anybody can tell me? :cry:

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Re: How to solve #10003: Cutting Sticks using DP?

Post by turuthok » Thu Jan 30, 2003 12:21 pm

ec3_limz wrote:How do I solve #10003: Cutting Sticks using Dynamic Programming (DP)? I have seen others' source code, but I don't understand how and why they work.

Please tell me.

DP is so complicated :(
DP is so interesting ... whoever came up with it was a genius. It might be complicated at first, but once you get used to it, you're gonna love it.

The main idea for this problem is that we can try to solve the min-cost for lowest range of cut-points, and then expand our range one by one until you got the cost for the maximum range.

Let's say you have cut-points a, b, c (strictly increasing position) of a stick whose length is x. Then what I meant by cost of lowest range would be the cost to cut 0..a, a..b, b..c, and c..x. Once you got the cost for all 4 of them, you proceed with calculating wider range ... in this case, the next range would be 0..b, a..c, b..x ... Calculating min-cost for these ranges are easy since you already got the min-cost for smaller ranges ...

I don't want to take away all your fun, so we should stop here ...

-turuthok-

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

10003 (Cutting Sticks) WA I/O

Post by UFP2161 » Thu Jul 31, 2003 11:27 pm

Could someone give me correct output for the following randomly generated input? Thanks in advance!
970
7
108 167 225 275 411 651 824
111
10
10 17 28 30 37 44 47 49 77 94
318
17
19 33 40 48 63 77 89 92 101 121 149 150 162 174 197 198 261
830
11
32 69 104 170 208 219 327 420 552 582 799
311
10
22 29 56 89 110 129 158 161 217 291
578
6
50 128 148 274 408 542
871
17
21 31 66 105 129 159 168 210 257 261 312 402 446 465 544 615 653
730
2
273 426
456
4
2 17 112 375
355
5
61 67 161 183 194
0

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Aug 09, 2003 8:22 am

Code: Select all

The minimum cutting is 2778.
The minimum cutting is 348.
The minimum cutting is 1203.
The minimum cutting is 2827.
The minimum cutting is 1034.
The minimum cutting is 1572.
The minimum cutting is 3271.
The minimum cutting is 1156.
The minimum cutting is 929.
The minimum cutting is 776.

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

Re: How to solve #10003: Cutting Sticks using DP?

Post by Algoritmo » Sat Nov 01, 2003 3:50 am

ec3_limz wrote:How do I solve #10003: Cutting Sticks using Dynamic Programming (DP)? I have seen others' source code, but I don't understand how and why they work.

Please tell me.

DP is so complicated :(
ec3_limz, have a look at this tutorial:
http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

From example 2 of this tutorial I introduced myself into what is DP. In problem 10003 I practiced it by the first time.

My first solution was made by backtracking, with this simple recursive definition:

Code: Select all

MinCost (Stick):
 if there are no cuts, Min Cost = 0;
 else:
  for each cut n
   Cost of n = Min Cost (Stick at left of n) + Min Cost (Stick at right of n)
   Min Cost = Smallest Cost
In C++, the program is just a bit bigger than this definition. This program was capable of giving any answer, but it was too costy and got Time Limit Exceeded.
On my first DP solution, I made 1 cut at each stage and each stage did only depend on the information computed in previous stage. It was a VERY complex program, which took me many hours. It also worked, but also got Time Limit Exceeded.

Then I followed what turuthok said, defining stage N as the calculation of sticks with length N. Each stage now depends on ALL previously computed ones. With a simple drawing I perceived that is the correct way to do the DP. Memory allocation requirements were now much lower and my program was finally Accepted, in 1 sec.

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

Post by bnbolo » Mon Nov 03, 2003 9:36 am

  • The minimum cutting is 2778.
    The minimum cutting is 351.
    The minimum cutting is 1209.
    The minimum cutting is 2974.
    The minimum cutting is 1068.
    The minimum cutting is 1662.
    The minimum cutting is 3345.
    The minimum cutting is 1156.
    The minimum cutting is 929.
    The minimum cutting is 776.
I don't know where is wrong.

ColdAndUgly
New poster
Posts: 2
Joined: Fri Nov 07, 2003 8:18 am

Post by ColdAndUgly » Fri Nov 07, 2003 8:22 am

I got the same output as bnbolo did.


Here is my code, if someone could make a suggestion, i would appreciate it.

[cpp]
// 10003 - Cutting Sticks.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

int iCutList[60][2];
int iWorkingArray[60];

void main()
{
int iTerm = 0;
int iLength;
int iCuts;
int iCut;
int iLoop1;
int iLoop2;
int iSum;
int iTotal;
int iPlaceHolder;

while(iTerm != 1) {
scanf("\n%d", &iLength);
if(iLength == 0)
iTerm = 1;
else {
scanf("\n%d", &iCuts);
scanf("\n%d", &iCut);
iCutList[0] [0] = 0;
iCutList[0] [1] = iCut;
iWorkingArray[0] = iCut;
for(iLoop1 = 1; iLoop1 < iCuts; iLoop1++){
scanf(" %d", &iCut);
iCutList[iLoop1] [0] = iCutList[iLoop1 - 1] [1];
iCutList[iLoop1] [1] = iCut;
iWorkingArray[iLoop1] = iCutList[iLoop1] [1] - iCutList[iLoop1] [0];
}
iWorkingArray[iLoop1] = iLength - iCutList[iLoop1 - 1] [1];
fflush(stdin);
iTotal = 0;
for(iLoop1 = iCuts; iLoop1 > 0; iLoop1--) {
//scanf all the values to find the smallest combination
iSum = 2000;
for(iLoop2 = 0; iLoop2 < iLoop1; iLoop2++) {
if(iWorkingArray[iLoop2] + iWorkingArray[iLoop2 + 1] <= iSum) {
iSum = iWorkingArray[iLoop2] + iWorkingArray[iLoop2 + 1];
iPlaceHolder = iLoop2;
}
}
//smallest found, now add to total, and combine pieces
iTotal = iTotal + iSum;
iWorkingArray[iPlaceHolder] = iSum;
for(iLoop2 = iPlaceHolder + 1; iLoop2 < iLoop1; iLoop2++) {
iWorkingArray[iLoop2] = iWorkingArray[iLoop2 + 1];
}
iWorkingArray[iLoop2] = 0;
}
printf("The minimum cutting is %d.\n", iTotal);
}
}
}
[/cpp]


thanks,
chris

ColdAndUgly
New poster
Posts: 2
Joined: Fri Nov 07, 2003 8:18 am

Post by ColdAndUgly » Fri Nov 07, 2003 8:26 am

I followed the method above to code this program, and i got a WA. Another thread contains some sample input, and a lot of my input didn't match. If anyone can take a look at it, i would appreciate it.

http://online-judge.uva.es/board/viewto ... ight=10003

thanks,
chris

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

Post by Algoritmo » Sat Nov 08, 2003 11:21 am

ColdAndUgly wrote:I got the same output as bnbolo did.

Here is my code, if someone could make a suggestion, i would appreciate it.
[cpp]
...
[/cpp]
thanks,
chris
In first place, I would like to sujest some changes in your code (and maybe in your way of coding). They make the code easyer to understand and find possible mistakes.

1:
The array iCutList[60][2] represents the cost and the length of 60 possible sticks, right? So it should be separated in Cost[60] and Length[60], as you will never use a variable in the second array dimension (example: iCutList[30][n]). If you prefer, you can make a struct (Stick[n].Cost and Stick[n].Length).

2:
I dont think you need fflush(stdin) and you don't need the "\n" or space in scanf format string unless you are using "%c" or gets() function.

3:
Instead of using an enormous else block, you could use:

Code: Select all

while (1) {
   if (iLength == 0) break;
   block....
}
Or even better:

Code: Select all

while (scanf("\n%d", &iLength)==1 && iLength) {
   block....
}
4:
Reading the code, I discovered you simply dont make use of the iCutList array in processing part. You use the iWorkingArray array instead. So iCutList is not beeing usefull there.

Well, I did not entirelly understand your code, but I see the array iWorkingArray get's smaller at each node of DP. This is not what I did. Node N calculates length and accumulated price for sticks that join N-1 final parts.... So a stick of N parts can result from:
stick with N-1 parts + Stick with 1 parts
stick with N-2 parts + Stick with 2 parts
stick with N-3 parts + Stick with 3 parts
...
So in my case, at each stage of DP more sticks are calculated and no stick is forgoten...

Hope I have helped.

Post Reply

Return to “Volume 100 (10000-10099)”