CVOTE - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Associative array

PROBLEM:

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.

EXPLANATION:

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

The same should be applied for the map countries_votes. See author’s solution and tester’s first solution as a reference.

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.

ALTERNATIVE SOLUTION:

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:

Author’s solution can be found here.
Tester’s first solution can be found here.
Tester’s second solution can be found here.

RELATED PROBLEMS:

Codechef November 2012 Challenge - TOURMAP
But all readers are still welcomed to provide related problems in comments :slight_smile:

3 Likes
2

Problem TOURMAP :slight_smile:

1 Like
3

Added. Thanks.

4

Anton Sir, I do not get this line in your solution chefs[i] = make_pair(chef, country);

What is its mechanism? I am unaware of templates as of now. I read this http://www.cplusplus.com/reference/utility/make_pair/ but its still not clear to me. I will be glad if you explain a bit. Thanks.

5

Unlikely I could explain you better than at the mentioned page :slight_smile:

Just note that chefs[] was created as array of pairs of strings:

pair<string, string> chefs[maxN]

So I use make_pair to convert two strings chef and country into the pair of strings.

Alternatively I could write:
chefs[i] = pair<string, string> (chef, country)
to use explicit constructor of exactly this type of pairs.
But as you see this way is longer.

1 Like
6

Thanks for the pair’ clarification, next line I din’t understand was int cN = unique(countries, countries + N) - countries;
Again the same problem, the mechanism part. I wonder how it is done in just one line where users have spent an entire algo for that. :frowning:

7

Well, your explanations are great. Things seeming tough at one sight look easy afterwards. I love things from the basic point of view, and hence your explanation. :slight_smile:

8

This is indeed neat one.
Before some time I wrote some long version like

for (cN = i = 0; i < N; ++i)
    if (i == 0 || a[i-1] < a[i])
        a[cN++] = a[i];

Then I saw this simple way at someone’s GCJ code.
The mechanism is that unique(a,a+N) behaves like the loop above and return pointer a+cN.

Hence to obtain the count we subtract a from it:
unique(a,a+N)-a which is (a+cN)-a = cN.

1 Like
9

pretty cool! :slight_smile:

10

One more doubt Sir, in the sort(chefs, chefs + N) call, why not N - 1 and why is it N? I am assuming the standard sort() function to operate over N elements (chefs), so 0 to N - 1, then why chefs + N?

11

Any clue why WA ?
http://www.codechef.com/viewsolution/1685899

12

It is a standard concept in C++ to include left end of the range but not include right end.

So range [0,N-1] is represented as [0,N)

13

You did not output anything for the test where N=10000 and M=1.

Try some simpler version like
2 1
a b
c d
a

1 Like
14

@anton_lunyov >> Please check my sample code I wrote to understand unique() further, but I am confused a bit.

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int arr[] = {1, 2, 3, 4, 4, 5, 5, 6};
	for(int i=0; i<8; i++)
		cout<<arr[i]<<endl;
	cout<<"\n";
	//cout<<unique(arr, arr+8)<<endl;
	int cn = unique(arr, arr+8) - arr;
	for(int i=0; i<8; i++)
		cout<<arr[i]<<endl;
	cout<<"cn = "<<cn<<endl;
	return 0;
}

It prints cn = 6. But when you un-comment line #9, it prints 8. What is the point here?

15

The reason is that unique works correctly only for sorted array.
When you do unique(a,a+8) the content of a[] becomes
a[] = {1,2,3,4,5,6,5,6}
since he stores all unique elements in the beginning but not touch the remaining ones.

When you do unique(a,a+8) twice second time is applied to bad array {1,2,3,4,5,6,5,6}.
Actually unique delete only repetitions of consecutive equal elements.
Hence he consider this array as having all unique elements and returns pointer a+8

16

Okay, but why are the last three elements 6,5,6 and why not 4,5,6?
Since the unique elements brought forwards should have made the arr[] as {1,2,3,4,5,4,5,6} from my point of view. My question is: why {1,2,3,4,5,6,5,6} any mechanism for that?

17

Oops, is it due to the a[cN++] = a[i] part that you wrote in the earlier “longer” version that you mentioned in comment to my last answer?

18

Yes, exactly. But try to output array after unique to make sure that I’m right.

19

Yes, you were right. Thanks. Nothing else beats the joy of learning something new everyday.

20

Sir, please explain this last part (most probably):

int chef_id = lower_bound(chefs, chefs + N, make_pair(chef,string())) - chefs;


int country_id = lower_bound(countries, countries + cN, country) - countries;

I get why make_pair() was used and why it was not used in the country_id, but I do not get what lower_bound() is doing? Can I get the raw code for this function, like you gave for unique()?