Given $N$ integers on a circle, how to choose them in pairs to obtain minimum sum?

Question

(Added by YCor 2019 July 7): it has been mentioned in the comments that this is part of a contest "Circular merging, July Challenge 2019 Division 1", where an equivalent question (just more clearly phrased) is asked here.

$N$ integers $A_1,A_2,A_3....A_N$ are arranged on a circle such that $A_i$ is adjacent to $A_{i+1}$. Also $A_N$ is adjacent to $A_1$. We can choose two adjacent integers (say $A_j$, $A_{j+1}$) and keep integer with value $A_j+A_{j+1}$ in between them on the circle. Then we can remove $A_j$, $A_{j+1}$ from the circle. We can keep doing this until one integer is left on circle i.e. total $N-1$ times. We need to minimise the sum of numbers that we added on the circle.

Example: $20,10,3$ (as sequence) are arranged on the circle. Then first we can choose $10,3$. Now the sequence becomes $20,13$. Then we choose $20,13$ and final sequence becomes $33$. Hence the sum of numbers that we added on circle is $13 + 33 = 46$. This is the minimum sum possible. What will be the general procedure to solve this problem ?

Answer 1

A very simple heuristic would be to

• represent they circle as a directed, connected cycle graph $G(V,E)$ with vertices $V\ =\ \lbrace v_i\ |\ 1\le i\le n\rbrace$ and directed edges $E=\lbrace e_{ij}=(v_i,v_{i+1})\ |\ 1\le i \lt n\rbrace \cup\lbrace (v_n,v_1)\rbrace$
• map each vertex $v_i$ to $A_i$
• while $E\ne\emptyset$
  • determine edge $e_{i,j}^*$ that minimizes the sum $A_i^*+A_j^* $ of adjacent-vertex weights
  • record $A_i^*+A_j^* $
  • assuming $(v_j^*,v_k)\in E$
    • $A_i^* := A_i^*+A_j^*$,
    • $E = E\cup (v_i^*,v_k)$,
  • $V=V\setminus v_j^*$

That algorithm amounts to finding the pair of adjacent numbers with minimal weight sum,
replace one of the numbers by that sum and remove the other from the circle.

The time complexity is $O(n^2)$, which surely isn't optimal; utilizing priority queues will certainly bring it down to $O(n\log(n))$

I like the question, because it poses different challenges like e.g. a linear programming formulation or to determine the most appropriate graph theoretic algorithm.

running the algorithm with the sequence provided by the PO in a comment yields $9,\ 4,\ (2+3),\ 2,\ 9\ \mapsto\ 9,\ 4,\ (5+2),\ 9\ \mapsto\ 9,\ (4+7),\ 9\ \mapsto\ (9+9),\ 11\ \mapsto\ (18+11)$, resp.
$9,\ 4,\ 2,\ (3+2),\ 9\ \mapsto\ 9,\ (4+2),\ 5,\ 9\ \mapsto\ 9,\ (6+5),\ 9\ \mapsto\ (9+9),\ 11\ \mapsto\ (18+11)$
the numbers generated by additon are $5,7,11,18,29$, resp. $5,6,11,18,29$, demonstrating that the heuristic fails to generate the optimal sequence of additions; please keep in mind that the numbers are arranged on a circle, which is why the $(9+9)$ sums are "legal".

Edit 2019-07-07:

An improvement on the above heuristic is possible, if one asks the right questions; if one encodes the order of additions via braces, as is customary in programming languages, two basic questions come up:

• how does nesting depth affect the sum of intermediate sums?
• how does the order of numeric values affect the result if the nesting pattern of the braces is the same?

these questions can be investigated by checking simple illustrative examples, albeit that doesn't qualify as a proof of correctness.

for investigating the first question, we consider an arrangemnt of eight ones around the circle and compare the linear nesting:
$(((((((1+1)+1)+1)+1)+1)+1)+1)$ which generates as the sequence of intermediate results of additions
$2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8$, which sums up to $35$
with the "binary tree" nesting: $(((1+1)+(1+1))+((1+1)+(1+1)))$
which generates the sequence (level by level from leaf "node" to root "node") of intermediate results $2,\ 2,\ 2,\ 2,\ 4,\ 4,\ 8$, which sums up to $24$

The conclusion is that summation with low nesting depth is preferable to high nesting depth.

for investigating the second question, we compare the "linear" addition of an arithmetic sequence in ascending and in descending order: $(((((((1+2)+3)+4)+5)+6)+7)+8)$
generates $3,\ 6,\ 10,\ 15,\ 21,\ 28,\ 36$, which sums up to $119$ $(((((((8+7)+6)+5)+4)+3)+2)+1)$
generates $15,\ 21,\ 26,\ 30,\ 33,\ 35,\ 36$, which sums up to $196$

The conclusion is that small values should be added before large ones

An improved $O(n^2)$ heuristic based on the observations:

• in every iteration determine a minimum weight maximal matching and combine the pairs of values via addition that are adjacent to the same matching edge; that halves the number of values in each iteration, resulting in $O(n)$ iterations.
• the minimum weight maximal matching of a cycle graph can be determineded in $O(n)$ time, which amounts to a total of $O(n)\cdot O(n) = O(n^2)$ time complexity$

applying the algorithm on the example sequence $9,\ 4,\ 2,\ 3,\ 2,\ 9$: the two maximal matchings are
$\lbrace(9,4),\ (2,3),\ (2,9)\rbrace$, generating sum $13+5+11=29$ and
$\lbrace(4,3),\ (3,2),\ (9,9)\rbrace$, generating sum $7+5+18=30$

in the next iteration the number of nodes is odd and we thus have three maximal matchings in $7,\ 5,\ 18$ the one with minimum weight is
$\lbrace(7,5)\rbrace$, yielding $(7+5)+18\ =\ 12+30\ =\ 52$
for the other two matchings we have:
$\lbrace(5,18)\rbrace$ yields $(5+18)+7\ =\ 23+30\ =\ 53$
$\lbrace(18,7)\rbrace$ yields $(18+7)+5\ =\ 25+30\ =\ 55$
which gives a strong indication of the correctness of the improved heuristic.

It remains to show that values of the $2k+1$ maximal matchings in case of a cycle graph with an odd number of vertices can be calculated in $O(2k+1)$ time:
suppose the value of a maximal matching is known and that $u$ is the vertex not adjacent to any of the matching's edges. If vertex $v$ is immediate neighbor to $u$ and $w$ on the circle, then the value of the matching $M_w$ with $w$ not adjacent to a matching edge can be calculated in $O(1)$ from the value of $M_u$ by adding $\left(|(u,v)|\ -\ |(v,w)|\right)$

Answer 2

So there is an easy polynomial time algorithm for the problem. In particular by considering all possible final moves there is an easy reduction to $n$ points on a line that gives at most an $O(n^2)$ blowup to considering the problem on a line. For the problem on the line simply perform DP on all line segments and calculating a larger line segments is done simply by considering the final move. This algorithm is at most $O(n^5)$.

Answer 3

Here is a partial description of a cubic time algorithm in quadratic space. The idea is to determine optimal values for cost(Ij,k) which is the cost incurred by amalgamating the members from position j increasing (say clockwise around the circle) to position m. Since the sum of entries of this subset is useful, we will keep track of that as well.

We initialize by setting cost(j,j) to zero and sum(j,j) to A[j] as j goes from 1 to N. We assume code to handle indices so that when we add k to an index j, it behaves as usual except that if j+k is greater than N, we convert that to index value (j+k - N).

We are going to start k at 1 and compute cost (j,j+k ) and sum(j,j+k). As k gets larger than 1, it makes sense to find an optimal index m to use to aid in computing the cost, but we will not keep track of that information for this implementation. Now to the loop body, executed once for each k and each j:

m=1
sum(j,j+k)=sum(j,j+m-1) + sum(j+m,j+k)
T=cost(j,j+m-1)+cost(j+m,j+k)
#tmove = m
For m=2 to k step 1 do
   V= cost(j,j+m-1)+cost(j+m,j+k)
   If (V < T)
       T=V
       # tmove=m
cost(j,k)=T + sum(j,k)
#move(j,k)=tmove

This loop body takes constant space and time at most N inner loop iterations. Since the cost of an interval incorporates the sum of the interval, this computes a minimal cost by finding a series of optimal divisions for each smaller interval. Once k has reached N-1, one can do a comparison of all final costs to find the optimum.

Gerhard "Not Quite The Dynamic Programmer" Paseman, 2019.07.27.