3953 - Finding seats

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

Moderator: Board moderators

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

3953 - Finding seats

Post by andmej » Fri Mar 21, 2008 10:30 pm

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:

Post by mf » Sat Mar 22, 2008 12:21 am

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.

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

Post by andmej » Sun Mar 23, 2008 12:15 am

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:

Post by mf » Sun Mar 23, 2008 11:19 am

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

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

Post by andmej » Sun Mar 23, 2008 10:34 pm

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

Post Reply

Return to “ACM ICPC Archive Board”