CareerCup

We'd have to use dynamic programming to solve this one, since there are 2^(m) combinations of making even the first cut.

My algorithm is listed below in pseudocode:

Rod-cutting problem
Say we have range i...j in consideration.
C(i, j) = cost of cutting a rod between markings i and j
i, j = 0, 1, …, m+1
C(i, j) = MIN/k {C(i,k) + C(k, j) + (j - i)}, k = i+1, …,j-1
So, 
i → 0, 1, …,m+1
j → 0, 1, …,m+1
for each {i,j}
    k → i+1, …,j-1
Time complexity: O(m^3)
Space complexity: O(m^2)
Initialization: C(0, 0) = 0; C(i, i) = 1 for i = 1, …,m+1
Return: C(0, m+1)

I don't think there is a viable greedy solution here (pick the median cut point each time? the cut point closest to the middle?), so we'll have to use dynamic programming and memoization:

def cut_log(arr):
    """Returns minimum cost of cutting the log."""
    if len(arr) <= 2:
	return 0
    optimal_cut_point = argmin_i(cut_log(arr[:i+1]) + cut_log(arr[i:]))
    return max(arr) - min(arr) + cut_log(arr[:i+1]) + cut_log(arr[i:]))

Surprisingly there is no need for a program to calculate. This is more like a brain teasing question. The lease cost is n - max(di), which di represents the length of log between neighbor markings. Each time cut off the shorter log on the sides of log and the log with longest length remains in the hard at the end.

Follow this blog, cpluspluslearning-petert.blogspot.co.uk/2015/04/minimize-cost-of-cutting-log-google.html, to see the induction.

I will consider the most optimal case which is the marking are equally spaced.
So let L be the distance between two consecutive marking. N will then be equal to (M+1)*L.
The best way to cut in this case is to cut at the marking M/2, then M/4, etc...until we reach L
This cutting path costs Log(N), since there are M similar paths. The total cost will be M*Log(N).
This solution is better than cutting the markings in sequence starting with the 1st, then 2nd, then 3rd until Mth. Which results in a cost of (M+1)*N/2


However since we don't know if the markings are equally spaced, the best solution is to try to get as close as possible to the optimal one (explained above) by cutting at the marking which is the closest to the middle of the segment.

Is this a trick question? If I cut the log after each first word, the cost is just m (because we are not cutting the last remaining log containing n-m words).

Here's working code for this problem, along with a test case (input expected to be clean):

public class LogCuttingProblem {

    public static void main(String[] args) {
        System.out.println(calculateLogCuttingCost(100, new int[]{23, 34, 35, 68, 71, 88, 93}));
    }
    
    public static int calculateLogCuttingCost(int n, int[] markings) {
        int m = markings.length;
        int[] newMarkings = new int[m+2];
        newMarkings[0] = 0;
        newMarkings[m+1] = n;

        for(int j=1; j<m+1; j++) {
            newMarkings[j] = markings[j-1];
        }
        m = newMarkings.length;

        int[][] cmatrix = new int[m][m];
        cmatrix[0][0] = 0;

        cmatrix[0][1] = newMarkings[1];
        cmatrix[m-2][m-1] = n - newMarkings[m-2];

        for(int i=1; i<m-2; i++) {
            cmatrix[i][i+1] = newMarkings[i+1] - newMarkings[i]; // sub-logs with no markings
        }

        for(int windowSize=1; windowSize<m; windowSize++) {
            for(int i=0; i+windowSize<m; i++) {
                int j = i + windowSize;
                int minCost = Integer.MAX_VALUE;
                for(int k=i+1; k<j; k++) {
                    int currCost = cmatrix[i][k] + cmatrix[k][j] + newMarkings[j] - newMarkings[i];
                    if(currCost < minCost) minCost = currCost;
                }
                if(j != i+1)cmatrix[i][j] = minCost;
            }
        }
        return cmatrix[0][m-1];
    }
}

DUP of 13467664

This is my solution using modified binary search to find the closest possible cut that is in the middle of the log:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int find_price(vector<int> &cuts, int from, int to) {
	
	if (from >= to-1) return 0;
	
	int dist=cuts[to]-cuts[from], m=(from+to)/2, cut = -1;
	int target=cuts[from]+dist/2, curdiff = dist, tmpdiff = abs(target - cuts[m]);
	
	while (m>from && m<to && curdiff>tmpdiff) {
		
		curdiff = tmpdiff;
		cut = m;
		// Left or right?
		if (abs(target-cuts[m-1]) < abs(target-cuts[m+1])) {
			tmpdiff = abs(target-cuts[--m]);
		} else {
			tmpdiff = abs(target-cuts[++m]);
		}
	}
	
	if (cut > -1) {
		dist += find_price(cuts, from, cut),
		dist += find_price(cuts, cut, to);
	}
	return dist;
}

int main() {
	
	const int len = 80;
	vector<int> cuts = {30,41,67,5,10,15,20,25};
	
	cuts.push_back(0);
	cuts.push_back(len);
	sort(cuts.begin(), cuts.end());
	
	cout << find_price(cuts, 0, cuts.size()-1);
	
	return 0;
}

Just cut the log in half and then each successive piece in half until you make all the cuts.