USACO 2020 US Open Contest, Bronze Problem 1. Social Distancing I

USACO 2020 US Open Contest, Bronze Problem 1. Social Distancing I

A terrible new disease, COWVID-19, has begun to spread among cows worldwide. Farmer John is trying to take as many precautions as possible to protect his herd from infection.

Farmer John's barn is a long narrow building containing NN stalls in a row (2≤N≤1052≤N≤105). Some of these stalls are currently occupied by cows, and some are vacant. Having read about the importance of "social distancing", Farmer John wants to maximize DD, where DD is the distance between the closest two occupied stalls. For example, if stalls 3 and 8 are the closest that are occupied, then D=5D=5.

Two new cows recently joined Farmer John's herd and he needs to decide to which formerly-unoccupied stalls they should be assigned. Please determine how he can place his two new cows so that the resulting value of DD is still as large as possible. Farmer John cannot move any of his existing cows; he only wants to assign stalls to the new cows.

 

 

 

SAMPLE INPUT:

14
10001001000010

SAMPLE OUTPUT:

2

In this example, Farmer John could add cows to make the occupancy string look like 10x010010x0010, where x's indicate the new cows. In this case D=2D=2. It is impossible to add the new cows to achieve any higher value of DD.

 

Problem credits: Brian Dean

USACO 2020 US Open Contest, Bronze Problem 1. Social Distancing I 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Dhruv Rohatgi )

By scanning through the stalls, we can compute a list of gaps: blocks of contiguous empty stalls. Let l1,…,lkl1,…,lk be the lengths of these gaps. For example, consider the sample input:

 

10001001000010

Then in this example, the gap lengths are 33, 22, 44, and 11.

If we only place a single cow, it will either go at the center of the largest gap, or in the left-most stall, or in the right-most stall. If we have two cows, then we might consider the following algorithm: for each of the three cases for the first cow, place the first cow; then try the three different cases for where the second cow might go. In total there are 99 potentially optimal placements (actually less because some are impossible) and for each placement we can compute the length of the minimum distance between cows in that placement, by a linear scan.

However, this does not cover all cases. It's possible that both cows are placed in the same gap (the largest gap). In this case we want to place one of the cows approximately one-third of the way through the gap, and the other cow two-thirds through. The above algorithm will never try this placement, so we need to check it also.

We can prove that the resulting 1010-case algorithm is correct. If the cows are not placed in the same gap, then each cow will be either in the center of some gap, or at the left end or right end of the whole sequence (because the two cows don't "interact"). If either cow is at the left end or the right end, then the above algorithm covers that case. If both cows are in centers of gaps, then at least one of them will be at the center of the largest gap. This case is also covered.

See below for Brian Dean's O(N)O(N) time algorithm. Some of the cases are condensed (and some are omitted because they're impossible), but in spirit his algorithm is as we described above.

 

#include <iostream>
#include <fstream>
using namespace std;
 
// Returns size of largest gap between two 1s and also the index where it starts
int find_largest_interior_gap(string s, int &gap_start)
{
  int biggest_gap = 0, current_start = -1, N = s.length();
  for (int i=0; i<N; i++) 
    if (s[i] == '1') {
      if (current_start!=-1 && i-current_start > biggest_gap) {
	biggest_gap = i-current_start;
	gap_start = current_start;
      }
      current_start = i;
    }
  return biggest_gap;
}
 
// Returns size of smallest gap between two 1s
int find_smallest_interior_gap(string s)
{
  int smallest_gap = 1000000000, current_start = -1, N = s.length();
  for (int i=0; i<N; i++) 
    if (s[i] == '1') {
      if (current_start!=-1 && i-current_start < smallest_gap) smallest_gap = i-current_start;
      current_start = i;
    }
  return smallest_gap;
}
 
int try_cow_in_largest_gap(string s)
{
  int gap_start, largest_gap = find_largest_interior_gap(s, gap_start);
  if (largest_gap >= 2) {
    s[gap_start + largest_gap / 2] = '1';
    return find_smallest_interior_gap(s);
  } 
  return -1; // no gap!
}
 
int main(void)
{
  ifstream fin ("socdist1.in");
  int N;
  string s, temp_s;
  fin >> N >> s;
  ofstream fout ("socdist1.out");
  int answer = 0;
 
  // Possibility 1. put two cows in largest interior gap
  int gap_start, largest_gap = find_largest_interior_gap(s, gap_start);
  if (largest_gap >= 3) {
    temp_s = s;
    temp_s[gap_start + largest_gap / 3] = '1';
    temp_s[gap_start + largest_gap * 2 / 3] = '1';
    answer = max(answer, find_smallest_interior_gap(temp_s));
  }
 
  // Possibility 2. cows at both ends
  if (s[0] == '0' && s[N-1] == '0') {
    temp_s = s; temp_s[0] = temp_s[N-1] = '1';
    answer = max(answer, find_smallest_interior_gap(temp_s));        
  }
 
  // Possibility 3. cow at left + cow in largest interior gap
  if (s[0] == '0') {
    temp_s = s; temp_s[0] = '1';
    answer = max(answer, try_cow_in_largest_gap(temp_s));
  }
 
  // Possibility 4. cow at right + cow in largest interior gap
  if (s[N-1] == '0') {
    temp_s = s; temp_s[N-1] = '1';
    answer = max(answer, try_cow_in_largest_gap(temp_s));
  }
 
  // Possibility 5. cow at largest interior gap.  done twice.
  if (largest_gap >= 2) {
    temp_s = s; temp_s[gap_start + largest_gap / 2] = '1';
    answer = max(answer, try_cow_in_largest_gap(temp_s));
  }
 
  fout << answer << "\n";
  return 0;
}

[/hide]