## 10003 - Cutting Sticks

Moderator: Board moderators

bazocc4
New poster
Posts: 4
Joined: Fri May 31, 2013 5:57 am

### Re: 10003 - Cutting Sticks

HELP ME pleaseee... i very keen that my code is true, but why WA ?

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
using namespace std;
int memcache;
int data;
int result;
bool state;
int rekursi(int lb , int rb)
{
if(memcache[ data[lb] ][ data[rb] ] > 0)
{
return memcache[ data[lb] ][ data[rb] ];
}

if(rb - lb == 1)
{
return 0;
}

int i;
int end = -1;
int temp;
for(i = lb+1 ; i < rb ; ++i)
{
temp = rekursi(lb , i) + rekursi(i , rb);
if(temp < end || end < 0)
{
end = temp;
}
}
return memcache[ data[lb] ][ data[rb] ] = end + data[rb] - data[lb];
}

int main()
{
int n,L,i,t,j,temp;
while(scanf("%d" , &L) != EOF)
{
if(L == 0)
{
break;
}

for(i=0 ; i <= L ; ++i )
{
state = false;
for(j=0 ; j <= L ; ++j)
{
memcache[j] = 0;
}
}

scanf("%d" , &n);
data = 0;
int counter = 1;
for(i=0 ; i < n ; ++i)
{
scanf("%d" , &temp);
if(state[temp] == false)
{
state[temp] = true;
data[counter++] = temp;
}
}
data[counter] = L;

int result;
if(n == 0)
{
result = L;
}
else
{
result = rekursi(0 , counter);
}

printf("The minimum cutting is %d.\n" , result);
}

return 0;
}

Thanks in advance brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

unabl4
New poster
Posts: 4
Joined: Sat Jun 22, 2013 3:02 pm

### Re: 10003 - Cutting Sticks

Hello everyone!

I've composed a program using algorithm from "algorithmist" (recursion. Although, I got this solution by myself, without peeking), but without memoization. For my submission I've received: Time Limit Exceeded, which could be kinda obvious (because some say - the test input is huge).

OK. So I've decided to memoize the stick interval cut costs.

For that one I've managed to create a separate structure:

Code: Select all

``````typedef struct {
int iFromIndex;
int iToIndex;
int iCost;
} stCutCost;
``````
So, basically it contains the cost for the intervals (which are denoted using their indexes rather than absolute values, for sake of simplicity). And then I've created an array that would contain the abovementioned structures.

Like this:

Code: Select all

``stCutCost *iCutsCosts; ``
.

I've used a pointer instead of a predefined array size, since the exact amount of intervals is variable. Because of that I was forced to use

Code: Select all

``int iCutsMem; ``
variable to hold the current amount of structures stored.

To store new interval (structure) I'm using following code:

Code: Select all

``````void vMemoize(int iFromIndex, int iToIndex, int iCost)
{
int y = iCutsMem;

iCutsMem++;

iCutsCosts = (stCutCost*)realloc(iCutsCosts, iCutsMem * sizeof(stCutCost));

iCutsCosts[y].iFromIndex = iFromIndex;
iCutsCosts[y].iToIndex = iToIndex;
iCutsCosts[y].iCost = iCost;
}
``````
- First I increment the amount of records, and then I "realloc" the space for my pointer array. And then I write down new entry.

So, before actually calculating any interval (except, zero-cut interval), I look through this array, and return the exact cut cost value if it is present. If not - I calculate the cost and store it.

My problem is - I receive a Runtime Error. While the program itself seems to be working correctly for every singe test case I could possibly think of.

Just in case, my working environment - Windows, Dev-C++.

Can anyone help me ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

Check input and AC output for thousands of problems on uDebug!

unabl4
New poster
Posts: 4
Joined: Sat Jun 22, 2013 3:02 pm

### Re: 10003 - Cutting Sticks

Code: Select all

``````#include "stdio.h"
#include "stdlib.h"

#define NA -1

typedef struct {
int iFromIndex;
int iToIndex;
int iCost;
} stCutCost;

int iNumberOfCuts; // The number of cuts to be done
int iLength;       // The overall length of the stick
int *iCuts;        // The array that holds the cut markers (lengths)
int iCutsMem;      // Memoized number of cuts

stCutCost *iCutsCosts;  // The memoization array

void vMemoize(int iFromIndex, int iToIndex, int iCost)
{
int y;

y = iCutsMem;
iCutsMem++;

if(y == 0)
{
iCutsCosts = (stCutCost*)malloc(sizeof(stCutCost));
}
else
{
iCutsCosts = (stCutCost*)realloc(iCutsCosts, iCutsMem * sizeof(stCutCost));
}

iCutsCosts[y].iFromIndex = iFromIndex;
iCutsCosts[y].iToIndex = iToIndex;
iCutsCosts[y].iCost = iCost;
}

int iCutLookup(int iFromIndex, int iToIndex)
{
int i;

for(i=0; i < iCutsMem; i++)
{
if(iCutsCosts[i].iFromIndex == iFromIndex && iCutsCosts[i].iToIndex == iToIndex) return iCutsCosts[i].iCost;
}

}

int iMinCut(int iFromIndex, int iToIndex)
{
if(iToIndex - iFromIndex == 1) return 0; // Nothing to cut anymore

int iCurrentCutCost;
int iCurrentMinCutCost = NA;  // Not available

int i;

iCurrentCutCost = iCutLookup(iFromIndex, iToIndex);

if(iCurrentCutCost != NA)
{
return iCurrentCutCost;
}
else
{
for(i = iFromIndex + 1; i < iToIndex; i++)
{
iCurrentCutCost = iMinCut(iFromIndex, i) + iMinCut(i, iToIndex) + (iCuts[iToIndex] - iCuts[iFromIndex]);

if((iCurrentCutCost < iCurrentMinCutCost) || (iCurrentMinCutCost == NA)) iCurrentMinCutCost = iCurrentCutCost;
}

vMemoize(iFromIndex, iToIndex, iCurrentMinCutCost);

return iCurrentMinCutCost;
}
}

int main(void)
{
while(1) {
scanf("%d", &iLength);  // Ask for the length

if(iLength == 0) break; // Stop input

scanf("%d", &iNumberOfCuts);   // Ask for the number of cuts
iCuts = (int*)malloc((iNumberOfCuts * sizeof(int)) + (2 * sizeof(int))); // Allocate space for cuts

/* Stick bounds */
*(iCuts) = 0;
*(iCuts + iNumberOfCuts + 1) = iLength;

int i;

for(i=1; i <= iNumberOfCuts; i++)
{
scanf("%d", iCuts + i);       // Input cuts
}

iCutsMem = 0;

printf("The minimum cutting is %d.\n", iMinCut(0, iNumberOfCuts + 1)); // C(0,N);
free(iCuts); // Clear the array after use
free(iCutsCosts);
}

return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

Instead of a top down recursive DP, try a bottom up DP. Mine gets AC in 0.155 sec. I have a 51 by 51 int array that stores the minimum cost for cutting up a stick based on position and length. For the sample input, my code fills the array in this order using for loops:

Code: Select all

``````d = 50
d = 50
d = 50
d = 125
d = 125
d = 200
The minimum cutting is 200.
d = 5
d = 3
d = 3
d = 3
d = 10
d = 7
d = 8
d = 15
d = 12
d = 22
The minimum cutting is 22.
``````
Check input and AC output for thousands of problems on uDebug!

unabl4
New poster
Posts: 4
Joined: Sat Jun 22, 2013 3:02 pm

### Re: 10003 - Cutting Sticks

Can you tell what is wrong with my code ? The Runtime error only occures if I manage to memoize the cut cost value (i.e calling vMemoize() function). I just simply don't get it, why should I rewrite the algorithm itself, if it works ? brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

I'm getting submission error for some reason. I rewrote my bottom up DP to a recursive top down DP. I still only use a 51 by 51 int array for memoization. Try rewriting your code without using dynamic memory allocation.
Check input and AC output for thousands of problems on uDebug!

unabl4
New poster
Posts: 4
Joined: Sat Jun 22, 2013 3:02 pm

### Re: 10003 - Cutting Sticks

I've tried defining memoization array like

Code: Select all

``stCutCost iCutsCosts; // 51 by 51 ``
but I get the same error brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

PM sent.

Both my top-down and my bottom-up DP get AC using a 51 by 51 two dimensional dp array. The bottom-up non-recursive code is faster.
Check input and AC output for thousands of problems on uDebug!

josman.perez
New poster
Posts: 1
Joined: Sun May 18, 2014 7:24 pm

### Re: 10003 - Cutting Sticks

I got runtime error and I don't know why, my program works and I've tried to figure out why but I have no clue... could someone please help me?

Code: Select all

``````import java.io.BufferedReader;
import java.util.StringTokenizer;

public class Main {

System.in));
static StringTokenizer st = new StringTokenizer("");

// Output
static StringBuilder output = new StringBuilder();

static final int NCUTS = 50;

public static void main(String[] args) throws Exception {

int[][] mCost = new int[NCUTS + 2][NCUTS + 2];

while (len != 0) {

// number of cuts

// where are we going to make the cuts
int[] where = new int[NCUTS + 2];

for (int i = 0; i < nCuts; i++) {
}
where = 0;
nCuts++;
where[nCuts] = len;

// Initialize the matrix of minimun cost
for (int i = 0; i <= NCUTS + 1; i++) {
for (int j = 0; j <= NCUTS + 1; j++) {
mCost[i][j] = Integer.MAX_VALUE;
}
}

for (int i = 0; i <= nCuts; i++) {
mCost[i][i] = 0;
mCost[i][i + 1] = 0;
mCost[i][i + 2] = where[i + 2] - where[i];
}

for (int i = 3; i <= nCuts; i++) {
for (int j = 0; j <= nCuts - i; j++) {
for (int k = j + 1; k <= j + i - 1; k++) {
if ((mCost[j][k] + mCost[k][j + i] + where[j + i] - where[j]) < mCost[j][j
+ i]) {
mCost[j][j + i] = mCost[j][k] + mCost[k][j + i]
+ where[j + i] - where[j];
}
}
}
}

// print
printString("The minimum cutting is ");
printInt(mCost[nCuts]);
printString(".");
printNewLine();
}

}

// Read next input-token as string.
static String readString() throws Exception {
while (!st.hasMoreTokens()) {
}
return st.nextToken();
}

// Read next input-token as integer.
static int readInt() throws Exception {
}

// Appends a string to current line of output
static void printString(String s) {
output.append(s);
}

// Appends an int to current line of output
static void printInt(int x) {
output.append(x);
}

// Writes the line to standard output
static void printNewLine() {
System.out.println(output.toString());
output = new StringBuilder();
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

Try input:

Code: Select all

``````100
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
0``````
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 10003 - Cutting Sticks

Got TLE:

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

#define INF (1<<30) - 1

typedef pair<int, int> segment;
typedef set<int> remCuts;

map<segment, int> mymap;

void printS(remCuts rc){
for(remCuts::iterator itr = rc.begin(); itr!=rc.end(); itr++){
printf("%d ", *itr);
}
}

int p(segment s, remCuts rc){

int lb = s.first;
int rb = s.second;
int cost = rb - lb;

//printf("Cutting segment (%d, %d) < ", lb, rb);
//  printS(rc);
// printf(">\n");

if(rc.empty()){
//printf("Reached end: Cost for cutting (%d, %d) is %d\n", lb, rb, 0);
return mymap[s] = 0;
}
if(mymap.count(s)){
//printf("Retrieving: Cost for cutting (%d, %d) is %d\n", lb, rb, mymap[s]);
return mymap[s];
}

int ans = INF;
for(remCuts::iterator itr = rc.begin(); itr!=rc.end(); itr++){
int cut = *itr;
if(cut > lb && cut < rb){
// printf("Cutting segment (%d, %d) at %d\n", lb, rb, cut);
remCuts nrc = rc;
nrc.erase(cut);
// printf("Cost: %d\n", cost);
// printf("newCost: %d\n", p(make_pair(lb, cut), nrc) + p(make_pair(cut, rb), nrc));
ans = min(ans, cost+p(make_pair(lb, cut), nrc) + p(make_pair(cut, rb), nrc));
}
}

if(ans == INF){
return mymap[s] = 0;
}

//printf("Cost for cutting (%d, %d) is %d\n", lb, rb, ans);
return mymap[s] = ans;

}

int main(){

while(1){
int l;
scanf("%d", &l);
if(!l) return 0;
mymap.clear();
remCuts rc;
segment s = make_pair(0, l);

int n;
scanf("%d", &n);
for(int x = 0; x<n; x++){
int cut;
scanf("%d", &cut);
rc.insert(cut);
}

int ans = INF;

int lb = 0; // Left bound
int rb = l; // Right bound
int cost = rb - lb;

for(remCuts::iterator itr = rc.begin(); itr!=rc.end(); ++itr){
int cut = *itr;

if(cut > lb && cut < rb){
// printf("Cutting segment (%d, %d) at %d\n", lb, rb, cut);
remCuts nrc = rc;
nrc.erase(cut);

ans = min(ans, cost+p(make_pair(lb, cut), nrc) + p(make_pair(cut, rb), nrc));
}
}

printf("The minimum cutting is %d\n", ans);

}

return 0;
}
``````
Is there something else that can be optimized in my algorithm, or does passing and using maps and sets really take that long? Also is it possible to know how long my code will run on the judge's input? So I know how off I am from the limit.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10003 - Cutting Sticks

You are missing the period at the end of the line.

You don't need to pass all of the cuts as a set and then ignore most of them. The cuts are fixed, use an array. Just try each cut point and then solve the left and right side and combine the costs.
Check input and AC output for thousands of problems on uDebug!

bachelorwhc
New poster
Posts: 1
Joined: Sat Feb 06, 2016 11:55 pm

### Re: 10003 - Cutting Sticks

Write in python, but get RE always.
I hava check test inputs and it works, but still don't know why got RE.

Code: Select all

``````import os
import math
while True:
wood_len = int(input().replace("\n", ""))
if wood_len == 0:
break
number_of_marks = int(input().replace("\n", ""))
marks = 
for mark in input().replace("\n", "").split(' '):
marks.append(int(mark))
marks.append(wood_len)
score = []
number_of_marks = len(marks)
for r in range(number_of_marks):
row =  * (number_of_marks)
score.append(row)
for start in range(2, number_of_marks):
for x in range(start, number_of_marks):
score[x - start][x] = math.inf
diff = marks[x] - marks[x - start]
prev = math.inf
for i in range(1, start):
prev = min([(score[x - start][x - start + i] + score[x - start + i][x]), prev])
score[x - start][x] = min([prev + diff, score[x - start][x]])
print("The minimum cutting is " + str(score[len(marks) - 1]) + ".")
exit()``````
Can someone helps?