You are given chefs from different countries (some chefs could be from the same country) and also several votes for chefs (some votes could be for the same chef). You need to find the chef that receives the most number of votes. In case of tie choose the chef with lexicographically smaller name. The same should be found for countries.
The simplest way to solve the problem is to extensively use associative array in the solution (STL map in C++, TreeMap in Java and so on). The associative array stores for each key some value and allows fast accessing and modifying of values by key as well as inserting new pair
(key, value). For simplicity let’s call it map below.
Now when we input chefs, let’s store the country for each chef in map
chefs_countries with has chefs as keys and countries as values:
for i=1 to N read chef, country chef_countires[chef] = country
To handle chef votes we use map having chefs as keys and integers as values and similar map for countries. To fill map of votes for countries, when we input some chef having a vote we use map
chefs_countries to get the country of this chef:
for i=1 to M read chef add 1 to chef_votes[chef] country = chef_countires[chef] add 1 to countries_votes[country]
Finally we should find the best chef and the best country. Consider for example chefs. Then we should iterate over the map of votes for chefs and update the maximal number of votes and the best chef during this loop. Usually map stores keys in sorted order. In the case of strings this coincides with the lexicographical ordering by default. Hence we should update the chef only when we meet the chef with strictly greater number of votes than our previous candidate for the best chef:
max_votes = 0 best_chef = "" for (chef, count) in chefs_votes if max_votes < count then max_votes = count best_chef = chef
In the case of using STL map or Java TreeMap the complexity of such solution is O((N + M) * log N * maxL) where maxL is the maximal length over chefs and countries names, which is 10 in this problem. The log N factor is the complexity of each operation (accessing or modifying) in map.
One can use usual arrays, sorting and binary search to solve this problem with the same complexity but with better constant hidden in asymptotic. See second tester’s solution as a reference.
By using hashing we can achieve complexity O((N + M) * maxL). See fastest solutions to this problem as a reference to such approach.
AUTHOR’S AND TESTER’S SOLUTIONS:
Codechef November 2012 Challenge - TOURMAP
But all readers are still welcomed to provide related problems in comments