Page **1** of **1**

### 3953 - Finding seats

Posted: **Fri Mar 21, 2008 10:30 pm**

by **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!

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*;*

........i++;

....}

....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.