CareerCup

Use dynamic programming.
1) Add two auxilary marks on each end of the log (totally n+2 marks)
2) min_cost[i][j]=minimum{min_cost[i][k] + min_cost[k][j] + length[i][j]}, where k=i+1 to j-1
3) min_cost[i][i+1]=0
4) min_cost[i][i+2]=length[i][i+2]
Find min_cost[0][n+1].

Giving you two extreme cases:
consider a log of length 8
1 strategy: cut smallest possible part, so we cut at mark 1,2,3,4,5,6,7 in that order
so cost would be 8,7,6,5,4,3,2

2 strategy: cut as evenly as possible, so we cut at mark 4,2,6,1,3,5,7
so cost would be 8,4,4,2,2,2,2

the difference would be more prominent with bigger log.

what is the meaning of "proportional to the length of the log"?
does it mean that if i cut at say second mark and there are total 10 marks, then cost is just 2.

i think there are two sub cases :
case 1:cost is linearly proportional to the the length of the log ,in which case,irrespective of the positions of cuts,we have to spent money equal to some constant times of total length of the rod.
case 2 :is when cost of cutting is not linearly proportional ,then we have to minimize sum of k terms ,each representing cost of a particular cut.keeping in mind that (a+b+c..)^n>a^n +b^n +...we should try to keep the size of the log as small as possible i.e k=n.

Go binary on the log... nlogn

first n/2
then part one... (n/2)/2...
part two... (n/2)/2...
11
5 6
3 2 3 3
2 1 1 1 1 2 1 2
1 1 1 1 1 1

cost: 6+3+3+2+1+2+2+1+1+1 => 22

Greedy algorithm, always divide the log as evenly as possible.

Is there any numbering of marks? Say, if n=10, and I make a cut at mark 2, it also means that I have made a cut at mark 8 from other end, making the overall sum constant.
By sum, I mean the cost of cutting log w.r.t one end and the other end.

Please let me know if I am overthinking this :P

assuming the n marks are equally spread across the entire log, Cut the log at n/2th mark, splitting it into two half, and keep repeating the process. the size of the log will be half its size with each cut, we'll make log(n) cuts cozt would be O(nlog(n))

Cutting evenly doesn't work. For example, look at 4,1,2,3. If you cut evenly, the cost is 2. But in fact you can do it with cost 1.9 (I leave this as an exercise :)

You need some sort of Huufman coding scheme where the order of the leaves are preserved.

Cutting evenly doesn't work. For example, look at 4,1,2,3. If you cut evenly, the cost is 2. But in fact you can do it with cost 1.9 (I leave this as an exercise :)

You need some sort of Huufman coding scheme where the order of the leaves are preserved.

I will give a try.
We have n distinct marks.
We can create all permutations of using these n marks.
Then we can find the cost of each permutation to find the one with the minimum.
We can do one optimization like cutting at 1 or cutting at n will amount the same. So we can cut down on the permutations this way.

I even don't understand the question

Why don't we put all the n marks at one end , so that the first cut will be proportional to the total length and rest all the n-1 cuts will be free of cost (negligible).
Please let me know your views (and did I understood the question correctly ?)

Why don't we put all the n marks at one end , so that the first cut will be proportional to the total length and rest all the n-1 cuts will be free of cost (negligible).
Please let me know your views (and did I understood the question correctly ?)

This is a variation of String Breaking problem in section 15.9 of "Algorithms by Cormen" text. It needs to be solved by D.P. If you can solve knapsack or similar problems, this is quite similar to that for solving it using D.P.

Can somebody check if this code is correct?

import java.util.ArrayList;


public class LogWoodCutting {
	
	public static void main(String args[])
	{
		ArrayList<Integer> LogSegmentLenght = new ArrayList<Integer>();
		/*
		 * e.g. 1
		LogSegmentLenght.add(4);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(2);
		LogSegmentLenght.add(3);
		*/
		
		//e.g. 2
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		LogSegmentLenght.add(1);
		
		System.out.println(LogWoodCutting.minimumPrice(LogSegmentLenght));
	}

	private static int minimumPrice(ArrayList<Integer> logSegmentLenght) {
		int n = logSegmentLenght.size();
		int[][] length = new int[n+1][n+1];
		int[][] minCost = new int[n+1][n+1];
		int[][] preCut = new int[n+1][n+1];
		int i,k;
		
		for(i=0;i<n;i++)
			length[i][i+1]=logSegmentLenght.get(i);
			
		for (k = 2; k <= n; k++)
			for (i = 0; i < n; i++) {
				if (i + k <= n)
					length[i][i + k] = length[i][i + k - 1] + length[i + k - 1][i + k];
			}
		
		
		for(i=0;i<n-1;i++)
			minCost[i][i+2]=length[i][i+2];
		

		for(i=0;i<n-1;i++)
			preCut[i][i+2]=i+1;
		
		
		for (k = 3; k <= n; k++)
			for (i = 0; i < n; i++) {
				if (i + k <= n)
					minCost[i][i + k] = findMin(i, i+k, minCost, length, preCut);

			}
		
		System.out.print("Cutting sequence:");
		printCut(0,n, preCut);
		System.out.println();
		
		return minCost[0][n];
	}

	private static void printCut(int i, int j, int[][] preCut) {
		if(preCut[i][j]==0) return;
		System.out.print(preCut[i][j] + " ");
		int cut = preCut[i][j];
		printCut(i,cut,preCut);
		printCut(cut,j,preCut);
		
	}

	private static int findMin(int i, int j, int[][] minCost, int[][] length, int[][] preCut) {
		int value = minCost[i][i+1]+minCost[i+1][j];
		preCut[i][j]=i+1;
		int k=2;
		while(i+k<j)
		{
			if((minCost[i][i+k]+minCost[i+k][j])<=value)
				{
				value = (minCost[i][i+k]+minCost[i+k][j]);
				preCut[i][j]=i+k;
				}
			k++;
		}
		return value + length[i][j];
	}

		
}

Think of this problem in terms of graph. lets say the "n" marks where we have to make a cut are "n" vertices and the cost of moving the ace from vertex V1 to V2 the length of log form V1 to V2.... now we have to cover all vertices while minimizing the cost...

thus this can be reduced to spanning tree problem and our goal is to find minimum spanning tree.... there are 2 algorithms for this... Prims and Kruskal.. they each have pros and cons... but any of them will solve the problem....

Hope this will work -
# include <stdio.h>

#define PRICE_PER_UNIT xx
#define MAX_SEGEMENT yy

int wood_segment[MAX_SEGMENT] = { 4,5,1,2,1,...};
typedef struct result_segment {
int left_seg;
int right_seg;
struct result_seg *next
}result_seg;

void free_ptr(result_seg *ptr)
{
if (ptr != NULL)
free_ptr(ptr->next);
free(ptr);
}

int cost_of(int first_seg_idx, int last_seg_idx)
{
int len = 0;
for(int i = first_idx, i <= last_seg_idx; i++)
len += wood_segment[i];
return (len * PRICE_PER_UNIT);
}

result_seg *calc_cost(int *total_cost, int first_seg_idx, int last_seg_idx)
{
int ct_cost, least_cost = 0, initial_cost;
result_seg *least_cost_seg, *left_cost_seg, *right_cost_seg;

initial_cost = *total_cost;
for(i = first_seg_idx; i < last_seg_idx; i++) {
*total_cost = initial_cost;
left_cost_seg = right_cost_seg = NULL;
if((ct_cost_seg = (result_seg) malloc(sizeof(result_seg))) == NULL){
printf("malloc failed \n");
exit(-1);
}
ct_cost_seg->left_seg = first_seg_idx+1; //(1,2) (1,3) (1,4) (1,5) - In case of 5 segments.
ct_cost_seg->right_seg = (last_seg_idx+1) - (last_seg_idx - i - 1);

*total_cost += cost_of(first_seg_idx, i);
*total_cost += cost_of(i+1, last_seg_idx);
if((left_seg - first_seg_idx) > 1) {
left_cost_seg = calc_cost(total_cost, first_seg_idx, i);
}
if((last_seg_idx - i) > 1) {
right_cost_seg = calc_cost(total_cost, i+1, last_seg_idx);
}
if(left_cost_seg == NULL && right_cost_seg == NULL){
return ct_cost_seg; // only two segments left.
}
if (left_cost_seg == NULL) {
ct_cost_seg->next = right_cost_seg;
} else {
ct_cost_seg->next = left_cost_seg;
if(right_cost_seg != NULL) {
for(result_seg *ct_seg = left_cost_seg; ct_seg->next != NULL; ct_seg = ct_seg->next);
ct_seg->next = right_cost_seg;
}
}
if(least_cost = 0 || least_cost > *total_cost) {
if(least_cost != 0)
free_ptr(least_cost_seg);
least_cost = *total_cost;
least_cost_seg = ct_cost_seg;
} else {
free_ptr(ct_cost_seg);
}
}
*total_cost = least_cost;
return ct_cost_seg;
}

main()
{
int least_cost = 0;
result_seg *least_cost_seg;

least_cost_seg = calc_cost(&least_cost, 0 , MAX_SEGMENT-1);
print("Minimal Cost = %d\n Minimal Cost Cuts are -", *least_cost);
for(; least_cost_seg != NULL; least_cost_seg = leg_cost_seg->next) {
printf("Left segments = %d Right segments %d\n", least_cost_sega>-left_seg, least_cost_seg->right_seg);
}
}

Sorry, what is the "goal"? Cutting at all the marks?

Otherwise, the minimum is 0, don't cut anything at all...

int CutWoodDP(vector<int>& w, map<pair<int, int>, int>& p, int start, int end, int length)
	{
		if (start >= end)
		{
			return 0;
		}

		if (p.find(pair<int, int>(start, end)) != p.end())
		{
			return p[pair<int, int>(start, end)];
		}

		int sumUpToi = 0;
		int minSum = numeric_limits<int>::max();

		for(int i=start; i<end; ++i)
		{
			sumUpToi += w[i];
			int sum = CutWoodDP(w, p, start, i, sumUpToi) + CutWoodDP(w, p, i+1, end, length - sumUpToi) + length;

			if (sum < minSum)
			{
				minSum = sum;
			}
		}

		p[pair<int, int>(start, end)] = minSum;

		return minSum;
	}

Cut at every half - 8 + (4+4) + (2 + 2 + 2 + 2) = 8log8

Recursion or dynamic programming. DP seems hard to work out.

I think,the cuts should happen where the 2 parts has the minimum difference in length.
log length is 10.marks at 2 ,4,6 ,8
4 and 6 cost 10
4- at 2 cost 4
6- (2,4) cost 6
(2,4) divide 4 cost 4 total cost -10+6+4+4=24

This is a variation of binary search. Cut the log in 2 halves each time and we would get the minimum cost.

can any1 help me in getting ref for google