Analysis: Fair Photography by Nathan Pinsker

We must guarantee that the number of Guernseys in our photo is equal to the number of Holsteins. If we denote Guernseys with the number 1 and Holsteins with the number -1, then any valid photo is simply a photo whose cows' numbers sum to exactly 0. Given an array that represents our cows, we can quickly find the sums of various blocks of cows by taking the prefix sums of this array. For each cow at position k, we store a number S_k representing the sum of the cows' numbers from 1 to k. To find the sum of cows' numbers from i to j, we can simply compute S_j - S_(i-1).

Motivated by this, we consider each cow in turn, and find the largest photo that can be snapped with that cow as the rightmost cow. The key insight here is that we can simply store the S_i values of all the cows we have already considered. For each distinct value of S_i, we can store the position of the leftmost cow that has that value. If we ever encounter an S_i that we have seen before, we know that we have found a valid photo, by the above logic.

Below is Mark Gordon's code. He stores the S_i values in an array. Since S_i can be negative, but not less than -N, he offsets the values in the array by N so that they are all at least 0.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cassert>

using namespace std;

#define MAXN 100010

int PSUM[MAXN * 2];

int main() {
  freopen("fairphoto.in", "r", stdin);
  freopen("fairphoto.out", "w", stdout);

  int N; cin >> N;
  assert(1 <= N && N <= 100000);
  vector<pair<int, char> > A(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
    assert(0 <= A[i].first && A[i].first <= 1000000000);
  }
  A.push_back(make_pair(1000000010, '?'));
  sort(A.begin(), A.end());
  for(int i = 1; i < N; i++) {
    assert(A[i - 1].first != A[i].first);
  }

  int result = 0;
  for(int i = 0; i < N; ) {
    int sz = 1;
    while(i + sz < N && A[i].second == A[i + sz].second) {
      ++sz;
    }
    result = max(result, A[i + sz - 1].first - A[i].first);
    i += sz;
  }

  int psm = 0;
  memset(PSUM, 0x3F, sizeof(PSUM));
  for(int i = 0; i < N; i++) {
    PSUM[N + psm] = min(PSUM[N + psm], A[i].first);
    psm += A[i].second == 'G' ? 1 : -1;
    result = max(result, A[i].first - PSUM[N + psm]);
  }

  cout << result << endl;
  return 0;
}