Python, advanced N^(3/2)

  • 0

    Let P_x = sum(A[:x]), the prefix sums. For every value j, we want P_i + P_{i+1} = P_j, and P_k + P_{k+1} = P_{-1} + P_{j+1}, so that the sum of ranges [0,i) equals (i, j); and (j, k) equals (k, N). Additionally, we want A[k] - A[i] = P[-1] - P[j+1] - P[j], so that the sum of ranges [0, j) minus A[i] equals (j, N) minus A[k]. These are necessary and sufficient conditions for the function returning true.

    In the latter condition, we have sets stored in Qinv. Specifically, in some sub-problem, B = Qinv[P[j]] and C = Qinv[P[j+1]+P[-1]] are sets, and we want to know if there is some C[k] - B[i] equal to the target of P[-1] - P[j+1] - P[j], a classic problem with complexity min(|B|, |C|). Our sub-problem only depends on (P[j], P[j+1]) which depends only on (P[j], A[j]), so there are at most N unique sub-problems; we'll remember our attempts so that we don't repeat the (failed) evaluation of a sub-problem.

    Consider an abstraction of Qinv: say X_i are disjoint sets with union [0, 1, ..., N-1]; and we choose any N pairs of subproblems. The N pairs chosen from all possible combos of the sqrt(N) largest |X_i|'s will have the highest sum; this sum_{i, j < sqrt(N)} min(|X_i|, |X_j|) = sum_{k < sqrt(N)} (2k + 1)X_k <= sum_k (sqrt(N) + 1)X_k <= N(sqrt(N) + 1) is bounded by O(N^(3/2)).

    def splitArray(self, A):
        if len(A) <= 3: return False
        P = [0]
        for x in A: P.append(P[-1] + x)
        Qinv = collections.defaultdict(set)
        for i, u in enumerate(A):
            Qinv[P[i] + P[i+1]].add(u)
        def subproblem(B, C, target):
            #Does some C[k] - B[i] == target?
            if len(B) < len(C):
                return any(b + target in C for b in B)
                return any(c - target in B for c in C)
        seen = set()
        for j in xrange(1, len(A) - 1):
            if (P[j], A[j]) in seen:
            seen.add((P[j], A[j]))
            B, C = Qinv[P[j]], Qinv[P[-1] + P[j+1]]
            target = P[-1] - P[j+1] - P[j]
            if subproblem(B, C, target):
                return True
        return False

    It works, and might be possible to work in general, but I suspect (not sure at all) that the test cases are incomplete. I feel there is a challenge case where it will fail (where there are nonempty subarrays that sum to zero) but I didn't investigate it thoroughly. I think empty arrays should be allowed though, and if they are, I think this approach is valid.

  • 0

    Should P_{-1} be P_{N}? By your definition, it's sum(A[:-1]), which is the sum of all numbers except the last number. Doesn't seem right. Also, are P_x and P[x] the same?

  • 0

    @StefanPochmann Err, that's not a literal definition, by P[-1] I mean P[N], which equals P[-1] in the code. Also I sometimes wrote P_x to denote P[x]. You should take the code to be the actual definition of P. Sorry the writing is not cleaned up,... I just had the idea and wrote the 'article' at the same time as the code while editing the code a bit, but the code works and should explain the idea very well.

  • 0

    Here is a brief explanation:

    Let P be as in the code:
    P = [0]
    for x in A: P.append(x + P[-1]).

    A valid triplet (i, j, k) is valid iff:
    P[i] + P[i+1] = P[j]
    P[k] + P[k+1] = P[N] + P[j+1]
    A[k] - A[i] = P[N] - P[j] - P[j+1]
    [and I guess i < j < k or something similar, but these are the relevant conditions we are using in the code]

    A valid triplet splits the array into 4 parts, call them p1, p2, p3, p4. For each possible j, let's find possible i's and k's so that p1==p2 and p3==p4. That's what B, C = Qinv[P[j]], Qinv[P[-1] + P[j+1]] does - B will be all the A[i]'s from valid i's, and C will be all the A[k]'s from valid k's. Then, we need to check whether p1+p2 == p3+p4. That's what "subproblem" does.

    Btw I'm still not sure whether this approach works in all cases. I don't feel that good about it actually... perhaps using A[i]'s directly is bad because we don't check the i < j < k stuff.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.