USACO 2016 January Contest Gold Division - Lights Out

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem asks us to simulate Bessie tracing the barn clockwise until she knows where she is. One way to think about this is to abstract away the polygon aspect of the problem and instead treat the angles and side lengths as a string. Now we need to help Bessie explore a string instead. Therefore we want try, for each starting position, extending the string until we get a unique substring.

Given that the constraints are small, we can use brute force to find the answer, with additional optimizations requiring suffix arrays or hashing.

Source code

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

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void solve() {
    ifstream fin("lightsout.in");
    int n;
    fin >> n;
    vector<vector<long long>> pts(n, vector<long long>(2));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            fin >> pts[i][j];
        }
    }
    fin.close();

    vector<long long> len(n);
    for (int i = 0; i < n; i++) {
        len[i] = llabs(pts[i][0] - pts[(i + 1) % n][0]) + llabs(pts[i][1] - pts[(i + 1) % n][1]);
    }

    vector<long long> cumfreqClock(n);
    cumfreqClock[n - 1] = len[n - 1];
    for (int i = n - 2; i > 0; i--) {
        cumfreqClock[i] = cumfreqClock[i + 1] + len[i];
    }

    vector<long long> cumfreqCounter(n);
    cumfreqCounter[1] = len[0];
    for (int i = 2; i < n; i++) {
        cumfreqCounter[i] = cumfreqCounter[i - 1] + len[i - 1];
    }

    vector<bool> angle(n);
    for (int i = 0; i < n; i++) {
        long long v1x = pts[i][0] - pts[(i - 1 + n) % n][0];
        long long v1y = pts[i][1] - pts[(i - 1 + n) % n][1];
        long long v2x = pts[i][0] - pts[(i + 1) % n][0];
        long long v2y = pts[i][1] - pts[(i + 1) % n][1];
        angle[i] = ((v1x * v2y - v1y * v2x) > 0);
    }

    long long res = 0;

    for (int spot = 1; spot < n; spot++) {
        if (cumfreqClock[spot] <= cumfreqCounter[spot])
            break;

        for (int fake = 1; fake < n; fake++) {
            if (fake == spot)
                continue;

            long long total = 0;
            int sI = spot, fI = fake;
            while (sI < n && fI < n) {
                if (angle[sI] != angle[fI])
                    break;

                total += len[sI];

                if (len[sI] != len[fI]) {
                    sI++;
                    fI++;
                    break;
                }

                sI++;
                fI++;
            }

            total += min(cumfreqClock[sI % n], cumfreqCounter[sI % n]);
            res = max(res, total - cumfreqCounter[spot]);
        }
    }

    ofstream fout("lightsout.out");
    fout << res << "\n";
    fout.close();
}

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

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}