USACO 2020 December Contest Bronze Division - Stuck in a Rut

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

You can solve the problem using a brute force approach where while you still have cows moving, you find all intersections, find the first one that happens and simulate moves based on this information.

I recommend reading the code below as it has a lot of comments.

Source codes

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

#include <iostream>
using namespace std;

const int MAX_N = 50;

int N, x[MAX_N], y[MAX_N], tstop[MAX_N];
char dir[MAX_N];

struct Intersection {
    int i, j, time_i, time_j, active;
};
Intersection I[MAX_N * MAX_N];

void find_all_intersections(void) {
    int current = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            if (dir[i] == dir[j]) {  // no intersection if same direction (or same cow)
                continue; 
            }

            // Possibly flip coordinates so that for simpllicity, we can
            // assume without loss of generality that cow i is moving north, and
            // cow j east
            int xi = x[i], yi = y[i], xj = x[j], yj = y[j];
            if (dir[i] == 'E') {
                swap(xi, yi);
                swap(xj, yj);
            }

            if (yi > yj) { // cow i already north of cow j?
                continue;             
            }
            if (xi < xj) { // cow i already west of cow j?
                continue;             
            }
            if (xi >= xj + yj - yi) { // cow i passes before cow j can cut her off
                continue;  
            }

            Intersection Inew = {i, j, yj - yi, xi - xj, 1};
            I[current] = Inew;
            current++;
        }
}

int main(void) {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> dir[i] >> x[i] >> y[i];

    find_all_intersections();

    // Repeatedly find earliest remaining intersection and process it
    while (1) {
        int earliest = -1;
        for (int i = 0; i < MAX_N * MAX_N; i++)
            if (I[i].active) {
                if (earliest == -1 || I[i].time_i < I[earliest].time_i) {
                    earliest = i;
                }
            }
        if (earliest == -1) {
            break;
        }
        Intersection &E = I[earliest];
        if (tstop[E.i] == 0 && (tstop[E.j] == 0 || tstop[E.j] > E.time_j)) {
            tstop[E.i] = E.time_i;
        }
        E.active = 0;
    }

    for (int i = 0; i < N; i++)
        if (tstop[i] == 0)
            cout << "Infinity\n";
        else
            cout << tstop[i] << "\n";
    return 0;
}

n = int(input())
v = list(map(int, input().split()))

ans = 0
for i in range(n):
    total = 0
    s = set()
    for j in range(i, n):
        s.add(v[j])
        total += v[j]
        if total % (j - i + 1) == 0 and (total // (j - i + 1)) in s:
            ans += 1
print(ans)