Skip to main content
6 of 6
Rollback to Revision 3
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

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

(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 ?

user142755