USACO 2017 January Contest Silver Division - Hoof, Paper, Scissors

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that we can only change the sign once, we can use prefix sums for each type of move and fix the position of the change.

Source code

The source code in C++ can be seen below.

#include <fstream>
using namespace std;

int sp[3][100002];

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;

        sp[0][i] = sp[0][i - 1] + (c == 'H');
        sp[1][i] = sp[1][i - 1] + (c == 'P');
        sp[2][i] = sp[2][i - 1] + (c == 'S');
    }

    int ans = max(sp[0][n], max(sp[1][n], sp[2][n]));  // no changes
    for (int i = 1; i <= n; i++) {
        ans = max(ans, sp[0][i] + max(sp[1][n] - sp[1][i], sp[2][n] - sp[2][i]));
        ans = max(ans, sp[1][i] + max(sp[0][n] - sp[0][i], sp[2][n] - sp[2][i]));
        ans = max(ans, sp[2][i] + max(sp[1][n] - sp[1][i], sp[0][n] - sp[0][i]));
    }

    cout << ans;
    return 0;
}