Inspirated

 
 

July 11, 2008

Programming Challenges: Australian Voting

Filed under: Blog — krkhan @ 10:44 am

PC/UVa IDs: 110108/10142, Popularity: B, Success rate: low, Level: 1

I had 28 (that’s twenty-eight) “Time Limit Exceeded” tries on this problem. I was looking everywhere for a loop that would drag, for every possible input that would cause breakdown and I couldn’t find any such thing. So much so, that I considered labeling this post as Australian Nightmare. The issue, once I found it, had nothing to do with Australia and all to do with the string and istringstream objects being significantly heavy to be constructed/destructed on each iteration of the loop on lines #138-153.

The book recommends further reading on voting systems and has linked to some mathematical theorem that proves that no voting system can ever be perfect. Considering the democratic results around the world in recent elections, yeah, what an absolute shocker.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>
 
using namespace std;
 
#define NBALLOTS 1000
 
typedef vector< vector< int > > twod_vector;
 
vector< int > calculate(vector< int > &votes, int ncand, bool atleast_50)
{
	vector< int > winners;
 
	int total = votes.size();
	int max = 0;
	for(int i = 0; i < ncand; i++) {
		int vote_count = count(votes.begin(), votes.end(), i);
		bool cond = !atleast_50 || (vote_count > total / 2);
		if(vote_count > 0 &&
				vote_count >= max &&
				cond) {
			max = vote_count;
			winners.push_back(i);
		}
	}
 
	return winners;
}
 
bool compare(pair< int, int > a, pair< int, int > b)
{
	return a.second < b.second;
}
 
map< int, int > vote_map(vector< int > &votes)
{
	map< int, int > table;
 
	for(vector< int >::iterator p = votes.begin();
			p < votes.end();
			p++) {
		table[*p]++;
	}
 
	return table;
}
 
vector< int > least_votes(vector< int > &votes)
{
	map< int, int > table = vote_map(votes);
	vector< int > min_keys;
	int min_value =
		min_element(table.begin(), table.end(), compare)->second;
 
	map< int, int >::iterator p;
	for( p = table.begin(); p != table.end(); p++ ) {
		if(p->second == min_value) {
			min_keys.push_back(p->first);
		}
	}
 
	return min_keys;
}
 
void eliminate(twod_vector &ballots, int value)
{
	for(int i = 0; i < (int) ballots.size(); i++) {
		for(int j = 0; j < (int) ballots.at(i).size(); j++) {
			if(ballots.at(i).at(j) == value) {
				for(int k = i;
					k < (int) ballots.size() - 1;
					k++) {
					ballots.at(k).at(j)
						= ballots.at(k + 1).at(j);
				}
			}
		}
	}
}
 
void eliminate(twod_vector &ballots)
{
	vector< int > min_values = least_votes(ballots.at(0));
 
	for(vector< int >::iterator p = min_values.begin();
			p != min_values.end();
			p++) {
		eliminate(ballots, *p);
	}
}
 
bool draw(vector< int > &votes)
{
	if(!votes.size()) {
		return true;
	}
 
	map< int, int > table = vote_map(votes);
	map< int, int >::iterator p = table.begin();
	int n = p->second;
	p++;
	for(; p != table.end(); p++) {
		if( n != p->second ) {
			return false;
		}
	}
 
	return true;
}
 
int main(int argc, char *argv[])
{
	twod_vector ballots;
	int ncases;
	cin>>ncases;
	cin.ignore();
	string dummy;
	getline(cin, dummy);
 
	for(int i = 0; i < ncases; i++) {
		int ncand;
		cin>>ncand;
		cin.ignore();
 
		vector< string > candidates(ncand);
		for(int j = 0; j < ncand; j++) {
			getline(cin, candidates.at(j));
		}
 
		twod_vector ballots(ncand);
		string str;
		istringstream iss;
		for(int j = 0; j < NBALLOTS; j++) {
			getline(cin, str);
 
			if(str == "") {
				break;
			}
			iss.str(str);
 
			for(int k = 0; k < ncand; k++) {
				int value = *istream_iterator< int >(iss);
				ballots.at(k).push_back(
						value - 1
						);
			}
			iss.clear();
		}
 
		vector< int > winners;
		int j = 0;
		while(winners.size() == 0) {
			if(draw(ballots.at(0))) {
				winners = calculate(ballots.at(0),
						ncand,
						false);
				break;
			}
 
			winners = calculate(ballots.at(0), ncand, true);
			eliminate(ballots);
			j++;
		}
 
		if(!ballots.at(0).size()) {
			for(int k = 0; k < ncand; k++) {
				winners.push_back(k);
			}
		}
 
 
 
		sort(winners.begin(), winners.end());
		if(i > 0) {
			cout<<endl;
		}
		vector< int >::const_iterator p;
		for(p = winners.begin(); p < winners.end(); p++) {
			cout<<candidates.at(*p)<<endl;
		}
	}
 
	return 0;
}
Tags: , , , , , , , , , , ,

4 Comments »

  1. Very nice!!

    Comment by Dymnallorymn — August 3, 2008 @ 4:22 pm

  2. Hi krkhan,
    I’m stuck with the Time Limit Exceeded, but I don’t understand if it’s a matter of algorithm efficiency, or my program falls inside an infinite loop.
    Here are the steps of my solution:
    1 count all the votes per candidate
    2 find min/max number of votes per candidate
    3a if min == max then all the remaining candidates have tied, and they are all winners. Then exit.
    3b else if max/tot > 50 / 10 we have a single winner. Then exit.
    3c find all the ballots starting with a losing candidate and shift the ballot until the head candidate is still in race for winning
    4 come back to #1
    This is the general idea (obviously we can avoid to count the votes at each iteration and also to shift the ballots).

    What do you think about this? Do you see any point of failure?
    Thank you so much.

    Regards,
    Matteo

    Comment by Matteo Landi — November 15, 2010 @ 2:16 am

  3. Hi again,
    I forgot to post a link to the implementation of the algorithm, and one to both the input and the output I use to test things.

    * code: http://pastebin.com/rhqYs1uZ
    * input: http://pastebin.com/UU3Af4hh
    * output: http://pastebin.com/q3hg5sD1

    Regards,
    Matteo

    Comment by Matteo Landi — November 15, 2010 @ 2:18 am

  4. I think I’ve found the bug.
    I was initializing the `min’ variable to a wrong value(number of candidates minus one instead of number of ballots minus minus one): this makes the program enter in an infinite loop, and that’s why I got that LTE message.
    As soon as Programmin-Challenges comes back on-line, I’ll try the fixed solution.

    Regards,
    Matteo

    Comment by Matteo Landi — November 18, 2010 @ 1:37 am

RSS feed for comments on this post. TrackBack URL

Leave a comment