Analysis: Breed Proximity by Fatih Gelgi

First of all, let's focus on the definition of "crowded". If we take a window of size K in the line and cows with the same breed exist in the window then it is crowded. That means, we can find the solution by checking all the windows of size K in the line. Consider the sample input given in the problem; window size is 3 (means 4 cows in the window):

7 3 4 2 3 4	window		max breed id
* * * *   	(0,3) 		none
  * * *	*	(1,4)		3
    * * * *	(2,5)		4

The search starts with window (0,3) and continues with sliding the window till the end of the line. Notice that sliding the window is as simple as removing the cow's breed at the beginning of the window while adding the new cow's breed at the end of the window. Here, "removing" is to decrease breed[x] by 1 where x is the breed of the cow to remove from the window. Similarly, "adding" means to increase breed[x] by 1 where x is the breed of the new cow. Checking if the current window is crowded is also simple; we just need to check if breed[x] > 1 where x is the breed of the new cow.

The running time is O(N) since the process requires only one pass on the cows. Below is the sample code:

#include <fstream>
using namespace std;

int n,k,line[50001],breed[1000001],crowded=-1;

int main()
{
	ifstream fin("proximity.in");
	fin >> n >> k;
	for (int i=0; i<n; i++)
	{
		fin >> line[i];
		// add next cow's breed to the end of sliding window
		breed[line[i]]++;
		// remove the cow's breed at the beginning of the sliding window
		if (i>k) breed[line[i-k-1]]--;
		// if there are more than one breeds in the sliding window, update max crowded
		if (breed[line[i]]>1 && line[i]>crowded)
			crowded=line[i];
	}
	fin.close();

	ofstream fout("proximity.out");
	fout << crowded << endl;
	fout.close();
}

Another way of solving the problem is to sort the cows based on their breed ids (in decreasing order) then their positions. If the first cow and the second cow in the sorted list have the same breed id and their distance is less than or equal to K, they will be crowded and will have the maximum breed id since it is a sorted list (sorted by position secondarily). We stop searching at this point and output the breed id. Otherwise, the search continues with the second and third cow, and so on.

This method requires sorting and one pass on the list of cows in the worst case. Hence, the time complexity is O(N log N). Travis' neat implementation is as follows:

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

#define NMAX 50005

struct Cow {
	int breedID;
	int x;
	bool operator<(Cow const& o) const {
		if (breedID == o.breedID) {
			return x < o.x;
		} else {
			return breedID > o.breedID;
		}
	}
};
Cow cows[NMAX];

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

	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		cows[i].x = i;
		scanf("%d", &cows[i].breedID);
	}

	sort(cows, cows + n);

	for (int i = 1; i < n; i++) {
		if (cows[i].breedID == cows[i-1].breedID && cows[i].x - cows[i-1].x <= k) {
			printf("%d\n", cows[i].breedID);
			return 0;
		}
	}

	printf("-1\n");
}