USACO Gold 2016 January - Lights Out

Official Analysis (C++)

Explanation

The official solution just doesn't use hashing.

We want to be able to pinpoint Bessie's location after traversing some edges and vertices, and then add the shortest distance to the exit from this location for each starting index. Then, we want to compare this total distance to the shortest distance to the end just from the starting vertex to find the answer. Finding the minimum distance to the end from each vertex can be done in $\mathcal{O}(N^2)$ time, as illustrated in the code. The question that remains is how to pinpoint Bessie's location after traversing some edges and vertices from each starting point.

As the official solution states, it is better to visualize the map as a string consisting of angles and edges rather than a polynomial. We can pinpoint Bessie's location if the current path is not repeated somewhere else in the map. If we were to frame this as a string-matching problem, we would want to find the shortest substring of the map such that it only appears once.

To handle angles, we can note that there are only two possible interior angles, $90^\circ$ and $270^\circ$.

We use hashing to find the shortest substring of the map. Distinguishing vertices from angles, we brute force through lengths in increasing order and use a one-base polynomial hash to check if the substring appears only once. If we find an appropriate substring, we find the total distance that we travelled before finding out where we were.

Implementation

Time Complexity: $\mathcal{O}(N^3)$

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

using ll = long long;

const ll P = 31;
const ll MOD = 1e9 + 7;
// maximum vertical/horizontal distance
const int MX = 2e5;