Analysis: Photo (bronze) by Fatih Gelgi

Problem can be solved with different approaches. One simple approach is to find the photos one by one starting from the one that has the first cow.

1. Start at cow 1 (say x=1).
2. Increase the size of the photo as large as possible (say y to the ending position).
3. Cut the photo as soon as there are two cows in the range (x,y). The valid photo is (x,y-1).
4. Starting position for the next photo is y.
5. Continue the loop at second step until x passes n.

In this approach, if the loop goes through all cows, it will be too slow. In fact, we can speed up finding the ending position of the current photo. Let the range of the current photo is (x,y). If there is a pair of unfriendly cows a and b in the range then the photo will be valid by excluding b (assuming a < b). That is, the valid range becomes (x,b-1). Similarly, we can find the range of the current photo by looping through the unfriendly cows and narrowing down the ending position.

Consider the following example:

cows
1 2 3 4 5 6 7 8 9 10  unfriendly     	photo 0	  photo 1   photo 2
--------------------  ----------   	-------	  -------   -------
					1,10  .-> 5,10  .-> 10,10
    *         +         3,8		1,7   |   5,10  |   10,10
  *       +             2,6		1,5   |   5,10  |   10,10
      *         +       4,9		1,5   |   5,10  |   10,10
*       +               1,5		1,4   |   5,10  |   10,10
            *      +    7,10		1,4 >-.   5,9 >-.   10,10

The range for the first photo starts with (1,10) narrows down to (1,7), (1,5), (1,4) due to the unfriendly pairs (3,8), (2,6), (1,5) respectively. The second photo start at 5 and finishes at 9. Final ranges for photos are (1,4), (5,9) and (10,10)

There are at most K+1 photos. The running time is O(K^2) since we loop through all unfriendly pairs for each photo. Below is the sample code:

#include <fstream>
#include <algorithm>

#define MAX 1000

using namespace std;

int n,k,a[MAX],b[MAX];

int main()
{
	ifstream fin("photo.in");
	fin >> n >> k;
	for (int i=0; i<k; i++)
	{
		fin >> a[i] >> b[i];
		if (a[i]>b[i]) swap(a[i],b[i]);	// keep as a_i < b_i
	}
	fin.close();

	int cnt=0,left=1,right;
	do
	{
		right=n;
		// find the right end of the current photo
		for (int i=0; i<k; i++)
			// if two unfriendly cows are in the photo
			//    shrink the right end by excluding the cow on the right
			if (left<=a[i] && right>=b[i])
				right=b[i]-1;
		cnt++;
		left=right+1;	// the left end of the next photo starts from right+1
	}
	while (left<=n);

	ofstream fout("photo.out");
	fout << cnt << endl;
	fout.close();
}

Another approach is to sort the unfriendly cows with respect to the cows on the right side. Let (a,b) is the the first unfriendly cow pair in the sorted order (a < b). That means the first photo can have a maximum range of (1,b-1) -- we have to exclude b and we know that there is no other unfriendly pairs in the range since the list is sorted. Then we can skip all the pairs in which the left cow is in this range. The next photo starts at b.

Consider the same example above (unfriendly pairs are sorted with respect to the right cow):

cows
1 2 3 4 5 6 7 8 9 10  unfriendly     	photo 	range
--------------------  ----------   	-----	-----
*       +               1,5		1	1,4
  *       +             2,6		1	1,4
    *         +         3,8		1	1,4
      *         +       4,9		1	1,4
            *      +    7,10		2	5,9
            				3	10,10

This approach requires O(K log K) time for sorting and O(K) time for just one iteration over the unfriendly pairs. That is O(K log K) running time in total -- faster than the first approach.

Travis's neat implementation is as follows:

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

#define KMAX 1000

struct cowpair {
	int x1, x2;
	bool operator<(cowpair const& o) const {
		return x2 < o.x2;
	}
};
cowpair cowpairs[KMAX];

int main() {
#ifndef HOME
	freopen("photo.in","r",stdin);
	freopen("photo.out","w",stdout);
#endif

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

	sort(cowpairs, cowpairs + k);

	int lastx = 0;
	int count = 1;
	for (int i = 0; i < k; i++) {
		if (cowpairs[i].x1 >= lastx) {
			count++;
			lastx = cowpairs[i].x2;
		}
	}
	 
	printf("%d\n", count);
}