Line combination problem

Imagine you have a line of “n” length, where “n” is natural number. You can split this line in as many part as you want, but each part have to be natural number length. Design an algorithm that will split line to maximize value calculated from multiplication of each line length.

Example:

Line length 5:
Possible splits:
(1, 1, 1, 1, 1) => 1 * 1 * 1 * 1* 1 = 5,
(2, 1, 1, 1) => 2 * 1 * 1 * 1 = 2,
(3, 1, 1) => 3 * 1 * 1,
(4, 1) => 4 * 1,
5 => 5,
(2, 2, 1) => 2 * 2 * 1 = 4,
(2, 3) => 2 * 3 = 6
The Best split is (2, 3) because 2 * 3 is 6 and this is the highest value.

Dynamic programming solution

Top-down approach would be to get a line of length “n” and then try to split it into lines of length (1, n – 1), (2, n – 2) up to (ceil(n/2), n – ceil(n/2)). We do not need to search any further since going after n/2 will lead to check mirrored combination. For example We do not need to check (n-1, 1) since we already check (1, n-1), and we are interested in multiplication result, so we do not care about order.

Brute force approach

fun ropeDivisionBrutForce(n: Int): Long {
    var maxValue = n.toLong()
    for (i in 2..ceil(n / 2.0).toInt()) {
        val test = ropeDivisionBrutForce(i) *
                ropeDivisionBrutForce(n - i)
        maxValue = max(maxValue, test)
    }
    return maxValue
}

This code solves the issue, but it is not optimal. It takes to long to solve even a small size problem. Example of time execution depend on problem size:
– N = 45 – 10 seconds,
– N = 47 – 27 seconds
Time grows pretty fast, what is the time complexity for this problem?

Brute force time complexity

Every recursive call will run a loop from 2 to n/2, each of this loop iteration will call two branches twice, one for “i” and one for “n – i”.
This will construct a tree structure, each node will have different amount of child nodes, depend on current sub-problem “n”.

\[
T(n) = \sum_{i=2}^{n/2} [T(i) + T(n-i) + O(1)]
\]

If we look at the recursive definition we can see that the highest value for next recursion is T(n/2) so we can calculate the maximum height of a tree as :

\[
\frac{n}{2^{h}} = 1\\
n = 2^{h}\\
h = lg(n)
\]

Now we need to consider how many branches we have in each iteration:

\[
T(n) = \sum_{i=2}^{n/2} [T(i) + T(n-i) + O(1)]\\
T(n) = T(2) + T(n-2) + T(3) + T(n-3) + .. + T(n/2) + T(n/2) \\
T(n) = T(2) + T(3) +.. + T(n-2)
\]
This looks like we have almost “n” branches in each iteration.

Each iteration will create “n” branches, each branch will then create it own n₀, n₁, n₂, … branches, this n are values from 2 to n/2. This means that the biggest new recursive call will be n/2, about half of the previous iteration. We will assume that every branch create n/2 new branches this will simplify our formula for next branch count.
First iteration would have n branches, second would have n*(n/2), third iteration n*(n/2)*(n/4).
Branch amount depend on depth:
\[
branches = (\frac{n}{2})^i
\]
We know that depth would be lg(n) so we can sum all branches :
\[
(\frac{n}{2})^1 + (\frac{n}{2})^2 + .. + (\frac{n}{2})^{\lg(n)}
\]
We know that eventually big O will depend on the highest power of n^x because n^x will grow faster that 2^x

This brings us to the final assumption of O(n) for this algorithm

\[
O(n^{lg(n)})
\]

Memonization

When we look at our algorithm we immediately should see that each iteration will repeat a lot of sub-problems. When we calculate “n” we are creating branches for nodes from 2 to n/2. Next each node will split again into its own sub-problems. Node N/2 will iterate from 2 to n/4 etc. If we store solved values for T(N) we will highly reduce recursion.

fun MutableMap<Int, Long>.getOrElse(key: Int, r: (Int, MutableMap<Int, Long>) -> Long): Long =
    this[key] ?: r(key, this).also { this[key] = it }

fun ropeDivision(n: Int, memo: MutableMap<Int, Long> = mutableMapOf()): Long {
    var maxValue = n.toLong()
    for (i in 2..ceil(n / 2.0).toInt()) {
        val test = memo.getOrElse(i, ::ropeDivision) *
                memo.getOrElse(n - i, ::ropeDivision)
        maxValue = max(maxValue, test)
    }
    return maxValue
}

First we created an extension to MutableMap. This extension methods check if a value for the current key exists, if yes then it will return this value, if not it will run the method passed as second argument, store the result into a hash map and return this value to the caller.

RopeDivision method received a second argument to store the hashed result. New implementation use “getOrElse” extension to either receive value from cache or calculate it.

After memorization solving issue for N=110, took only 1ms

Tabulation

This time we will try to solve our problem bottom-up. We will start from solving few steps by hand

1	2	3	4	5	6	7	8	9	10
1	2	3	2 * 2	2*3	3*3	3*2*2	3*3*2	3*3*3	3*3*2*2

If we look at element 10 we can clearly see that it could be recreated using one of pair (2, 8) or (4, 6) both sum into 10 and both gave the same multiplication (3*3*2*2).

If we look at element 8 it could be created only from pairs (2, 6), pair (4,4) would create 2*2*2*2, and this value is smaller than 3*3*2.

This means that to get the best value for i-th element, we need to search previous created elements and try to find pair(a, b) that a+b = i and T(a) * T(b) is max value.
Find solution for i-th element require loop from 2 to n/2 and check pairs (a, i – a)

fun ropeDivisionTab(n: Int): Long {
    val array = arrayOfNulls<Long>(max(4, n + 1L).toInt())
            as Array<Long>
    array[1] = 1
    array[2] = 2
    array[3] = 3
    for (i in 4..n) {
        var currentMax = Long.MIN_VALUE
        for (j in 2..ceil(i / 2.0).toInt()) {
            currentMax = max(currentMax, array[j] * array[i - j])
        }
        array[i] = currentMax
    }
    return array[n]
}

Firs we allocate array for n + 1 element, since we will count from 1 to n, minimal size of array will be 4 to initialize first three array elements without worrying of overflow.
Next “i” loop iterate for rest of the table from 4 to n-th element. Each iteration try to find a pair of previous responses(“j”- loop) that will generate the best result for i-th element as described before. We store best result in array on “i”-th position.
When we finish creating every element of this array, all we need to do is return last element.

Mathematic solution

This problem can be simply solved when we look again on our tabulation result. Every element of array is combined from 3^a * 2^b, all we have to do is find a and b that will create the highest value.

To maximize 3^a * 2^b we need as big “a” as we can get and minimum “b”. We can get the biggest “a” from i = 3a + 2b, just by dropping “2b” part i = 3a and this lead to

a = floor(i / 3)
b = (i – 3 * a) / 2

When the number is divided by 3, we end up with three possible b values
b = 0 when i mod 3 return 0 or 1
b = 1 when i mod 3 return 2
B = 0 for mod 1 is invalid, we can check it on i = 10

a = floor(10/3) = 3
b = (10 – 3 * 3) / 2 = 1/2 = 0
this will return 3³*2⁰ = 27 and this is not the maximum value.

To fix it, all we need to do is whenever “i” modulo 3 return 1, we need to decrease a by 1, and then calculate b. This should always end up with 1 + 3 = 4 so in this case b is always 2

a = floor(10/3) = 3 because modulo return 1, “a” is decremented to 2
b = (10 – 3 * 2) / 2 = 4 / 2 = 2
The result is 3²*2² = 9 * 4 = 36

fun ropeDivisionMath(n: Int): Long {
    val div3 = n / 3
    val mod3 = n % 3
    val (count3, count2) = if (mod3 == 1 && div3 > 0) Pair(div3 - 1, 2)
    else Pair(div3, max(0, mod3 - 1L))
    return 3.0.pow(count3.toDouble()).toLong() *
            2.0.pow(count2.toDouble()).toLong()
}