Solution Notes (Jonathan Paulson): This is a simulation problem, and the constraint that the cows only travel for 10^6 seconds makes it pretty straightforward. You can just write down for each cow where it is at each second as you read the input, and then count the number of times T when their positions at T were different but their positions at T+1 were the same.

The problem is still efficiently solvable if the times are much larger (say, up to 10^12) but the number of instructions is still small (say, 100,000). Then the solution is a version of coordinate compression (which also makes an appearance in "crazy fences"); the only "interesting times" are when a cows speed changes, and there are at most 200,000 of these (each instruction causes an increase and then decrease in speed; actually, since the start of one instruction and the beginning of another overlap, the real number is more like 100,000 but this isn't important). To simplify implementation of this idea, it is useful to keep track of Bessie's movement relative to Elsie, instead of their absolute positions. Then a moo occurs when Bessie passes 0. Now that time is divided up into ~100,000 intervals of constant speed, it is easy to compute the change in position due to each time interval, and keep track of the number of times Bessie passes 0. Here is Travis Hance's solution in C++:

``````#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define BESSIE 0
#define ELSIE 1

// A "Key Point" occurs at any time a cow stops or turns around.
// The cow field represents which cow is changing state, either
// BESSIE or ELSIE. The newdir field represents the new direction
// that cows moves in; either -1 for left, 1 for right, and 0
// for stopped.
struct KeyPoint {
int t;
int cow;
int newdir;
KeyPoint(int t, int cow, int newdir)
: t(t), cow(cow), newdir(newdir) { }
bool operator<(KeyPoint const& o) const {
return t < o.t;
}
};

vector<KeyPoint> keyPoints;

// Reads the input for the given cow and stores its key points
// in the keyPoints vector. Returns the direction that the given
// cow moves at the beginning.
int readKeyPoints(int n, int cow) {
int t = 0;
int initdir;
for (int i = 0; i < n; i++) {
int dt;
scanf("%d", &dt);

char c;
do {
c = fgetc(stdin);
} while (c != 'L' && c != 'R');
int dir = (c == 'R' ? 1 : -1);

if (t == 0) {
initdir = dir;
} else {
keyPoints.push_back(KeyPoint(t, cow, dir));
}

t += dt;
}
keyPoints.push_back(KeyPoint(t, cow, 0));
return initdir;
}

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

int nSteps1, nSteps2;
scanf("%d", &nSteps1);
scanf("%d", &nSteps2);

// Read input and initialize the directions of the cows.

// Sort by time. We could do a linear-time merge instead but
// this is easier and nearly as fast.
sort(keyPoints.begin(), keyPoints.end());

// Initialize time and positions of cows.
int t = 0;
int x1 = 0;
int x2 = 0;

// Initialize counter for the total number of "moo"s
int nMoos = 0;

for (int i = 0; i < keyPoints.size(); i++) {
// Look at the next key point.
int new_t = keyPoints[i].t;
int new_x1 = x1 + (new_t - t) * dir1;
int new_x2 = x2 + (new_t - t) * dir2;

// Determine if the cows moo at some time in the interval (t, new_t].
if (x1 != x2 && (new_x1 == new_x2 || ((x1 < x2) ^ (new_x1 < new_x2)))) {
nMoos++;
}

// Update to the new state.
t = new_t;
x1 = new_x1;
x2 = new_x2;
if (keyPoints[i].cow == BESSIE) {
dir1 = keyPoints[i].newdir;
} else {
dir2 = keyPoints[i].newdir;
}
}

printf("%d\n", nMoos);
}``````