10003 - Cutting Sticks

[otavio]

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]

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]

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]

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.

[hank]

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]

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.

[hank]

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

[turuthok]

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-

[UFP2161]

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]

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]

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]

• 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]

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]

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]

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.