24
$\begingroup$

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference between those integers; i.e., if the removed integers are $b$ and $c$, you put $|b - c|$ into the set again. You keep applying the operation until you are left with only a single number. So after $n - 1$ steps the game will terminate; you need to find out what is maximum value of the single number left in the end.

I am interested in seeing any polynomial time algorithm for the problem. Currently I don't have any idea about how to solve this problem in less than $\mathcal{O}(n !)$.

If you feel that there does not any polynomial time algorithm, could you please establish in which complexity class it lies? Is it NP complete?

Summarizing the main arguments:

  1. You can never get more than maximum of $a_i$'s.
  2. It seems like the number of different terminal values are at most $2^{n - 2}$.
  3. Not every expression is valid. An expression corresponds to a combination of + and - signs assigned to integers in the array.
  4. Keeping the difference $\geq$ 0 is the main source of difficulty.
  5. If we assume that all the expressions are valid, then this problem can be converted to a NP complete problem: the SUBSET-SUM problem. But as not all the expressions are valid, this can give us better ideas/algorithms.
  6. Bill Bradley has proved the problem of finding the minimum is NP-hard and he has also shown the construction for point 2; the problem of finding the number of different terminal positions was raised by Johan Wästlund.
  7. Brendan McKay's comment extends the argument for finding the maximum is also NP hard. Hence currently we have managed to prove that the problem is NP hard.
$\endgroup$
  • $\begingroup$ Looks more like a (discrete) optimization problem than a number theory problem… $\endgroup$ – Dirk Mar 19 '14 at 10:21
  • $\begingroup$ ^Dirk, On your suggestion I have changed the title to Optimization problem. $\endgroup$ – Praveen Dhinwa Mar 19 '14 at 10:23
  • 3
    $\begingroup$ Some experimentation suggests that the number of different terminal values is at most $2^{n-2}$. Is there an easy way to see this? Plainly it's at most $2^n$ since the terminal value is a linear combination with coefficients $\pm1$ of the initial numbers. $\endgroup$ – Johan Wästlund Mar 19 '14 at 16:44
  • $\begingroup$ @JohanWästlund: the requirement that each difference is positive kills off some possibilities. It seems like requiring each pair entries in the sequence to have the right sign gives a factor of 4, but this can't be the full explanation. $\endgroup$ – Alex R. Mar 19 '14 at 17:39
  • $\begingroup$ Divide by 2 since the end result is nonnegative. $\endgroup$ – The Masked Avenger Mar 19 '14 at 17:43
13
$\begingroup$

[Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster. I have edited this to include a complete answer to the original question.]

Let's refer to the operation of replacing two values $b,c$ in a multiset by the single value $|b-c|$ as a "contraction"; the original poster asks if it is possible to find an ordering of repeated contractions that maximizes the final value.

In this post, we begin by asking if we can find the order with the minimum possible value. Specifically, we try to determine whether the minimum value is zero or greater than zero. We will show that deciding this question is NP-complete. (We need to make it into a decision problem ("is it equal to zero?") rather than a minimization problem ("what's the smallest value?") to phrase it in terms of NP-completeness.) We then show how to convert this result into a statement about the maximum rather than minimum value.

Also, to Johan Wastlund's comment above, a slight modification of the construction gives an $O(2^{n-2})$ lower on the maximum number of distinct values that can be produced (which I'll outline at the bottom).


Determining if the minimum value is zero is clearly in NP-- we can simply (non-deterministically) guess the correct pattern of steps to produce zero. Showing that it is NP-complete takes a little more effort. We will show this by a reduction from the partition problem.

Take an instance of the partition problem with inputs $x_1,...,x_n$. We are trying to find a subset $S\subseteq \{1,...,n\}$ such that $\sum_{i\in S}x_i=\sum_{i\not\in S}x_i$.

Set $M_1=M_2=2\sum_i x_i$. Consider the multiset $\{M_1,M_2,x_1,...,x_n\}$. Let $f(x,y)=|x-y|$. Since we have taken $M_1$ to be so large, it follows that

$$f(\cdots(f(f(M_1,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_1-\sum_{j=1}^k x_{i_j}$$

and similarly for $M_2$.

Claim: if there exists a subset $S$ that partitions the integers $x_1,...,x_n$, then the minimum value attained by repeated contractions is zero.

Proof: Assume that such an $S$ exists. Then we can apply $f$ to $M_1$ and the elements of $S$ to get

$$M_1-\sum_{i\in S}x_i$$

and similarly with $M_2$ and the complement of $S$ to get

$$M_1-\sum_{i\not\in S}x_i$$

As our last step, we can subtract these and get zero. Since the output value is non-negative, then the minimum value is zero.

Claim: if an ordering of repeated contractions produces a final value of zero, then we can produce a partition from this ordering in polynomial time.

Proof: The computation of the final value attained by the repeated contraction corresponds to the evaluation of $f$ on a binary tree with the leaf nodes labeled by $x_1,...,x_n$. As pointed out in the comments above, we can "squash" this tree (in $O(n)$ time) and show that the output is equal to the sum $\sum_i \pm x_i$. If we let $S$ correspond to the $x_i$ with a positive index, we have constructed the desired partition.


We have shown above that determining whether the smallest value is zero is NP-complete. We now show that this implies the same complexity for the maximum.

Specifically, take $x_1,...,x_n$ and observe that the maximum possible value that can be achieved by repeated contraction is $\max_i x_i$. We now ask the question: is the maximum final value achieved by repeated contraction equal to $\max_i x_i$, or is it strictly smaller?

We will show that deciding this question is NP-complete. It is clearly in NP, since we can exhibit an ordering of contractions that achieves the maximum, if such an ordering exists.

To show that it is NP-complete, we will reduce from the problem of determining if there is an ordering of repeated contractions that equals zero.

Take the multiset $A=\{x_1,...,x_n\}$ and consider a new element $M=1+\sum_i x_i$. Let $B=A\cup \{M\}$. Note that $M$ is the unique maximum over $B$.

We first show that if the maximum final value for the repeated contraction of $B$ is $M$, then the minimum repeated contraction of $A$ is 0. If there exists a repeated contraction with final sum $M$, then any contraction that involves $M$ must be of the form $f(M,0)$ (otherwise the final sum would be strictly less than $M$) and vice versa. Suppose that we replace $M$ by 0; the same pattern of contractions will now produce a final value of 0. Therefore, we have produced a pattern of contractions on $A\cup \{0\}$ that gives a final value of zero.

In the other direction, we show that if the minimum final value for the repeated contraction of $A$ is 0, then the maximum value for $B$ is $M$. Suppose that the minimum repeated contraction of $A$ is 0. Then consider the identical pattern of contractions on $B$, which will leave us with $M$ and 0; the last contraction will produce $|M-0|=M$

Therefore, we can determine if the minimum final value of $A$ (which was arbitrary) is zero if an only if we can determine if the maximum final value of $B$ is $M$.

Therefore, the problem of determining if the maximum final value of a repeated contraction is equal to the maximum of the original set is NP-complete.


Johan Wastlund asked, as a function of $n$, what the maximum number of distinct values can be produced by applying $f$ in all possible combinations? He suggested it might be $2^{n-2}$. The construction above can be modified to show that there are at least this many possibilities.

Let $x_i=2^i$, for $i=1,...,n-2$. Let $M_1=2^{n-1}$ and let $M_2=2^n$. Since

$$M_z>\sum_{i=1}^{n-2}$$

(for $z=1,2$) then we still have $$f(\cdots(f(f(M_z,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_z-\sum_{j=1}^k x_{i_j}$$

Let $S$ be the subset of indices subtracted from $M_1$. Then we can construct the sum $$f(M_1-\sum_{i\in S}^k x_{i},M_2-\sum_{i\not\in S}^k x_{i})= M_2-M_1+(\sum_{i\in S}^k x_{i})-(\sum_{i\not\in S}^k x_{i})$$

This sum assumes a distinct value for each subset $S$ of $\{1,...,n-2\}$, so there are at least $2^{n-2}$ distinct values.

$\endgroup$
  • $\begingroup$ According to my point number 5, I was taking the combinations of +-x1 +- x2 +-x3 + .. +- xn, And I was saying that not all such expressions are valid, I thought that this might make problem somewhat simpler wrt complexity, but I was wrong. Your solutions is quite creative. Though it does not give much idea about how to convert this problem into equivalent partition problem so that we might apply pseudo polynomial time algorithm algorithm for that, then I think some approximation algorithms might be applied too. I will try to think over the second part myself. It seems interesting. $\endgroup$ – Praveen Dhinwa Mar 20 '14 at 16:59
  • 5
    $\begingroup$ Here is how to bootstrap off the theorem about the minimum to show that finding the maximum is also NP-hard. Take an arbitrary instance $P$ of the minimisation problem. Add one mores integer $a_{n+1}$ larger than all the others and call it a maximisation problem $P'$. Then the solution to $P'$ is $a_{n+1}$ iff the solution to $P$ is 0. This takes a few steps to prove but isn't difficult. $\endgroup$ – Brendan McKay Mar 20 '14 at 18:28
  • $\begingroup$ Oh, good point! I'll incorporate that in the answer above as soon as I have a chance (and credit you). $\endgroup$ – Bill Bradley Mar 21 '14 at 0:22
0
$\begingroup$

This was meant to be a comment, but I don't have enough reputation to post one. Hopefully it might have something to do with an answer too (but I do not remember what polynomial time means).

Assume for convenience $a_1 \leq a_2 \leq ... \leq a_{n-1} \leq a_n$. Let $m$ denote the max value of the number at the end of the game. Clearly $m$ is at most $a_n$. We could consider a dual problem: Save $a_n$ aside, and with the remaining numbers $a_1 \leq a_2 \leq ... \leq a_{n-1}$ play the same game, but this time trying to end up with the smallest possible number. Say that smallest number is $s$, so now we have $m = a_n - s$. An idea how to get $s$ would be as follows: It is of the form (abs value of) $a_{n-1}+e_{n-2}a_{n-2}+...+e_2 a_2 + e_1 a_1$ where $e_j=-1$ if the preceding partial sum is positive (so we aim to decrease it further), or $e_j=1$ if the preceding partial sum is negative (we aim to make it closer to $0$). Just an idea, I did not verify all details, meant a comment.

Let me illustrate (since the meaning of preceding partial sum may not be clear). Say we start with $[2,7,17,19,35]$. Save $35$ aside and with the remaining numbers form $19-17-7+2$ (the $+2$ at the end because $19-17-7=-5<0$, and we want to make the $-5$ to move closer to $0$). Thus $19-17-7+2 = -3$, or (taking abs value) $s=3$. Finally $m=35-3=32$. If I follow the steps of the game instead, it would look like this: $[2,7,17,19,35]$, $[2,7,2,35]$, $[2,5,35]$, $[3,35]$, $[32]$.

$\endgroup$
  • 2
    $\begingroup$ You can't assign signs arbitrarily. Also, the greedy algorithm can fail, such as when you are trying to make the smallest signed sum of $\lbrace 3,3,2,2,2\rbrace.$ $\endgroup$ – Douglas Zare Mar 20 '14 at 3:38
  • $\begingroup$ Assigning signs arbitrary might perhaps result in $O(2^n)$, better than $O(n!)$ ? Right, the greedy fails on $[3,3,2,2,2]$ returning $3-3+2-2+2=2$ when the optimal is $3+3-2-2-2=0$ (for smallest signed sum). Playing the dual game on $[3,3,2,2,2]$ (aiming at smallest number at the end): $[3,1,2,2]$, $[3,1,2]$, $[2,2]$, $[0]$, don't yet see an algorithm though. $\endgroup$ – Mirko Mar 20 '14 at 8:00
  • $\begingroup$ @DouglasZare, We have been discussing this question on CodeForces as well: codeforces.ru/blog/entry/11076. I have a comment [codeforces.ru/blog/entry/11076#comment-162163] there stating that being unable to assign signs arbitrarily is not a problem here because invalid assignments will NEVER give you the optimal answer. So if you found an optimal answer (to the minimization problem) then you can be sure that there will be a valid set of operations to achieve it. $\endgroup$ – Snowbear Mar 20 '14 at 19:27
  • $\begingroup$ @Snowbear: I see that you have asserted several times that the optimal arrangement of signs is always reachable by this difference method. However, I don't see you prove that. Note that it is false if you look for the maximum instead of the minimum nonnegative sum. $\endgroup$ – Douglas Zare Mar 20 '14 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.