1
$\begingroup$

Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:

  • Array: 7 5 9 1 3 9 6
  • Remove elements 9 and 1 to form array 7 5 3 9 6 that is divisible into two subarrays of equal sum {7,5,3} and {9,6}

Another example:

  • Array: 1 10 100
  • Whichever subset to remove in the second case, it is not possible to split the array into two parts with the same sum.

The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Please credit the original source of the problem. $\endgroup$ – Apass.Jack Dec 23 '18 at 2:53
  • $\begingroup$ The "continuous subsets" part is definitely helpful, since we have to consider only a polynomial (in terms of n) number of possibilities. $\endgroup$ – Gassa Dec 23 '18 at 16:16
  • $\begingroup$ Because there are O(n^2) possibles continuous subset (subsequence?) and we could find the "separating point" of the two equal sum subsets in O(n), we have a trivial O(n^3) solution. We could reduce the second part to O(lg n) with binary search and prefix sum. Not sure that a O(n^2 lg n) would be enough. Use 64-bit deal with the 1 billion upper bound. $\endgroup$ – Black Arrow Dec 25 '18 at 7:24
  • $\begingroup$ @BlackArrow, I posted an O(n^2) method $\endgroup$ – James Waldby - jwpat7 Jun 16 at 20:08
0
$\begingroup$

Let S denote the solution sum. Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method. Let A denote a given array of positive integers. Consider two kinds of partitions of A: (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence. We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind: Let S be a prefix sum of A. We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E. With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous. The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S>H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -> after last element of E
        for j in range(i+1, n-1): # j -> first element of E
            while Esum < Etarget and k<n-1:
                Esum += A[k]
                k += 1
            if Esum > Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum < Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
$\endgroup$

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.