Algorithm for two piles of equal heights by removing boxes from above or below

Question

Suppose you have two piles, each of which consists of N boxes of different heights. You want to remove the boxes to get two piles of the same height (if possible). You cannot remove a box that is not at the top or bottom of the heap! You can see, for example, that if we remove the red squares below, we get two towers of equal height:

Another way to state this problem: two arrays of positive numbers are given, are there two consecutive subsequences (one in each array) whose sums are equal?

This problem is similar to this one in which we have an array A size N and the target t , and we want to find a sequential subsequence of A whose sum is t (equivalently, we have one bunch of boxes and we want to remove the boxes above and below, to get a bunch of heights t ), This problem can be solved in O(N) . On the other hand, the above problem has a trivial solution O(N^2) (see Answers below), but is there also an algorithm O(N^2) ( O(N log N) )?

Addendum: Field sizes are positive integers. It is assumed that they are all different (otherwise the problem can be solved trivially in O(N) ). If we denote by H total size of two piles, there is an O(H log H) algorithm (see Answers below). Thus, the problem becomes more interesting for H than N (an effective solution for H = N^2 would be a good start;)

Answer 1

Find all the amounts in O(n^2) and add them to the hash table:

 for l in [0, n) cur_sum = 0 for r in [l, n) cur_sum += a[r] hash_table.add(cur_sum) 

After that, we need to do the same for the second array and check if at least one sum occurs in the hash table.

This is much better than the naive O(n^3) solution.

You can also solve this problem in O(H log H) time, where H is the sum of the heights of the boxes if all the heights are integers, but this is only useful if the total height is limited.

The solution O(H log H) as follows:

We can quickly find all subarahms. Let’s see what subarahma S . This is the difference between the two prefix sums P[r] - P[l] = S If we add H to both sides of the equation, we get P[r] + (H - P[l]) = H + S Therefore, we need to check whether there are two elements in the array P[i] and H - P[i] , respectively, which add up to the given value. Let not just check their existence, but also count the number of such pairs. No, it looks exactly like multiplying two polynomials. The coefficients of the first polynomial are the number of occurrences of a particular sum of the prefix ( C[i] = count(j: P[j] == i) ). The second polynomial, in fact, is one and the same inverse. We can multiply these two polynomials by the time O(H log H) using the fast Fourier transform (since both of them have degree H ). After that, we just need to verify that the H + i coefficient for the product is non-zero.

As soon as we find out all the sums for the first and second arrays, we need to check whether they have at least one thing in common.

Answer 2

It is like an algorithm to find the length of the longest palindrome in a string. The palindrome algorithm examines the beginning and end of the string to determine if the palindrome exists, if not, the first character of the string is removed from the string, so the rest of the string is compared with the result of removing the last character of the string.

In this case, you are looking for a box that occurs due to the removal of the top and bottom of the heap. If the heap does not lead to a box of equal size in another heap, then remove the top of the heap and compare the result by taking the bottom of the heap. A recursive pseudo code might look like this:

 global pile2 global HashTableForPile2 # each value is a box in Pile2 def FindBoxInPile(pile, top, bottom): if (top == ReachedBottomInPile or bottom == ReachedTopInPile): Stop processing and return False ## base case else: # find the box created from the top to the bottom for i in range(bottom, top) sumPile1 += pile[i] # Determine if an identical box is inside both piles. # If so, return True; otherwise, recurse. # (assuming HashTableForPile2 was calculated earlier) if (sumPile1 == HashTableForPile2[sumPile1]): return True # take top AND bottom off pile if (FindBoxInPile(pile1, top-1, bottom+1) == True): return True # A box is inside both piles # take top OR bottom off pile and compare result elif (FindBoxInPile(pile1, top-1, bottom) == True or FindBoxInPile(pile1, top, bottom+1) == True) return True # A box is inside both piles, return True 

The dynamic programming solution will work in O (N) time.