0
$\begingroup$

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

$\endgroup$
24
  • 2
    $\begingroup$ Looks like dynamic programming problem in assignments. $$W(\{t_1,\dots,t_n\})=\min_{i\in\{1,\dots,n\}}w_{i,i+1} + W(\{t_1,\dots,t_n\}\backslash\{t_i,t_j\})$$ seems to be the general recursion where $W(\mathcal T)$ is minimum weight over all members of the set $\mathcal T$ and $w_{i,i+1}=A_i+A_{i+1}$ and you need to relabel the set entries. $\endgroup$
    – Turbo
    Jul 6, 2019 at 11:42
  • 1
    $\begingroup$ There may be cleverer way to optimize. Second solution is at step $i$ you pick all even or all odd indices or you pick one edge and go to step $i+1$ with minimum of the three possibilities in mind and that may simplify things. $\endgroup$
    – Turbo
    Jul 6, 2019 at 11:52
  • 1
    $\begingroup$ Where does this problem come from? Gerhard "Interview, Challenge, Contest, Or Homework?" Paseman, 2019.07.06. $\endgroup$ Jul 6, 2019 at 21:19
  • 2
    $\begingroup$ No rather go to the Meta post. $\endgroup$
    – YCor
    Jul 7, 2019 at 8:13
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is part of an ongoing contest. $\endgroup$ Jul 7, 2019 at 8:24

3 Answers 3

2
$\begingroup$

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)$

$\endgroup$
6
  • $\begingroup$ your algorithm does not works always .For example consider 9,4,2,3,2,9 . In this case if 2,3 is chosen in first iteration instead for 3,2 final answer is wrong . $\endgroup$
    – user142755
    Jul 6, 2019 at 11:32
  • 1
    $\begingroup$ @Shrijana I will replace "algorithm" by "heuristic" but leave the answer to illustrate, together with your counter example, that there isn't an easy answer. $\endgroup$ Jul 6, 2019 at 11:51
  • $\begingroup$ I do not know but i think it has answer .Do you have some idea how to solve the problem ?I am trying it from long time $\endgroup$
    – user142755
    Jul 6, 2019 at 11:57
  • 1
    $\begingroup$ There is a straightforward cubic algorithm with quadratic space that solves this problem. It may be possible to optimize on both space and time. However, I imagine this Is an exam question or contest problem. I hope that the original poster will mention where they found the problem. Gerhard "Isn't Feeling Dynamic At Present" Paseman, 2019.07.06. $\endgroup$ Jul 6, 2019 at 22:14
  • 2
    $\begingroup$ @ManfredWeis Can you remove the answer since it is from a contest . $\endgroup$
    – user142757
    Jul 7, 2019 at 8:07
0
$\begingroup$

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)$.

$\endgroup$
2
  • 1
    $\begingroup$ I believe there is a quartic time algorithm involving dynamic programming along the lines of your suggestion. I am concerned that the original poster is asking us to solve a competition problem for them. Gerhard "Is Waiting For The Uproar" Paseman, 2019.07.06. $\endgroup$ Jul 6, 2019 at 21:40
  • $\begingroup$ @GerhardPaseman Maybe from codechef.com/JULY19A/problems/CIRMERGE $\endgroup$
    – user142757
    Jul 7, 2019 at 7:46
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.