Analysis: Fair Photography [silver] by Nathan Pinsker

Effectively, we are being asked to find the maximum size of a photo containing an even number of cows, at least half of which are white. This is because, given any such photo, there must be at least as many white cows as spotted cows. We can turn this into a valid photo by painting spots on cows until there are an equal number of white and spotted cows.

To actually find these photos, we separately keep track of cows in odd positions and cows in even positions. The two cows at opposite ends of a valid photo must have opposite "parities", so that there are an even number of cows in the photo. We have one more condition to satisfy, though: we must make sure that the photo we choose is composed of at least half white cows (or, in other words, the number of white cows is greater than the number of spotted cows). Equivalently, if we denote white cows with the number 1 and spotted cows with the number -1, then any valid photo is simply a photo whose cows' numbers sum to a nonnegative even number. We can quickly find the sums of these numbers by taking the prefix sums of this array.

Motivated by this, we consider each cow in turn, and find the best photo that can be snapped with that cow as the rightmost cow. The key insight here is that, if a cow A is to the right of a cow B and has a lower prefix sum as well, then we will never use cow A in a photo and so can remove it from the array. (Any time we can use cow A, we can use cow B, which gives us a larger photo.) Thus, the only cows that matter at any given point have increasing prefix sums from left to right. If we know K is the prefix sum of the cow we're considering, we simply find the cow with prefix sum just above -K in our array. Since we can keep the cows in our array ordered from left to right, their corresponding prefix sums will be ordered from small to large. This means that we can binary search to find the cow that will give us the largest photo, giving a runtime of O(log n) for each of the n steps. The total runtime is thus O(n log n).

Below is Mark Gordon's code. He uses V[0] and V[1] to process the two parities of the cows separately, and uses the lower_bound function to do his binary search.

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

using namespace std;

#define MAXN 100010
#define INF 1000000010

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

  int N; cin >> N;
  vector<pair<int, char> > A(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
  }
  sort(A.begin(), A.end());

  int ps = 0; /* Tracks the prefix sum of the array. */
  int result = 0;
  vector<pair<int, int> > V[2];
  for(int i = 0; i < N; i++) {
    /* Record the current (prefix, position) if 
    if (V[ps & 1].empty() || V[ps & 1].back().first < ps) {
      V[ps & 1].push_back(make_pair(ps, A[i].first));
    }

    /* Update the prefix sum with the current cow. */
    ps += A[i].second == 'W' ? -1 : 1;

    /* Find the farthest starting position that has prefix sum no larger
     * than the current prefix (and therefore starting there gives us more
white cows). */
    if (!V[ps & 1].empty() && ps <= V[ps & 1].back().first) {
      result = max(result, A[i].first -
                           lower_bound(V[ps & 1].begin(), V[ps & 1].end(),
                                       make_pair(ps, -INF))->second);
    }
  }
  cout << result << endl;
  return 0;
}