USACO 2020 US Open Contest Bronze Division - Social Distancing I

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

You should either place both cows in the largest interval of zeroes or place one cow in each of the two largest intervals.

Alternatively, we can binary search the answer and be careful about where to place them.

Binary search is more reliable usually so this is why I used it to solve the problem.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("socdist1.in");
    ofstream cout("socdist1.out");

    int n;
    cin >> n;
    vector<int> nxt(n);

    string s;
    cin >> s;

    for(int i = n-1; i >= 0; i--)
        if(s[i] == '1')
            nxt[i] = i;
        else
            if(i == n-1)
                nxt[i] = 10000000;
            else
                nxt[i] = nxt[i+1];

    int L = 0;
    int R = n;
    int ans = 0;
    while(L <= R)
    {
        int mid = (L + R) / 2;
        int poza = -1, pozb = -1;
        int lst = -10000000;
        bool valid = 1;
        for(int i = 0; i < n; i++)
        {
            if(s[i] == '1')
            {
                if(i - lst < mid)
                    valid = 0;
                lst = i;
            }
            else
            {
                if(nxt[i] - i >= mid && i - lst >= mid)
                {
                    if(poza == -1)
                        poza = i, lst = i;
                    else
                        if(pozb == -1)
                            pozb = i, lst = i;
                }
            }
        }

        if(pozb != -1 && valid)
            ans = mid, L = mid + 1;
        else
            R = mid - 1;
    }

    cout << ans;
    return 0;
}

with open("socdist1.in", "r") as fin:
    n = int(fin.readline().strip())
    s = fin.readline().strip()
nxt = [0] * n
for i in range(n-1, -1, -1):
    if s[i] == '1':
        nxt[i] = i
    else:
        if i == n-1:
            nxt[i] = 10000000
        else:
            nxt[i] = nxt[i+1]
L = 0
R = n
ans = 0
while L <= R:
    mid = (L + R) // 2
    poza = -1
    pozb = -1
    lst = -10000000
    valid = True
    for i in range(n):
        if s[i] == '1':
            if i - lst < mid:
                valid = False
            lst = i
        else:
            if nxt[i] - i >= mid and i - lst >= mid:
                if poza == -1:
                    poza = i
                    lst = i
                elif pozb == -1:
                    pozb = i
                    lst = i
    if pozb != -1 and valid:
        ans = mid
        L = mid + 1
    else:
        R = mid - 1
with open("socdist1.out", "w") as fout:
    fout.write(str(ans))