Dynamic Programming - Minimize the Number of Canoes to Take Kids (Google Interview Question)

1. Problem Description
This is a Google interview question for software engineer from careercup. Here  is the original thread of this problem,

"If a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights."

2. Analysis
Some of contributors have already proposed a very good solution for this problem. It is to sort the weight - the lightest on one end and the heaviest on the other. Then try to pair the lightest and the heaviest. If the sum of two weights is not greater than the load of boat, then these two share one canoe. Otherwise the heaviest uses one canoe and move towards the middle. Then consider the lightest with the 2nd heaviest. Repeat this process until exhaust the list of weight.

I believe that this is the best solution so far and my solution proposed in this blog can't do better than this. However it will think about this problem in a different angle and try to use dynamic programming to solve this problem.

The following picture shows the mathematical formulation and constraints, and the sub-problem.

Constraints and Sub-problem

Corner cases:
    - N = 2, if the sum of two weights > 150, then f(2) = 2 otherwise f(2) = 1
    - N= 1, f(1) = 1

3. Implementation Discussion
Caching 
As usual I was trying to cache the result of the sub-problems. But unfortunately I fail to do so, because I can't find the good key for hash map that can represent the sub-problem uniquely. The sub-problem consists of a list o f weights with the list size from 1 to N-1. The candidate of the key would be either the list of indices of kids remaining in the sub-problem or the actual weights remaining in the sub-problem. Therefore the key would be a list/vector.This is really not a good solution in this case.

Sorting
Sorting should also benefit this solution. Because it will limit the number of sub-problems. As long as found the pair whose weight is greater than the load of the canoe, then can stop trying the rest of sub-problems because we already have a solution as good as the best of the rest. The following picture shows the sub-problem after sorting.

Sub-problem after Sorting

Data Structure and Algorithm - Find the longest strictly ascending sub-sequence of array (Google Interview Question)

1. Problem Description

This is a Google interview question from careercup. Here is the original thread,

"

You are given an unsorted sequence of integers 'a'. Find the longest subsequence 'b' such that elements of this subsequence are strictly increasing numbers. Elements in the subsequence 'b' must appear in the same relative order as in the sequence 'a'. You may assume that 'a' can fit to the memory.

Example:
input: a = [-1 2 100 100 101 3 4 5 -7]
output: b = [-1 2 3 4 5] 

".

2. Examples

I am to propose a tree structure to insert all the elements of array into the tree. Only the best/longest possible solutions will remain in the tree and one of the solutions will be found when reaching the end of array. 

Let's take a look how the two examples in the thread can be worked out by hand, then we can look into the tree structure. Apologize for my handwriting as the train was tumbling when I was working on them.

Example 1: [-1, 2, 100, 100, 101, 3, 4, 5, -7]

Solution of Example 1

Example 2: [10, 8, 6, 10, 2, 10 , 6, 14, 4, 9, 5, 13, 3, 11, 7, 15, 80, 9, 10, 10, 10, 10]

Solution of Example 2 - 1

Solution of Example 2 - 2

Solution of Example 2 - 3

Let's take a look at the more difficult one - Example 2. Here is some detailed explanation why each step is taken so.

Step a: - Insert 10 into an empty node

Step b: - Insert 8 into  left of 10, because 8 < 10.

            - Remove 10 from the right branch.

              Reason: any sub-sequence involving 10 can be replaced by 8. The left branch (8)
                            is always better or at least as good/long as the right branch (10).

Step c: - Insert 6 into the left of 8, because 6 < 8

            - Remove 8 from the right branch. The same reason as Step b

Step d: - Insert 10 as the child of 6, because 10 > 6 (build up the sub-sequence)

Step e: - Insert 2 into the left branch of 6, because 2 < 6

            - Keep both branches

              Reason: the left branch (2) has the potential to overtake the right branch (6), for

                            instance 3,  4, 5 following next in the array.

Step f: - Insert 10 as child of 2. because 10  > 2

            - Ignore inserting 10 as child of 6, because 6 already has a child 10

            - Remove the right branch 6, 10

              Reason: The same as Step b. In general if two branches has the same depth and

                            each element in the left branch is =< it counterpart at the same

                            level in the right branch, then the whole right branch can be removed.

                            In this case the parent node of two branches are 2 and 6, and their

                            parent node is the root, therefore 6 and 10 can be removed.

Step g: - Insert 6 as a child of 2 and stays at the left branch

               Reason: as child of 2 because 6 > 2 and stays at the left branch because 6 < 10

            - Remove 10 as Step b

Step h: - Insert 14 as a child of 6 because of 14 > 2 and 14 > 6

Step  i: - Insert 4 as a child as 2 and stay as  left branch. Same reason as Step g

            - Keep both branches as Step e

Step  j: - Insert 9 as child of 4 and 6. And stays the left branch as child of 6

            - Remove 14 as Step b

            - Then continue to remove 6 and 9 as Step f

Step k: - Insert 5 as child of 4 and stays in the left branch

            - Remove 9 as Step b

Step  l: - Insert 13 as child of 5 as 13 is the largest value

Step m: - Insert 3 as child of 2

             - Keep both branches as Step i

Step n: - Insert 11 as child of 3 and child of 5 and stay at the left branch of 5

            - Remove 13 as Step b

Step n':- Remove 11 as child of 3

              Reason: any following number > 11 conforms the sub-sequence, the right

                            branch is preferred because it is longer than left branch. (Currently

                            the depth of left and right are 3 and 4)

Step o: - Insert 7 as child of 3 and 5. Stays at the left branch of 5

            - Remove 11 as Step b

            - Remove 7 as child of 3 as Step n'

Step p: - Insert 15 as child of 3 and child of 7

            - Remove 15 as the child 3 as Step n'

Step q: - Insert 80 as child of 3 and child of 15

            - Remove 80 as child of 3 as Steop n'

Step r: - Insert 9 as child of 3 and child of 7. Stays at the left branch of 7

            - Remove 9 as child of 3 as Step n'

Step s: - Insert 10 as child of 3 and child of 9

            - Remove 15 and 80 as Step f

            - Remove 10 as child of 3 as Step n'

Step t: - Ignore 10 as duplicate of last value

Step u: - Ignore 10 as duplicate of last value

Step v: - Ignore 10 as duplicate of last value 

End:     - Reach the end of the array

             - One of solutions 2, 4, 5, 7, 9, 10

             - Length: 6

In Step n, Step o, Step p, Step q, Step r and Step s, the insertion to the left branch can be avoided actually in the first place then no bother deleting again. It will be discussed in the next section.

3. Analysis

Now let's take a close look at the tree structure and operations based on the examples in Section 2.

Branches 

    - 2, therefore this is a binary tree

Ordered

    - Yes

    - The children are greater than parents

    - The left branches is less than the right branches

Insertion

    - Give x, Find the node, y, that is one of following cases. And insert x as a child of y

        * y is a leaf node and less than x, for instance Step d and Step h

        * y is not a leaf node but its child is greater than x, for instance Step g and Step i

    - If y is the root, then insert as its left node, for instance Step b and Step c

Deletion after insertion of x

    -  If y is not a left node and x has a sibling z (must be greater than x)

        * Delete z, if z has no children, for instance Step k

    - x has a counterpart, z, at the same level at the right branch,

        * Delete x, if x > z and z has child/children, for instance Step p and Step q

    - Compare x with its sibling z

        * Delete the right branch up to the common ancestor of x and z, if x is less

           than z and x's ancestors are less than z's ancestor at each level,

           for instance Step f, Step g and Step j 

Exemption from insertion, 

Just examining Step n, Step o, Step p, Step q, Step r and Step s, probably do not need to insert x into the left branch. Do not insert x, if meet all the following conditions

    - y is a left node it has a sibling z

    - y < z

    - x < y

    - x < z

    - z's child is less than x as well

Solution

Guarantee find one of the longest sub-sequences but not all the solutions. In Example 2, Step s shows that 2, 4, 5, 7, 15, 80 is also a solution.

Complexity

Assume the size of the array is N and  the size of the longest sub-sequence as M,

    - Computation complexity: worst case N*M.

        * For instance given array is sorted and ascending, then  M=N, the tree will be like

           drop line. Each note has an element and each insertion will have to  compare

           all from the top to the bottom for insertion. (This worst case can be dropped

           to a linear solution by caching the leaf node)

    - Space complexity: worst case N

4. Solution and Implementation

I will discuss them in my next two blogs.

Data Structure and Algorithm - Find All Values as the Sum of Two Cubes in Two Different Ways Under N (Google Interview Question)

1. Problem Description

This is a Google interview question for software engineer inters from careercup. Here is the original thread, 

"

Write a function that would print all positive numbers smaller than n that can be expressed as the sum of two cubes in two different ways. Bonus: calculate the complexity of that function. 

For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.

"

2. Analysis

The simplest way is to use brutal force to iterate from 1 to N and check if this value is the sum of two cubes in two different combinations. Iterating each value takes a linear way. For each value i, it takes (i^1/3) to check if it is the sum of two cubes and has only two combinations. All together the computation complexity is more than O(N) and less than O(N^(4/3)).

The brutal force approach is worse than linear computation, therefore it is not good enough. As some of contributors points out, the correct way is to find out all the cubes under N and then see if value i can be sum of two and has only two combinations.

Rather than take the top-down approach. Here I would like to take bottom-up approach. After find out all the cubes under N, rather than check if value i can be sum of two and has only two combinations, I would compute all the possible sums of two cubes and their frequency. And those sums that are no more than N and the frequency equal to 2 are what I am after.

Given N and all cubes no greater than N as {X1, X2, ..., Xm}, where m = the integer no greater than (N^1/3). Then computer all possible sums, SUM = Xi + Xj, where i is not equal to j and both range from 1 to M. In maximum it would have M*(M-1)/2 possible SUMs. And those are no greater than N and appear exactly twice meet the requirement.

3. Solution

Pseudo-code

    - 1. Find out all cubes under N as {X1, X2, ..., Xm}

    - 2. Compute all possible SUM = Xi+Xj and increment its frequency

    - 3. Filter out SUM no greater than N and its frequency equal to 2

Counting the frequency associated with the SUM could use the hash map by SUM as the key and the frequency as the value. It takes constant time to search and linear time to filter out those meet the requirement.

Complexity

    - M equal to the integer no greater than N^(1/3)

    - In maximum has M*(M-1)/2 possible SUM

Therefore the computation complexity is O(N^(2/3)) and space complexity is O(N^(1/3)+N^(2/3)). Both are better than linear complexity.

Data Structure and Algorithm - Find the minimal intervals (Google Interview Question)`

1. Problem Description
This is a Google interview question for Interns from careercup. Here is the original description of this thread,

"

From a list of integer intervals, write a function to minimize the number of overlapping or consecutive ones. 

Test Input: [4, 8], [3, 5], [-1 2], [10, 12]
Test ouput: [-1, 8], [10,12]"

2. Analysis
As I introduced the sweep line algorithm in this blog entry, Data Structure and Algorithm - Sweep Line Algorithm, I believe that this problem can be solved with the similar idea.

Problem:
Given N intervals, [X1, Y1], [X2, Y2], ..., [Xn, Yn], where
    - Xi and Yi are all integers with i's range from 1 to N, and
    - the intervals are all inclusive on both ends.

Properties of the Sorted Lower and Upper Bounds:
According to the blog entry, Data Structure and Algorithm - Sweep Line Algorithm, we group the lower bounds and the upper bounds, {X1, X2, ..., Xn} and {Y1, Y2, ..., Yn}. Now we sort both lower bounds and upper bounds in the ascending order as,
    - Lower bounds: {L1, L2, ..., Ln}
    - Upper bounds: {U1, U2, ..., Un}
Because the lower and upper bounds are sorted, the following properties hold,
    - L1 <= L2 <= ... <= Ln
    - U1 <= U2 <= ... <= Un
    - Li <= Ui, for any given i between 1 to N
    - L1 <= L2 <= ... <= Li <= Ui, for any given i betwen 1 to N

Detect the Continuous/Overlap
Given the sorted lower and upper bounds,
    - Lower bounds: { L1, l2, ...,   Li, Li+1, ...., Ln}
    - Upper bounds: { U1, U2, ..., Ui, Ui+1, ..., Un]

Let's consider if Ui and Li+1 are overlapped, Based on the properties of the sorted lower and upper bounds, Ui is the largest value of {L1, U1, L2, U2, ..., Li, Ui} and Li+1 is the least value of { Li+1, Ui+1, Li+2, and Ui+2, ..., Ln, Un}. Therefore let's examine their relationship,
    - If Li+1 > 1 + Ui, then there is NO Continuous/Overlap here,
        * A interval with upper bound of Ui should stop here.
        * A new interval with the lower bound of Li+1 should start here
    - Otherwise there is either a CONTINUOUS or OVERLAP,
        * If Li+1 = 1 + Ui, then this is a CONTINUOUS  case.
        * Otherwise it is a OVERLAP case

3. Solution
Example:
Let's take a look at the example: [4, 8], [3, 5], [-1 2], [10, 12]
The sorted lower and upper bounds are,
    - Lower bounds: {-1, 3, 4, 10}
    - Upper bounds: { 2,  5, 8, 12}
Here is the algorithm runs
    - Take -1 as the lower bound of the first interval
    - Ui = 2, Li+1 = 3, where  i = 1. it is a CONTINUOUS case and continue
    - Ui = 5, Li+1 = 4, where i = 2, it is a OVERLAP case and continue
    - Ui = 8, Li+1 = 10, where i = 3, this is none of above cases
        * The first interval stops her as [-1, 8]
        * The second interval starts here with lower bound as 10
    - Reach the end, construct the second interval with the upper bound of Un, [10, 12]

Pseudo-code:
    - 1. Group lower bounds and upper bounds as {X1, ..., Xn} and {Y1, ..., Yn}
    - 2. Sort lower and upper bounds in ascending order as {L1, ..., Ln} and {U1, ..., Un}
    - 3. Take LowerBound = L1 as the lower bound of the first interval
    - 4. Compare Li+1 and Ui where i ranges from 1 to N-1
        * 4.1 if Li+1 > 1 + Ui, then 
                 construct the interval with Ui as the upper bound, [LowerBound, Ui]
                 update LowerBound = Li+1
                 go to Step 4.3
        * 4.2 if i = N - 1, then
                 construct the interval with Un as the upper bound, [LowerBound, Un]
                 Terminate the program
        * 4.3 Increment i by 1 and repeat Step 4         
This solution has O(NlogN) computation complexity and O(N) space complexity.

Data Structure and Algorithm: Minimal Swaps from Array A to B (Google Interview Question)

1. Problem Description
This is a Google interview question for software engineer from careercup. The following is the original thread,
"

You are given two arrays - A & B. The length of the arrays is the same - N. The values in the arrays are integers from 0 to N - 1 in random order and no number is repeated. You need to list a sequence of two-element swaps required to reorder the array A into the order of the array B. Additionally, at each step of the sequence you are allowed to swap two elements only if one of them is 0.

"

2. Analysis
Given the size of array as N and all unique elements (according to the problem description), all the total different combination of arrays are N! (factorial of N). A and B are just two combinations of N! Based on the fact all the combinations can be reached from a initial state (let's say in a ascending order) via swapping there must exist a minimal swaps that can make A and B the exactly same.

As we are talking about the minimal swaps of A to reach B, all the elements in A that are already in the correct locations should stay untouched and those are not should be swapped to reach B. Here comes the problem of how to reach B via minimal swaps.

The current solution proposed by some contributors
The solution proposed by some contributes are not the solution to reach B with the minimal swaps. Here is how it is done. Go through form the beginning of A and B and comparing two elements at the same location. If they are the same then carry on to the next location. If not the same, do the following, (suppose at this location x in A and y in B and x != y)
    - Swap x with 0 in A
    - Swap 0 with y in A
Now at this location A and B have the same value y. And in this way one difference causes two swaps. In general given M difference between A and B, the minimal swaps will be 2M.

The minimal swaps solution
Let's take another look at the example appearing in the thread.

int a[] = {1, 3, 2, 4, 0};
int b[] = { 4, 0, 3, 2, 1};

The solution proposed by Diapankar and a few others needs 10 swaps to reach B. According to the above analysis, 10 is exactly twice of the number of different element between A and B, 5.

Is this really need 10 swaps. Here is the solution that it should look like,
    - 1st swap:   1 and 0 => 0 3 2 4 1
    - 2nd swap: 4 and 0 => 4 3 2 0 1
    - 3rd swap:  2 and 0 => 4 3 0 2 1
    - 4th swap:  3 and 0 => 4 0 3 2 1
This takes exactly 4 swaps. If recall my other few blog entries, the difference between A and B can be called "edit distance". As all elements are unique and A and B are composed of the same elements. The actual question can be generalized as how many swaps to reduce the "edit distance" between A and B to 0. And what is the minimal swaps?

My solution as illustrated in the above example follows,
    - Find out the element 0 in A and its location i
    - Find out the element x in B at the same location i
    - Swap x with 0 in A
    - Repeat last 3 steps until there is no difference
The number of swaps of this solution is M - 1, where M is the "edit difference".

Here is a special case, When element 0 appears in the same location in A and B at the beginning or during the swap, two extra swap is need. In this case the minimal swap will be M+1.

int a[] = {1, 0, 2, 4, 3};
int b[] = { 4, 0, 3, 2, 1};

In the above case the edit distance M is equal to 4. But as the element 0 is not appearing in the editing difference list, therefore have to make it in the list. The solution is simple swap it out. For instance swap 0 with 3 (then M' = 5), Then we need M'-1 = 4 swaps to reach B. Therefore in total M'-1+1 = 5 swaps to from A to B. In this special case the minimal swaps is M'=M+1.

3. Solution
Here is the pseudo-code,
    - 1. Extract out the different elements into the edit distance list
    - 2. Check if 0 is appearing in edit distance list
        - 2.1 If not, swap 0 with one of element in the edit distance and add it into this list
    - 3. From the list look at the location of element "0".
    - 4. Find out the value x in B at the same location
    - 5. Swap 0 with x in the edit distance list (in A)
    - 6. Remove x from the edit distance list
    - 7. Repeat last 5 steps until exhaust the edit distance list
Bear in mind that Step 2.1 can only happen once. Either it happens at the very beginning when exacting the edit distance list, or it could happen after Step 5.
    -
Quite a few contributes pointed out how to do Step 3, 4 and 5 via using a N size array to save the index of each element in A, because the range of elements is from 0 to N-1 and without duplicate. In this special case it works perfectly fine. But in a more general case that keeps the uniqueness of elements but does not have the range constraint, a hash map should be used as the data structure with the element as the key and its index in A as the value.

In all here this solution has O(N) computation complexity and O(N) space complexity and guarantees minimal swaps as M-1/M+1.

Minimize the cost of cutting a log : Google Interview Question

1. Problem Description
This is a Google interview question from careercup. Here is the original post,

"You are given a log of wood of length `n’. There are `m’ markings on the log. The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. Given such a log, determine the least cost of cutting.
 "

2. Analysis
Before diving into the anslysis, let's be clear about my understanding on this problem.
    - The log can be cut on both sides
    - The cost is accumulated on log cut off each time (total m marking, m cuts)
    - The log still in the hand is not counted as cost

Assuming given a log of length n with m markings use D to represent the length between neighboring markings, d0, d1, ..., dm.
    - Size of D: m+1
    - Sigma(di) = n, where i from 0 to m

m = 1
One marking, one cutting to d0 and d1. In this case literally decide to cut from which side. Cut d0, then cost is d0 and cut d1 the cose is d1. Therefore the least cost of cutting this log is min(d0, d1).

m = 2
Two markings, two cuttings to d0, d1 and d2. Now we have 4 ways of cutting
    - Cut d0 off, then the cost is d0 + f(1) = d0 + min(d1, d2),
        where sud-problem f(1): the remaining log d1, d2
    - Cut d2 off, then the cost is d2 + f(1)  = d2 + min(d0, d1),
        where sud-problem f(1): the remaining log d0, d1
    - Cut d0+d1 off, then the cost is d0+d1+f(1) = d0+d1+min(d0,d1),
        where sud-problem f(1): the cut-off log d0, d1
    - Cut d1+d2 off, then the cost is d1+d2+f(1) = d1+d2+min(d1, d2),
        where sud-problem f(1): the cut-off log d1, d2

Let consider the value of d0, d1, and d2
If d0 is the largest, then the cost follows
    - d0 + min(d1, d2)
    - d2 + d1
    - d0 + d1 + d1
    - d1 + d2 + min(d1, d2)
Minimize the cost, therefore d2+d1 is th least cost.

If d1 is the largest, then the cost follows,
    - d0 + d2
    - d0 + d2
    - d0 + d1 + d0
    - d1 + d2 + d2
Minize the cost, therefore d0+d2 is the least cost.

If d2 is the largest, then the cost follows,
    - d0 + d1
    - d2 + min(d0, d1)
    - d0 + d1 + min(d0, d1)
    - d1 + d2 + d1
Minimize the cost, therefore d0+d1 is the least cost.

Now we can conclude that the least cost will be sum of the m least logs. It is also equals to the length of log minus the longest log, n - max(di).

m = 3
Three markings, three cuttings to d0, d1, d2, and d3. Now we have 24 ways of cutting
    - Cut d0 off, then the cost is d0+f(2),
        where the sub-problem f(2) with remaining log: d1, d2, d3
        cost = d0 + (d1+d2+d3 - max(d1, d2, d3))
                = n - max(d1, d2, d3)
    - Cut d0 and d1 off, then the cost is d0+d1+f(1)+f(1)
        where two sub-problems f(1), cut-off log d0, d1 and remaining log d2,d3
        cost = d0 + d1 + (d0+d1 - max(d0, d1)) + (d2+d3 - max(d2, d3))
                = n + d0 + d1 - max(d0, d1) - max(d2, d3)
    - Cut d0,d1 and d2 off, then the cost is d0+d1+d2+f(2)
        where the sub problem f(2) with cut-off log d0, d1, d2
        cost = d0 + d1 + d3 + (d0+d1+d2 - max(d0, d1, d2))
                = n + d0 + d1 + d2 - d3 - max(d0, d1, d2)
    - Cut d3 off, then the cost is d3 + f(2),
        where the sub-problem f(2) with remaining log: d0, d1, d2
        cost = d3 + (d0 + d1 + d2 - max(d0, d1, d2))
                = n - max(d0, d1, d2)
    - Cut d3, d2 off, then the cost is d3+d2+f(1)+f(1)
        where two sub-problems f(1), cut-off log d3, d2 and remaining log d1, d0
        cost = d3 + d2 + (d3+d2 - max(d3, d2)) + (d1+d0 - max(d1, d0))
                = n + d3 + d2 - max(d3, d2) - max(d1, d0)
    - Cut d3, d2, d1 off, then the cost is d3+d2+d1+f(2)
        where the sub-problem f(2) with cut-off log d3, d2, d1
        cost = d3 + d2 + d1 + (d3+d2+d1 - max(d3, d2, d1))
                = n + d3 + d2 + d1 - d0 - max(d3, d2, d1)

Again lets consider the largest value of di.
If d0 is the largest one, then the cost follows,
    - n - max(d1, d2, d3)
    - n + d0 + d1 - d0 - max(d2, d3) = n + d1 - max(d2, d3)
    - n + d0 + d1 + d2 - d3 - d0 = n + d1 + d2 - d3
    - n - d0
    - n + d3 + d2 - max(d3, d2) - d0
    - n + d3 + d2 + d1 - d0 - max(d3, d2, d1)
Minimize the cost, therefore n - d0 is the least cost

If d1 is the largest one, then the cost follows,
    - n - d1
    - n + d0 + d1 - d1 - max(d2, d3) = n + d0 - max(d2, d3)
    - n + d0 + d1 + d2 - d3 - d1 = n + d0 + d2 - d3
    - n - d1
    - n + d3 + d2 - max(d3, d2) - d1
    - n + d3 + d2 + d1 - d0 - d1 = n + d3 + d2 - d0
Minimize the cost, therefore n - d1 is the least cost

If d2 is the largest one, then the cost follows,
    - n - d2
    - n + d0 + d1 - max(d0, d1) - d2
    - n + d0 + d1 + d2 - d3 - d2 = n + d0 + d1 - d3
    - n - d2
    - n + d3 + d2 - d2 - max(d1, d0) = n + d3 - max(d1, d0)
    - n + d3 + d2 + d1 - d0 - d2 = n + d3 + d1 - d0
Minimize the cost, therefore n - d2 is the least cost

If d3 is the largest one, then the cost follows,
    - n - d3
    - n + d0 + d1 - max(d0, d1) - d3
    - n + d0 + d1 + d2 - d3 - max(d0, d1, d2)
    - n - max(d0, d1, d2)
    - n + d3 + d2 - d3 - max(d1, d0) = n + d2 - max(d1, d0)
    - n + d3 + d2 + d1 - d0 - d3 = n + d2 + d1 - d0
Minimize the cost, therefore n - d3 is the least cost

Now we can conclude that the least cost is the n - max(di) if m = 3.

m as any value
Use the induction theory this can be concluded that the least cost is equal to n - max(di).

3. How to Cut?
As the solution is rolled out, the longest log will be remained in the hand and the rest will be cut off and regarded as the cost. The solution of cutting is quite simple - always pick up the shorter log to cut on the both side for each cutting. In this way it will guarantee the longest log will remain on the hand as the last.

C++11 Features - Special Member Function Generation

This is a reading note of Item 17 of Scott Meyers' book - Effective Modern C++.

1. C++98
4 special functions
    - Default constructor/destructor/copy constructor/copy assignment operator
    - Generated when not declared
    - Can throw
    - Implicitly public, inline and non-virtual
    - desrtuctor can be virtual if its base class have virtual destructor

Copy constructor and copy assignment operator
    - Their generations are independent
    - Declare one does not have any effect on other's generation
    - Generated when not declared and needed

Rule of Three
    - Declaration of copy constructor, copy assignment and desctrctor
        * Either all of three
        * Or none of three

2. C++11
4 become 6 - move operations (move constructor and move assignment operator).
Move constructor and move assignment operator:
    - Generate them if not declared and needed
    - Member-wise move except the static members
    - Member-wise move the base class part
    - "Member-wise move" does not guarantee "move" the object, It is decided by std::move
        * If std::move decided it is a move, then move will take place
        * Otherwise move is replaced by copy
    - Their generations are not independent
        * Declare one prevents the generation of the other
        * Motivation behind: member-wise move is not good enough for one, neither is for the other
    - Their generations are prohibited by any declaration of copy operation
        * Motivation behind: if member-wise copy is not good enough, neither is member-wise move
    - Their declaration prohibits the generation of copy operation
        * Motivation behind: if member-wise move is not good enough, neither is member-wise copy

Rule of Three remains true in C++11
    - The declaration of destructor is bond with the copy operations
    - Therefore strong motivation: not generate move operation if user-declared destructor exists

Move operations are generated only if the following three conditions are true:
    - No copy operations declaration
    - No move operation declaration
    - No destructor declaration
This rule may extend to copy operations, because the automatic generation of copy operations for classes that have one of copy operation or destructor declared is deprecated by C++. So for now use "default", referring to C++11 features - Explicitly defaulted/deleted member functions, to explicitly declare copy operations generated by compiler. "default" supports copy operations, move operations, (virtual) destructor and default constructor.
As Scott Meyers points out in the example with generated move operations (no move, copy operations and destructor declared), declaring a destructor later can cause performance penalty. Because declaring a destructor suppresses the generation of move operation, and therefore move operation is replaced by copy operations.

Comparison between C++98 and C++11
    - Constructor and destructor exactly same, except destructor default as "noexcept" in C++11. Refer to C++11 Features - noexcept.
    - Copy constructor or copy assignment operator: same as C++98 - their generations are independent and do member-wise copy on non-static members. Except in C++11 their generations are prohibited by declaration of move operation and Rule of Three is enforced - its generation is deprecated if any user-defined copy operations or destructor declared.
    - Move operations: generated on when 3 conditions are met and do member-wise move on non-static members.
   
Bibliography:
[1] Scotts Meyer, "Effective Mordern C++", O'REILLY, 2014 First Release
[2] Bjarne Stroustrup, "The C++ Programming Language", C++11, 4th Edition
[3] C++ Reading Club @ IG Group