USACO 2023 December Contest Bronze Division - Cowntact Tracing 2

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Let's find all sequences of consecutive ones and find for how many days we can keep the process going without any interferences.

Then, we can group the cows in ranges of 2 * first_ans - 1, where first_ans is the number of days found previously and we can do some math after.

For more details, I recommend checking the source codes below.

Source codes

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

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

struct dt
{
    int len, cntL, cntR;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<dt> ones;

    for(int i = 0; i < n; i++)
    {
        if(s[i] == '1' && (i == 0 || s[i-1] == '0'))
        {
            int len = 0;
            int lenS = 0;
            int lenD = 0;
            int x = i-1;
            while(x >= 0 && s[x] == '0')
                x--, lenS++;
            x = i;
            while(x < n && s[x] == '1')
                x++, len++;
            i = x-1;
            while(x < n && s[x] == '0')
                x++, lenD++;
            ones.push_back({len, lenS, lenD});
        }
    }

    if(ones.size() == 0)
    {
        cout << 0;
        return 0;
    }

    int minD = 1000000;
    for(int i = 0; i < (int) ones.size(); i++)
    {
        if(ones[i].cntL == 0 || ones[i].cntR == 0)
            minD = min(minD, ones[i].len-1);
        else
            minD = min(minD, (ones[i].len - 1) / 2);
    }
    minD++;

    int cnt = 0;
    for(int i = 0; i < (int) ones.size(); i++)
        cnt += max(1, (ones[i].len + minD * 2 - 2) / (minD * 2 -  1));

    cout << cnt << '\n';
    return 0;
}

n = int(input())
s = input().strip()
ones = []
i = 0
while i < n:
    if s[i] == '1' and (i == 0 or s[i-1] == '0'):
        length = 0
        lenS = 0
        lenD = 0
        x = i - 1
        while x >= 0 and s[x] == '0':
            lenS += 1
            x -= 1
        x = i
        while x < n and s[x] == '1':
            length += 1
            x += 1
        i = x - 1
        while x < n and s[x] == '0':
            lenD += 1
            x += 1
        ones.append((length, lenS, lenD))
    i += 1
if not ones:
    print(0)
else:
    minD = 1000000
    for length, lenS, lenD in ones:
        if lenS == 0 or lenD == 0:
            minD = min(minD, length - 1)
        else:
            minD = min(minD, (length - 1) // 2)
    minD += 1
    cnt = 0
    for length, lenS, lenD in ones:
        cnt += max(1, (length + minD * 2 - 2) // (minD * 2 - 1))
    print(cnt)