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(); }