3953 - Finding seats

[andmej]

This problem (http://acmicpc-live-archive.uva.es/nuev ... php?p=3932) is about finding the minimum area of a submatrix enclosing at least k 1's of a boolean matrix.

Does anybody know an efficient algorithm to compute this? I tried an O(n^4) algorithm but is too slow.

Thanks!

[mf]

Think about how to solve this problem in O(n) time: given an array of non-negative integers, find a contiguous subarray of minimum size, with sum of elements at least k.

Then you could solve the original problem in O(n^3) time, which should be fast enough.

[andmej]

Hello, mf. Thanks for your answer.

I've been thinking a lot about how to solve the problem you said. I've tried modifying Kadane's algorithm, but unsuccessfully. I think that once I have that part of the problem solved, the complete solution will be very similar to the solution of UVa's problem 108 - Maximum sum.

Can you give me any other advice about how to solve that part?
And excuse me if I'm being a problem for you... You can ignore this message if you feel uncomfortable.

Bye and thanks.

[mf]

You could brute-force index of the end of subarray. Let's call that j. For this j, you would be looking for the largest index i <= j, such that a+a[i+1]+...+a[j] >= k. This about what happens to i when you increment j by 1.

Answer: it stays the same or increases, which leads to the following O(n) algorithm (in C++):

int best = INT_MAX, i = 0, sum = 0;
for (int j = 0; j < n; j++) {
....sum += a[j];
....while (i < j && sum-a >= k) {
........sum -= a;
........i++;
....}
....if (sum >= k) best = min(best, j-i+1);
}

[andmej]

Thanks, mf.

I came up with this code (before reading your answer):

Code: Select all

  long long curr = 0;
  int i, j, minI, minJ;
  i = j = minI = 0;
  minJ = infinity;
  for (j=0; j<n; ++j){
    while (arr[i] == 0 && i++ < n);
    if (i == n) break;
    if (i > j){
      j = i;
    }
    curr += arr[j];
    while (curr >= k){
      if (j - i < minJ - minI){
	minJ = j; minI = i;
      }
      curr -= arr[i++];
    }
  }
  if (minJ == infinity) return infinity;
  return (minJ - minI + 1);
  }

I tried with it but got Time limit exceeded. Then I used your code and got accepted in 9.7 seconds with a time limit of 10!

Then I optimized mine a little and reduced it to 8.6 seconds (For example, I understood that I don't need to find the actual indexes of the range, just its length. I also used int instead of long long and inline for the function).

Thanks a lot! You have been of great help to me. You really made my neurons sweat.