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

**Moderator:** Board moderators

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!

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

http://www.dreamviews.com

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.

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

http://www.dreamviews.com

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

........sum -= a

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

....}

....if (sum >= k) best = min(best, j-i+1);

}

Thanks, mf.

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

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.

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);
}
```

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

http://www.dreamviews.com