Solution: Splitting the Pirate Loot

Solution

Let’s denote $v_1 + v_2 + ··· + v_i$ as sum$(i)$. Splitting the set of $n$ items evenly into three parts is possible only if their total value is divisible by three, i.e., sum$(n) = 3V$, where $V$ is an integer. Then, we need to partition $n$ numbers into three parts where the sum of numbers in each part is equal to $V$. Instead of partitioning all $n$ items, let’s try to solve a smaller problem of partitioning the first $i$ items into parts of value $s_1, s_2,$ and $sum(i) − s_1 − s_2$. We define $split(i,s_1,s_2) =$ true if such partition is possible (and false, otherwise) and note that the pirates can fairly split the loot only if $split(n,V,V)=$ true.

Stop and think:

Given the first five items

$$\boxed{3}\boxed{6}\boxed{4}\boxed{1}\boxed{9}$$

$split(5,4,13) =$ true.

Find all other values $split(5,s1,s2)$ equal to true.

Imagine that you have already constructed the binary two-dimensional array $split(i−1,s_1,s_2)$ for all possible values $0≤s_1 ≤V$ and $0 ≤ s_2 ≤ V$ . Can you use this array to construct the array $split(i,s_1,s_2)$?

Assume that $split(i,s_1,s_2) =$ true—that is, we can split the first $i$ numbers into three parts such that the sum of numbers in the first part is $s_1$ and the sum of numbers in the second part is $s_2$.

• The $i$-th number belongs to the first part. Then $v_i ≤ s_1$. By taking it out of the first part, we will partition the first $i − 1$ numbers into three parts such that the sum of the first two parts is $s_1 − v_i$ and $s_2$, that is, $split(i − 1, s_1 − v_i , s_2 ) =$ true.

• The $i$-th number belongs to the second part. Then $v_i ≤ s_1$. Similarly to the previous case, $v_i ≤s_2$ and $split(i−1,s_1,s_2−v_i)=$ true.

• The $i$-th item belongs to the third part. Then, $split(i−1,s_1,s_2)=$ true. This way, we compute the value of $split(i,s_1,s_2)$ by looking at $split(i−1,s_1−v_i,s_2)$, $split(i−1,s_1,s_2−v_i)$, and $split(i−1,s_1,s_2)$.

The base case for this recurrence relation is: $split(0,0,0) =$ true and $split(0,s_1,s_2)=$ false if $s_1+s_2 >0$.

---

 $Split(v_1,\ldots,v_n)$:
 if $v_1 +\ldots+v_n$ is not divisible by $3$:
 return false
 $V ←(v_1+\ldots+v_n)/3$
 $split ←$ three-dimensional array of size $(n + 1) × (V + 1) × (V + 1)$
 initialize all elements of $split$ to false
 $split[0][0][0] ←$ true
 for $i$ from $1$ to $n$:
 for $s_1$ from $0$ to $V$:
   for $s_2$ from $0$ to $V$:
    $split[i][s_1][s_2] ← split[i − 1][s_1][s_2]$
    if $s_1 ≥ v_i$:
     $split[i][s_1][s_2] ← split[i][s_1][s_2]$ OR $split[i −1][s_1 −v_i][s_2]$
    if $s_2 ≥ v_i$:
     $split[i][s_1][s_2] ← split[i][s_1][s_2]$ OR $split[i − 1][s_1][s_2 − v_i]$
 return $split[n][V ][V ]$

---

The running time is $O(nV^2)$.

Code