Page 1 of 1

3953 - Finding seats

Posted: Fri Mar 21, 2008 10:30 pm
by andmej
This problem ( ... 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.


Posted: Sat Mar 22, 2008 12:21 am
by 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.

Posted: Sun Mar 23, 2008 12:15 am
by 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.

Posted: Sun Mar 23, 2008 11:19 am
by 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;
....if (sum >= k) best = min(best, j-i+1);

Posted: Sun Mar 23, 2008 10:34 pm
by 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.