## 3953 - Finding seats

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### 3953 - Finding seats

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!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com