10003 - Cutting Sticks

[bazocc4]

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[1004][1004];
int data[60];
int result;
bool state[1004];
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] = 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]

It looks like you figured it out.

[unabl4]

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]

post your full code

[unabl4]

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; 
    }
    
    return NA; // Not found
}

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]

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[0][2] = 50
d[1][2] = 50
d[2][2] = 50
d[0][3] = 125
d[1][3] = 125
d[0][4] = 200
The minimum cutting is 200.
d[0][2] = 5
d[1][2] = 3
d[2][2] = 3
d[3][2] = 3
d[0][3] = 10
d[1][3] = 7
d[2][3] = 8
d[0][4] = 15
d[1][4] = 12
d[0][5] = 22
The minimum cutting is 22.

[unabl4]

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]

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.

[unabl4]

I've tried defining memoization array like

Code: Select all

stCutCost iCutsCosts[2601]; // 51 by 51 

but I get the same error

[brianfry713]

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.

[josman.perez]

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.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader stdin = new BufferedReader(new InputStreamReader(
			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];

		int len = readInt();
		while (len != 0) {

			// number of cuts
			int nCuts = readInt();

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

			for (int i = 0; i < nCuts; i++) {
				where[i + 1] = readInt();
			}
			where[0] = 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[0][nCuts]);
			printString(".");
			printNewLine();
			len = readInt();
		}

	}

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

	// Read next input-token as integer.
	static int readInt() throws Exception {
		return Integer.parseInt(readString());
	}

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

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

[jddantes]

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]

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.

[bachelorwhc]

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 = [0]
    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 = [0] * (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[0][len(marks) - 1]) + ".")
exit()

Can someone helps?