Analysis: Cow Crossings by Brian Dean


This problem can be approached several different ways.

One idea that perhaps comes to mind initially but is not quite correct is to sort the cows on A and then sort again on B, and treat a cow as safe if it ends up in the same position in both orderings. However, this unfortunately does not work, due to cases like this:

3
1 3
2 2
3 1

The key observation we should make to solve this problem is that a cow is safe if all the cows before her in the A ordering are also before her in B, and if all the cows after her in A are also after her in B. We can test this efficiently by sorting the cows on A and then scanning through the ordering, keeping a running maximum of the B value of each cow as we go. When we reach a particular cow (a,b), we check if the max B we have seen so far is smaller than b -- this means that all the cows before (a,b) in the A ordering are also before this cow in the B ordering. We then need to do the same thing in reverse: scan backwards through the A ordering while keeping a running minimum of the B values; when we encounter a cow (a,b), we test if the min B we have seen so far is larger than b, as this ensure that all the cows after (a,b) in the A ordering are also after this cow in the B ordering.

Here is Jonathan Paulson's solution written in Java:


import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class crossings {
    public static int i(String s) { return Integer.parseInt(s); }
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new FileReader("crossings.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("crossings.out")));
        int n = i(in.readLine());
        int[][] P = new int[n][2];
        for(int i=0; i<n; i++) {
            String[] arr = in.readLine().split(" ");
            P[i] = new int[]{i(arr[0]), i(arr[1])};
        }
        Arrays.sort(P, new Comparator<int[]>() {
            public int compare(int[] A, int[] B) {
                return A[0]-B[0];
            }
        });

        int[] maxl = new int[n];
        maxl[0] = P[0][1];
        for(int i=1; i<n; i++)
            maxl[i] = Math.max(maxl[i-1], P[i][1]);

        int[] minr = new int[n];
        minr[n-1] = P[n-1][1];
        for(int i=n-2; i>=0; i--)
            minr[i] = Math.min(minr[i+1], P[i][1]);

        int safe = 0;
        for(int i=0; i<n; i++) {
            boolean ok = true;
            if(i!=0 && maxl[i-1] > P[i][1]) ok = false;
            if(i!=n-1 && minr[i+1] < P[i][1]) ok = false;
            if(ok) safe++;
        }
        out.println(safe);
        out.flush();
    }
}

Here is a solution from Travis Hance written in C++:


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define NMAX 100000

struct Crossing {
	int x1, x2;
	int x2index;
};
Crossing crossings[NMAX];

inline bool cmp1(Crossing a, Crossing b) {
	return a.x1 < b.x1;
}

inline bool cmp2(Crossing a, Crossing b) {
	return a.x2 < b.x2;
}

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

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &crossings[i].x1);
		scanf("%d", &crossings[i].x2);
	}

	sort(crossings, crossings + n, cmp2);
	for (int i = 0; i < n; i++) {
		crossings[i].x2index = i;
	}

	sort(crossings, crossings + n, cmp1);
	int answer = 0;
	int maxX2indexSeen = -1;
	for (int i = 0; i < n; i++) {
		if (crossings[i].x2index == i && maxX2indexSeen == i-1) {
			answer++;
		}
		maxX2indexSeen = max(maxX2indexSeen, crossings[i].x2index);
	}

	printf("%d\n", answer);
}