Блог пользователя bigintegers

Partitioning an array into equal sums
Автор bigintegers, история, 7 лет назад, По-английски

I was wondering if anyone knows how to solve the following question. I have tried on-and-off for about a week now, but I cannot figure it out:

Given an array A of N (1 <= N <= 100,000) positive integers, is it possible to remove exactly two elements in the array in order to form a partition of the array into three contiguous subarrays with equal sums?

For example, if A = [1, 3, 4, 2, 2, 2, 1, 1, 2], you can remove the "4" and the second-to-last "2" in order to get the following array: A = [1, 3, REMOVED, 2, 2, REMOVED, 1, 1, 2].

This works because 1 + 3 = 2 + 2 = 1 + 1 + 2 = 4.

But in some cases it might not be possible. For instance, if A = [1, 1, 1, 1, 1, 1], it's impossible,

Something important to keep note of is that don't need to determine which elements to remove but rather whether or not it is possible (so just yes/no is enough).

I have been struggling for a really long time with this problem. It is a variant of the "partition an array into 3 parts with equal sums" problem since you're forced to drop two elements in the array here.

I have tried thinking of DP solutions with no luck. Does anyone know how I can solve this? I think prefix sums might be useful here.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +5 Проголосовать: не нравится

Let i and j be the indexes of the elements that we are gonna remove.

Well, if we fix i than we know how much we want the other 2 sums to be. Let's look for the first position j so that sum[1...i-1] <= sum[i+1...j-1]. We can do that easily by binary search. If sum[1...i-1] != sum[i+1...j-1] then we can't get a partition if we remove the ith element, else we need to look at sum[j+1...n] to see if it is equal to the other 2 sums. If it is then we've found a valid partition.

Of course, so we can access the sums in O(1) we are gonna use prefix sums.

If the elements of the array are non-negative than there's some more case work to do, but in this case if they are >0, I think this solution is right.

→ Ответить
  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 8  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, thank you a lot for your help. This makes sense to me in theory, and you are correct that all of the integers are positive (so there shouldn't be any special cases). However, I am having a lot of trouble actually implementing this as practice. I was wondering whether you would be able to take a look at my code, and help me. I have added comments so that you understand what I am trying to do. In particular, I am having a lot of trouble setting up the binary search part, and the portions after it.

    I would really appreciate any help.

    int main() {
	vector<int> A = {1, 3, 4, 2, 2, 2, 1, 1, 2};

	vector<int> prefix;
	prefix.push_back(A[0]);
        
	FOR(i, 1, A.size()) {
		prefix.push_back(prefix[i - 1] + A[i]);
	}

	/* Let i, j be the indexes of the element we are going to remove. */
	FOR(i, 1, A.size() - 3) {
		int sum_of_subarray_one = prefix[i - 1];

		/* Now we want to find the first position j so that
		 * sum[1...i-1] <= sum[i+1...j-1] with binary search. */
	}

	return 0;
}
    → Ответить
    • »
      »
      »
      7 лет назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Hey, thank you for posting an interesting question.

      So instead of finding a j such that sum[1...i-1] <= sum[i+1...j-1] i directly wrote binary search to return j such that sum[0...i-1] == sum[i+1...j] if there exists one or else return -1.(my indexing starts from 0)

      here sum_one is the sum of the first subarray and diff is the sum upto the first element we removed. So if we remove element at index i then sum_one = sum[i-1] and diff = sum[i].

      int binary_search(int l, int r, int sum_one, int diff){  
	if(l==r){
		if( sum[l] - diff == sum_one){
			return l;
		}
		return -1;
	}

	int middle = (l+r)/2;

	if( (sum[middle] - diff) == sum_one ){
		return middle;
	}

	else if( (sum[middle] - diff) < sum_one ){
		return binary_search(middle+1, r, sum_one, diff);
	}
		
	return binary_search(l, middle, sum_one, diff);
}
      → Ответить