USACO NOV06 Problem 'badhair' Analysis

by Richard Peng

Define N[i] to be the first cow to the right of cow i which is taller than cow i. It's quite obvious that calculating N[i] for all i is equivalent to solving the problem.

An easy observation is that if h[i]>h[j], n[i]>j, then n[i]>=n[j] since if n[i]h[i]>h[j], contradicting with the definition of n[j]. Therefore, we could start n[i] as i+1 and while h[n[i]]The proof that this algorithm runs in O(N) time is non-trivial. First note that we coudl not have ih[n[i]]>i. Therefore, once we have calculated n[i], all the n values between i and n[i] will never be accessed again by j(There also is a different solution using stacks, but this solution appears to be much more straightforward)

Code (by Brian Dean):

#include <stdio.h>

#define MAX_N 100000
int N, h[MAX_N], n[MAX_N];

unsigned int solve(void) {
  unsigned int T = 0;
  int i, c;

  for (i=N-1; i>=0; i--) {
    c = 0; n[i] = i+1;
    while (n[i] < N && h[n[i]] < h[i]) {
      c += n[n[i]] - n[i];
      n[i] = n[n[i]];
    }
    T += c;
  }
  return T;
}

int main(void) {
  FILE *fp;
  int i;

  fp = fopen ("badhair.in", "r");
  fscanf (fp, "%d", &N);
  for (i=0; i<N; i++) fscanf (fp, "%d", &h[i]);
  fclose (fp);
  
  fp = fopen ("badhair.out", "w");
  fprintf (fp, "%u\n", solve());
  fclose (fp);

  return 0;
}