USACO 2021 December Contest Bronze Division - Lonely Photo

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

A idea which would run in \(O(n^2)\) would be to fix the beginning position of the substring and iterate over the ending position. As we iterate through the ending position, we keep track of how many G's and H's we have and just count how many strings we have that respect the pattern.

Now in order to optimize this to \(O(n)\), we need to think at what things are important to keep track of when it comes to deciding if a substring is a lonely photo.

Given that a lonely photo has both cows but only one cow of a type, it makes sense to keep track of the most recent two cows of each type and try doing some casework.

We know that the minimal length of a lonely photo is 3 so we need to see first when does a photo start becoming lonely and when does it end.

It is clear that the photo will no longer be lonely once we got at least two cows of both types and it all comes now down to knowing when we first get at least one cow of each type.

From there, all we have to do is to rely on simple casework to see how much we can add to the answer (from least recent occurence of the first cow to least recent occurence of the second cow).

In order to see the details, I recommend reading the codes, especially the Python one.

Source codes

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

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

int n;
string s;

int main() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    int prevG = -1, prevGG = -1;
    int prevH = -1, prevHH = -1;

    long long ans = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == 'G') {
            prevGG = prevG, prevG = i;
        }
        else {
            prevHH = prevH, prevH = i;
        } 
        if (i >= 2) {
            if (prevGG != -1 && prevHH != -1) {
                ans += min(i-2, min(prevG, prevH)) - min(prevGG, prevHH);
            }
            else {
                if(prevG != -1 && prevH != -1) {
                    ans += min(i-2, min(prevG, prevH)) + 1;
                }
            }
        }
    }

    cout << ans;
    return 0;
}

n = int(input())
s = input()

lastG = -1
secondlastG = -1
lastH = -1
secondlastH = -1

ans = 0

for i in range(n):
    if s[i] == 'G':
        secondlastG = lastG
        lastG = i
    else:
        secondlastH = lastH
        lastH = i
    if i >= 2 and lastG != -1 and lastH != -1:
        if lastG <= i-3 or lastH <= i-3:
            ans = ans + min(lastG, lastH) - min(secondlastG, secondlastH)
        else:
            ans = ans + (i-2) - min(secondlastG, secondlastH)

print(ans)