USACO 2023 US Open Contest Bronze Division - FEB

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Start with initial number of matches. Then, we have three main cases:

1. F..FFFFB or BFFFF..F -> step is 1, we can get it all or nothing (corner case when we have only F)
2. BFFFB - we can get up to (F+1) new matches and at least one if length is even
3. EFFFFB - we can get up to F new matches and at least one if length is even

Applying these cases and taking the optimal answer is going to be enough.

For a more detailed solution and casework review, I recommend checking this solution out.

Source codes

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string s;
    cin >> s;

    int cnt = 0;

    for(int i = 0; i < n; i++)
        if(i + 1 < n && s[i] == s[i+1] && s[i] != 'F')
            cnt++;

    int mini = cnt, maxi = cnt;
    int stp = 2;

    for(int i = 0; i < n; i++)
    {
        if(s[i] != 'F')
            continue;
        int len = 0;
        while(i + len < n && s[i + len] == 'F')
            len++;
        set<int> ch;
        if(i > 0)
            ch.insert(s[i-1]);
        if(i + len < n)
            ch.insert(s[i+len]);
        if(ch.size() <= 1)
        {
            if(i == 0 || i + len == n)
                maxi += (len - (ch.size() == 0)), stp = 1;
            else
                if(len % 2 == 1)
                    maxi += (len + 1);
                else
                    maxi += (len + 1), mini += 1;
        }
        else
        {
            maxi += len;
            if(len % 2 == 1)
                mini++;
        }
        i = i + len - 1;
    }

    vector<int> ans;
    for(int i = mini; i <= maxi; i += stp)
        ans.push_back(i);

    cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << '\n';
    return 0;
}

n = int(input())
s = input().strip()
cnt = 0
for i in range(n - 1):
    if s[i] == s[i + 1] and s[i] != 'F':
        cnt += 1
mini = cnt
maxi = cnt
stp = 2
i = 0
while i < n:
    if s[i] != 'F':
        i += 1
        continue
    length = 0
    while i + length < n and s[i + length] == 'F':
        length += 1
    ch = set()
    if i > 0:
        ch.add(s[i - 1])
    if i + length < n:
        ch.add(s[i + length])
    if len(ch) <= 1:
        if i == 0 or i + length == n:
            maxi += length - (1 if len(ch) == 0 else 0)
            stp = 1
        else:
            if length % 2 == 1:
                maxi += length + 1
            else:
                maxi += length + 1
                mini += 1
    else:
        maxi += length
        if length % 2 == 1:
            mini += 1
    i += length
ans = list(range(mini, maxi + 1, stp))
print(len(ans))
for x in ans:
    print(x)