Analysis: Record Keeping by Fatih Gelgi

The trivial idea is to try all possibilities: check how many times each group appears in the list. We know that the order of cows can be different in same groups. Trying all cow permutations in a group complicates coding. Instead, a better idea is to sort the cows alphabetically in a group and store them in a string. Then we can search each string in the list easily. For instance, the sample will input will be as follows after sorting each group:

BESSIE ELSIE MATILDA
BESSIE FRAN INGRID
BESSIE ELSIE MATILDA
FRAN INGRID MATILDA
BESSIE ELSIE MATILDA

Now, we can clearly see the string "BESSIE ELSIE MATILDA" appears in the list three times. Note that we put space between cows instead of having "BESSIEELSIEMATILDA". Otherwise, the solution will fail in the following input - "BESSI EELSIE MATILDA" is not same as "BESSIE ELSIE MATILDA":

BESSI EELSIE MATILDA
BESSIE FRAN INGRID
BESSIE ELSIE MATILDA
FRAN INGRID MATILDA
BESSIE ELSIE MATILDA

The running time will be O(N^2) since we search each string in the entire list. N is small hence the solution is fast enough for the problem. Sample code is as follows:

// O(N^2)
#include <fstream>
#include <algorithm>

using namespace std;

int n;
string groups[1001];

int main()
{
	ifstream fin("records.in");
	fin >> n;
	for (int i=0; i<n; i++)
	{
		string str[3];
		fin >> str[0] >> str[1] >> str[2];
		sort(str,str+3);				// sort each group
		groups[i]=str[0]+" "+str[1]+" "+str[2];		// and convert it to a string
	}
	fin.close();

	int best=0;
	for (int i=0; i<n; i++)
	{
		int cnt=0;
		// search for the groups that are same as group i 
		for (int j=0; j<n; j++)
			if (groups[i]==groups[j]) cnt++;
		if (best<cnt) best=cnt;	// update the best count
	}

	ofstream fout("records.out");
	fout << best << "\n";
	fout.close();
}

Although it is not necessary for this problem, a faster solution may worth mentioning for similar problems in bronze division. In the first solution, we have a list of strings that correspond to the groups with sorted cows. Let's sort the entire list this time. Then the sample input will become as follows:

BESSIE ELSIE MATILDA
BESSIE ELSIE MATILDA
BESSIE ELSIE MATILDA
BESSIE FRAN INGRID
FRAN INGRID MATILDA

Now, it is much easier and faster to find same groups since they will be consecutive. This solution requires sorting the entire list which is O(N log N) and only one pass over the list is necessary which is O(N). Here's the code for the faster solution:

// O(N log N)
#include <fstream>
#include <algorithm>

using namespace std;

int n;
string groups[1001];

int main()
{
	ifstream fin("records.in");
	fin >> n;
	for (int i=0; i<n; i++)
	{
		string str[3];
		fin >> str[0] >> str[1] >> str[2];
		sort(str,str+3);				// sort each group
		groups[i]=str[0]+" "+str[1]+" "+str[2];		// and convert it to a string
	}
	fin.close();

	sort(groups,groups+n);				// sort the entire list

	int best=0;
	for (int i=0,j=1; i<n; i++,j++)
		// continue counting until the next string is different
		if (groups[i]!=groups[i+1])
		{
			if (best<j) best=j;		// update the best count
			j=0;
		}

	ofstream fout("records.out");
	fout << best << "\n";
	fout.close();
}