Kattis Challenge - Recount - count who has the most votes in a list of names

Question

I am attempting to solve the Kattis problem Recount.

The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge!

In their desperation, the election officials turn to you and ask you to write a program to count the vote!

Input

The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least 2 votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to 100,000 valid votes.

Output

If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: "Runoff!" (don’t forget to include the exclamation mark!)

Sample Input 1

Penny Franklin 
Marti Graham 
Connie Froggatt 
Joseph Ivers 
Connie Froggatt 
Penny Franklin 
Connie Froggatt 
Bruce Stanger 
Connie Froggatt 
Barbara Skinner 
Barbara Skinner 
***

Sample Output 1

Connie Froggatt

Sample Input 2

Penny Franklin 
Connie Froggatt 
Barbara Skinner 
Connie Froggatt 
Jose Antonio Gomez-Iglesias 
Connie Froggatt 
Bruce Stanger 
Barbara Skinner 
Barbara Skinner
***

Sample Output 2

Runoff!

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
struct voter
{
 string name;
 int numvotes;
 bool operator==(const string &) const;
 bool operator<(const voter &) const;
 bool operator>(const voter &) const;
};
bool voter::operator==(const string &f) const
{
 return name == f;
}
bool voter::operator<(const voter &f) const
{
 return (numvotes < f.numvotes);
}
bool voter::operator>(const voter &f) const
{
 return (numvotes > f.numvotes);
}
bool myfunction(voter i, voter j) { return (i<j); }
int main() {
 vector<voter> voters;
 string name;
 while (getline(cin, name))
 {
 if (name == "***")
 {
 break;
 }
 _Vector_iterator<_Vector_val<_Simple_types<voter>>> it = find(voters.begin(), voters.end(), name);
 if (it != voters.end()) {
 it->numvotes += 1;
 }
 else
 {
 voter a;
 a.name = name;
 a.numvotes = 1;
 voters.push_back(a);
 }
 }
 sort(voters.begin(), voters.end(), greater<voter>());
 if (voters[0].numvotes == voters[1].numvotes)
 {
 cout << "Runoff!" << endl;
 }
 else
 {
 _Vector_iterator<_Vector_val<_Simple_types<voter>>> tt = max_element(voters.begin(), voters.end());
 cout << tt->name << endl;
 }
 return 0;
}

My program will pass all of the tests except the very last one where it "times out". Any input I can get on this will be greatly appreciated. This code does compile and run in VS and here: http://cpp.sh/8l3b

To get this to run on cpp.sh I did have to change the _Vector_iterator<_Vector_val<_Simple_types<voter>>> on lines 43 and 63 to auto. I don't quite understand why, so I would also be very appreciative if you could explain what I should use as a type to be portable.

Answer 1

There are 2 important performance issues here:

1. find(...) in a vector performs a linear search, \$O(n)\$. You would do better by using a hash map instead, that would allow constant-time search, \$O(1)\$.

2. Sorting the candidates by vote count is unnecessary to find the ones with the maximum count. Sorting is an \$O(n \log n)\$ operation. You can find the maximum with a linear search, \$O(n)\,ドル and in a second linear pass you could verify if a run-off is needed. (You could as well make this part of step 1 and do it in a single pass, but that wouldn't change the order of complexity of the algorithm.)

Lastly, a minor thing, but the implementation will fail if there are less than two candidates :-)

Answer 2

@janos is correct in pointing out your two main inefficiencies:

• Using a vector instead of a map makes the counting process take O(v²) time, where v is the number of votes. Either way, it would take O(n) space, where n is the number of candidates.
• Sorting the counts would take O(n log n) time, whereas finding the maximum would take O(n) time.

There is a specific algorithm to do this task: the Boyer-Moore Majority Vote Algorithm. It works by keeping track of the frontrunner as the count progresses. Note that you would still need to store all of the votes in a vector to verify that the leader has a majority.

Answer 3

As others have already commented on the performance issues, I will comment on your C++ usage.

---

Don't use using namespace std;

It is bad practice to use using namespace std;, although this is that bad for small programs such as yours, it would be better if you could get rid of that habit as soon as possible :) (If you know what you are doing, then you may keep it - but only if you really know what you are doing).

What's _Vector_iterator?

What's _Vector_iterator? Wait, is that a compiler specific type to denote an iterator for std::vector? Not good! I don't know what compiler is in use, but using compiler specific types is very bad because:

• You have no guarantee that _Vector_iterator is still going to be a vector iterator when the compiler is upgraded
• Your code doesn't compile on any other compiler

This is not only for _Vector_iterator, but for every other type beginning with a _ that you are using.

Instead, use std::vector<T>::iterator for an iterator, std::vector<T>::value_type for T and so on. If you can use C++11, use auto:

auto it = std::find(voters.begin(), voters.end(), name);

Avoid std::endl

std::endl outputs a newline, and flushes the output stream. Depending on the platform, this is not always needed, and if you know you need to flush the stream to see any output, better be explicit and use std::flush.

Flushing is expensive, so this may slow down your program. Additionally, to speed up input/output, you can unsync with stdio (the sync is used if you are using std::printf and std::cout interchangeably, but if you are only using one of them, you can safely turn in off). This will give you a small performance cases if you have to output a lot of strings:

std::ios::sync_with_stdio(false);

Remove the unnecessary function

You are not using myFunction anywhere in your program, so you can safely remove it.

You don't need return 0;

You don't need to return 0; from main, as the compiler will implicitly do it for you. Although sometimes, it doesn't harm specifying it, when for example you are returning with an error in main, and want to show that the function was a success.

You can use emplace_back

Instead of creating a voter, filling it with data, and the copying it to the vector, you can directly construct it in the vector using emplace_back:

voters.emplace_back(name, 1);

Note that this will require you to write a constructor for voter.