USACO 2014 December Contest, Bronze Problem 4. Learning by Example

原题下载

USACO2014DEC-B4

答案:

(Analysis by Jonathan Paulson - jonathanpaulson@gmail.com)

The main difficulty here is that A and B are so large we cannot consider each new cow separately. We have to batch them up somehow.

Imagine each cow as a point on a number line (corresponding to its weight). Each new cow has (at most) one neighbor to the left and one neighbor to the right, so either a new cow has one nearest neighbor, or it is exactly between two old cows.

So each old cow "covers" some range on the number line where it is the nearest neighbor, depending on the cow to it's left and right (i.e. the next lighter and next heavier cow). By counting up how many new cows each old spotted cow covers, we'll get our answer.

Coding this up is tough. There are a lot of possible off-by-one errors. In the rest of the analysis, I'll walk through how I coded it.

First off: the easiest way to consider a cow and it's neighbors at the same time is to sort them, so let's do that. A nice way to avoid edge cases is to add extra old cows at the beginning and the end so that each cow has two neighbors; if we put these extra cows far enough out, they won't affect anything.

I thought it was easiest to consider each neighboring pair of cows separately. Let S (S for "start") be the weight of the cow on the left and let E (E for "end") be the weight of the cow on the right. We want to handle the interval [S+1,E] (notice we handle the right endpoint but not the left endpoint; this way, our ranges add up to the whole interval with no point counted twice or uncounted).

Let M= (s+E)/2 (M for "middle"). Then the left cow covers the interval [S+1,M] and the right cow covers the interval [M+1,E]. But not every point is a new cow: we need to intersect these intervals with [A,B]. So really, the left cow covers the interval [max(S+1,A),min(M,B)], and the right cow covers the interval [max(M+1,A),min(E,B)]. So if the left cow is spotted, add the left interval. If the right cow is spotted, add the right interval.

Whew! Actually, we've made one mistake: do you see it? We didn't consider the case where MM was right in the middle (if S and E are both even or both odd, M is right in the middle; otherwise, M is in the left interval where we put it). If M is right in the middle, and the left cow is not spotted and the right cow is spotted *and* M is a new cow, then we didn't count M and we should have.

Here's my C++ code, which follows the description above closely:

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

#define PB push_back
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
  ll n, A, B;
  scanf("%lld %lld %lld", &n, &A, &B);
  vector<pll> V;
  for(ll i=0; i<n; i++) {
    char buf[100];
    ll w;
    scanf("%s %lld", buf, &w);
    V.PB(MP(w, buf[0]=='S' ? 1 : 0));
  }
  ll INF = ll(1000)*1000*1000*1000;
  V.PB(MP(-INF, 0));
  V.PB(MP(INF, 0));
  sort(V.begin(), V.end());

  ll ans = 0;
  for(ll i=0; i+1<V.size(); i++) {
    ll S = V[i].X;
    ll E = V[i+1].X;
    ll M = (S+E)/2;

    if(V[i].Y==1) {
      ll s = max(A, S+1);
      ll e = min(B, M);
      if(e >= s) {
        ans += e-s+1;
      }
    }
    if(V[i+1].Y==1) {
      ll s = max(A, M+1);
      ll e = min(B, E);
      if(e >= s) {
        ans += e-s+1;
      }
    }
    if(V[i+1].Y==1 && V[i].Y==0 && (S%2)==(E%2) && A<=M && M<=B) {
      ans++; // Should count M
    }
  }
  printf("%lld\n", ans);
}