## 10142 - Australian Voting

Moderator: Board moderators

devil
New poster
Posts: 2
Joined: Tue Aug 17, 2010 11:19 pm
Location: USA

### Re: 10142 - Australian Voting

Hi Guys,
This is my first post here so hello !

My code is accepted on programming challenges but not on uva online judge.
I've passed all the test cases I found here in this topic successfully. I've also tried uvatoolkit succesfully too.

Here is my code if any one could find the problem I'll be grateful

Code: Select all

``````// Australian Voting

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

void readCandidates(map<int, string> &cand, int n){
int c=0;
while(c<n){
string str;
getline(cin, str);
if(str.empty())
continue;
++c;
cand[c] = str;
}
}

void printCandidates(map<int, string> &cand){
for(map<int, string>::iterator it=cand.begin() ; it!=cand.end() ; it++)
//cout << it->second << " : " << it->first << endl;
cout << it->second << endl;
}

void readBallots(vector<vector<int> > &ball, int n){
while(true){
string str;
getline(cin, str);
if(str.empty())
break;
vector<int> b;
b.push_back(1);
stringstream ss(str);
int x;
for(int i=0 ; i<n ; i++){
ss >> x;
b.push_back(x);
}
ball.push_back(b);
}
}

void printBallots(vector<vector<int> > &ball){
cout << "Ballots:" << endl;
for(int i=0 ; i<ball.size() ; i++){
cout << "(" << ball[i][0] << ") ";
for(int j=1 ; j<ball[i].size() ; j++)
cout << ball[i][j] << " ";
cout << endl;
}
cout << endl;
}

void initTable(vector<pair<int, int> > &r, int n){
for(int i=1 ; i<=n ; i++)
r.push_back(make_pair(0, i));
}

void printTable(vector<pair<int, int> > &r){
cout << "Results:" << endl;
for(int i=0 ; i<r.size() ; i++)
cout << r[i].second << " : " << r[i].first << endl;
cout << endl;
}

int total(vector<pair<int, int> > &r){
int sum = 0;
for(int i=0 ; i<r.size() ; i++)
sum += r[i].first;
//if(!sum) cerr << "sum can not equal zero" << endl;
return sum;
}

int rfind(vector<pair<int, int> > &r, int val){
for(int i=0 ; i<r.size() ; i++)
if(r[i].second == val)
return i;
return -1;
}

void initResults(vector<pair<int, int> > &r, vector<vector<int> > &b){
for(int i=0 ; i<b.size() ; i++){
int idx = rfind(r, b[i][1]);
//if(idx==-1) cerr << "index can not equal -1" << endl;
if(idx!=-1)
r[idx].first++;
}
}

double ratio(vector<pair<int, int> > &r, int k){
int sum = total(r);
return ((r[k].first * 1.0) / (double)sum) * 100.0;
}

vector<string> getWinners(vector<pair<int, int> > &r, map<int, string> &c){
vector<int> above;
vector<string> names;
for(int i=0 ; i<r.size() ; i++){
if(ratio(r, i) >= 50)
above.push_back(r[i].second);
}
int max = -1;
for(int i=0 ; i<above.size() ; i++)
if(r[rfind(r, above[i])].first > max)
max = r[rfind(r, above[i])].first;
for(int i=0 ; i<above.size() ; i++){
if(r[rfind(r, above[i])].first == max)
names.push_back(c[r[rfind(r, above[i])].second]);
}
return names;
}

int minResults(vector<pair<int, int> > &r){
int min = r[0].first;
for(int i=1 ; i<r.size() ; i++)
if(r[i].first < min)
min = r[i].first;
return min;
}

bool isTie(vector<pair<int, int> > &r){
int v = r[0].first;
for(int i=0 ; i<r.size() ; i++)
if(r[i].first != v)
return false;
return true;
}

void prune(vector<pair<int, int> > &r, vector<vector<int> > &b){
int min = minResults(r);
for(int i=0 ; i<r.size() ; i++){
if(r[i].first == min){
int del = r[i].second;
for(int j=0; j<b.size() ; j++){
if(b[j][b[j][0]] == del){
bool found = false;
while(!found){
++b[j][0];
int next = b[j][b[j][0]];
int idx = rfind(r, next);
if(idx != -1){
if(r[idx].first == min)
continue;
r[idx].first++;
found = true;
}
}
}
}
int idx = rfind(r, del);
r.erase(r.begin()+idx, r.begin()+idx+1);
}
}

}

int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;

map<int, string> cand;

vector<vector<int> > ball;

vector<pair<int, int> > results;
initTable(results, n);

initResults(results, ball);

vector<string> w = getWinners(results, cand);
if(!w.empty()){
for(int i=0 ; i<w.size() ; i++)
cout << w[i] << endl;
if(t) cout << endl;
continue;
}
if(isTie(results)){
printCandidates(cand);
if(t) cout << endl;
continue;
}

while(true){
prune(results, ball);
vector<string> w = getWinners(results, cand);
if(!w.empty()){
for(int i=0 ; i<w.size() ; i++)
cout << w[i] << endl;
break;
}
if(isTie(results)){
printCandidates(cand);
break;
}
}
if(t) cout << endl;
}
return 0;
}
``````

devil
New poster
Posts: 2
Joined: Tue Aug 17, 2010 11:19 pm
Location: USA

### Re: 10142 - Australian Voting

Thanks, Finally accepted

Nothing better than random test cases!

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int getRand(int a, int b){
return a + random() % b;
}

int main(){
srandom(time(NULL));
int t = getRand(1, 1000);
cout << t << endl << endl;
for(int k=0 ; k<t ; k++){
int n = getRand(1, 20);
cout << n << endl;
for(int i=0 ; i<n ; i++)
cout << (char)('A'+i) << endl;
int b = getRand(1, 1000);
for(int i=0 ; i<b ; i++){
vector<bool> v(1001, false);
for(int j=0 ; j<n ; j++){
int x = getRand(1, n);
while(v[x])
x = getRand(1, n);
v[x] = true;
cout << x << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
}
``````
Comparing 527 test cases with uvatoolkit, I found that this is the only different one:
16
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
5 4 11 1 14 6 2 12 9 16 3 13 15 10 8 7
11 7 1 16 8 10 2 9 14 15 12 5 4 3 13 6
16 6 3 5 1 15 10 14 13 11 2 4 8 12 9 7
14 12 1 6 7 5 16 4 13 10 8 9 2 15 11 3
2 3 10 15 4 13 11 16 9 12 14 5 8 7 6 1
7 11 10 5 8 6 15 14 4 13 2 3 9 16 1 12

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### Re: 10142 - Australian Voting

After several tries, I finally found this random test case:

Code: Select all

``````12
A
B
C
D
E
F
G
H
I
J
K
L
10 9 12 4 5 2 6 3 8 1 7 11
1 7 2 11 4 3 12 10 8 6 9 5
7 10 11 8 6 2 5 1 12 3 4 9
10 4 9 6 12 1 11 8 5 3 2 7
1 4 6 12 2 11 8 10 7 5 3 9
8 4 9 3 11 7 12 2 5 10 1 6
4 1 7 5 9 12 3 6 8 10 11 2
9 6 12 3 1 11 8 2 7 10 5 4
6 9 1 3 11 2 4 10 12 7 5 8
2 10 9 1 4 6 12 11 8 3 5 7
1 10 3 7 4 8 5 6 11 12 9 2
7 10 1 3 12 2 4 11 8 6 5 9
4 8 1 9 5 10 11 7 6 2 3 12
12 8 1 7 9 4 6 10 2 3 11 5
3 2 9 6 1 4 10 11 7 8 12 5
1 2 7 3 10 12 8 4 11 5 9 6
6 11 10 7 5 8 4 2 1 3 12 9
3 8 12 4 7 1 5 11 9 6 10 2
4 8 10 1 6 3 12 5 7 2 11 9
5 8 10 9 7 4 1 11 12 2 3 6
2 10 6 8 5 1 9 4 7 3 12 11
9 5 7 11 4 1 8 10 2 6 3 12
2 12 7 4 3 5 10 9 6 11 8 1 ``````
My WA program gives J as a winner whereas UVA Toolkit gives A.
I solved this case step by step on a piece of paper and my answer seems to be correct according to the description of the problem.
Can anyone explain it to me?

Spribo
New poster
Posts: 3
Joined: Mon Sep 06, 2010 2:07 pm

### Re: 10142 - Australian Voting

I have tried every input appearing on this forum, and I get the expected output, but I still get wrong answer on PC! Could you please provide me some input to find my mistakes?

Code: Select all

``````program avot;

type
candidate=record
name:string[80];
u:integer;
res:real;
end;

var
o,l,p,s,num,cases,index:integer;
d:string;
bal:array[1..1000,1..21] of integer;

function minimum:real;
begin
p:=1;
inc(p);
for p:=1 to num do begin
end;
end;

procedure calc;
begin
for p:=1 to num do
for p:=1 to s do
for p:=1 to num do
end;

procedure declare;
var
j,k:integer;
r:real;
begin
r:=minimum;
for j:=1 to num do begin
end;
end;
for j:=1 to s do begin
k:=2;
inc(k);
if k<=num then  begin
bal[j][1]:=bal[j][k];
end;
end;

end;
calc;
{check for general equality}
p:=1;
inc(p);
if p=num+1 then begin
for p:=1 to num do begin
end;
writeln;
end
{end}
else begin
p:=1;
inc(p);
if p<=num then begin
if index<cases then writeln;

end
else begin
declare;

end;
end;
end;

procedure make(w,t,q:integer);
begin
if t=length(d) then
bal[w][q]:=ord(d[t])-48;
if ord(d[t+1]) in [48..57] then begin
bal[w][q]:=10*(ord(d[t])-48)+(ord(d[t+1])-48);
if q<num then make(w,t+3,q+1);
end
else begin
bal[w][q]:=(ord(d[t])-48);
if q<num then make(w,t+2,q+1);
end;
end;

begin
s:=0;
for index:=1 to cases do begin
for p:=1 to num do
while d<>'' do begin
inc(s);
make(s,1,1);
end;
for p:=1 to num do
calc;
p:=1;
p:=1;
inc(p);
if p=num+1 then begin
for o:=1 to num do  begin
end;

end
else begin
p:=1;
inc(p);
if p<=num then begin
writeln;

end
else
declare;

end;
end;
end.``````

Spribo
New poster
Posts: 3
Joined: Mon Sep 06, 2010 2:07 pm

### Re: 10142 - Australian Voting

Well, I got solved... I had just a mistake in what had to do with updating the number of ballots... Variable s in my code isn't properly updated. And I had to add some code to output blank lines so as to get solved instead of presentation error...

reggaeguitar
New poster
Posts: 3
Joined: Fri Jan 18, 2013 1:35 am

### Re: 10142 - Australian Voting

Hi everyone, I'm getting a TLE for this problem, I have tested it with all the test cases I have found here and I get the right answer, I think the problem might be in the i/o portion, if anyone is willing to take a look at my code I would really appreciate it, feel free to message me any questions you might have, thanks

Code: Select all

``````#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX_CANDIDATES = 20;

template <typename T>
void free2D(T** arr, int size);

void tallyVotes(int* totals, int** ballots, int numBallots, int numCandidates, vector<int> loserIndices)
{
for (int i = 0; i < numBallots; ++i)
{
int voteIndex = -1;
while (true)
{
bool skipVote = false;
if (voteIndex == numCandidates - 2)
break;
voteIndex++;
int curVote = ballots[i][voteIndex];
for (unsigned int j = 0; j < loserIndices.size(); ++j)
{
//check to see if the ballots first vote is on
//the loser's list, if it is then check next vote
//until finding one that is not on the loser's list
if (curVote == loserIndices[j])
{
skipVote = true;
break;
}
}
if (skipVote == false)
{
++totals[curVote];
break;
}
}
}
}

vector<int> findWinner(int** ballots, int numBallots, int numCandidates)
{
vector<int> loserIndices;
bool firstTally = true;
int* totals = new int[numCandidates];
for (int i = 0; i < numCandidates; ++i)
totals[i] = 0;

while (true)
{
vector<int> curLoserIndices;
vector<int> winnerIndices;

if (firstTally == true)
{
}

/*cout << endl; //debug
for (int i = 0; i < numCandidates; ++i) //debug
{
cout << totals[i] << endl;
}*/

if (loserIndices.size() == 0)
{
}
else
{
//find candidate with least votes who isn't
int tempMin = MAX_VOTES + 1;
for (int n = 0; n < numCandidates; ++n)
{
if (totals[n] < tempMin)
{
bool notInLosers = true;
for (int p = 0; p < loserIndices.size(); ++p)
{
if (loserIndices[p] == n)
{
notInLosers = false;
break;
}
}
if (notInLosers == true)
tempMin = totals[n];
}
}
}

for (int i = 0; i < numCandidates; ++i)
{
{
winnerIndices.clear();
winnerIndices.push_back(i);
}
{
winnerIndices.push_back(i);
}
else if (totals[i] < minNumVotes && firstTally == true)
{
curLoserIndices.clear();
curLoserIndices.push_back(i);
}
{
curLoserIndices.push_back(i);
}
}

//
for (int m = 0; m < winnerIndices.size(); ++m)

if (maxNumVotes > numBallots / 2 || totalWinnerVotes == numBallots) //or the total of tied candidate votes = num ballots
{
return winnerIndices;
}
else
{
loserIndices.insert(loserIndices.end(), curLoserIndices.begin(), curLoserIndices.end());
//clean up before next tally first
for (int i = 0; i < numCandidates; ++i)
totals[i] = 0;
firstTally = false;
}
}
}

void processCase()
{
int numCandidates;
scanf("%d", &numCandidates);
getchar(); //eat newline after numCandidates
stringstream os;
string line;
char** candidateNames = new char*[numCandidates];
for (int i = 0; i < numCandidates; ++i)
{
candidateNames[i] = new char[81];
getline(cin, line);
if (line.empty())
continue;
strcpy(candidateNames[i], line.c_str());
}
int** ballots = new int*[1000];
for (int i = 0; i < 1000; ++i)
{
ballots[i] = new int[numCandidates];
}
int ballotIndex = -1;
while (true)
{
getline(cin, line);
if (line.empty())
break;
++ballotIndex;
istringstream is(line);
for (int i = 0; i < numCandidates; ++i)
{
int temp;
is >> temp;
ballots[ballotIndex][i] = temp - 1;
}
}
vector<int> winnerIndices;
//ballotIndex = number of ballots
winnerIndices = findWinner(ballots, ballotIndex, numCandidates);
//ofstream outf("out.txt", ios::app);//debug
for (unsigned int i = 0; i < winnerIndices.size(); ++i)
{
cout << candidateNames[winnerIndices[i]] << endl; //outf << candidateNames[winnerIndices[i]] << endl; //debug
}
printf("\n");
//outf << endl; //debug
free2D(candidateNames, numCandidates);
free2D(ballots, ballotIndex);
}

template <typename T>
void free2D(T** arr, int size)
{
//size is the number of rows in the array
for (--size; size >= 0; size--)
{
//delete each row
delete[] arr[size];
}
//delete the pointers to the rows
delete[] arr;
}

int main()
{
int numCases;
scanf("%d", &numCases);
getchar(); //eat newline after numCases
int caseCounter = 0;
while (--numCases > -1)
{
++caseCounter;
processCase();
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10142 - Australian Voting

Yes your input parsing seems wrong. Try input:

Code: Select all

``````2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2``````
getchar(); //eat newline after numCandidates
You could do something like:
while(getchar()!='\n');
and then the comment is redundant and it'll still work if there is trailing whitespace.
Check input and AC output for thousands of problems on uDebug!

tropiciel
New poster
Posts: 1
Joined: Thu Jan 31, 2013 10:01 pm

### Re: 10142 - Australian Voting

I wasted 4 days on it, only to learn that my only mistake was to print one newline too much at the end of output. Sigh.

Code: Select all

``````    if( i < cases-1 )
std::cout << std::endl;
``````

zaloo
New poster
Posts: 1
Joined: Mon Sep 23, 2013 12:49 am

### Re: 10142 - Australian Voting

So I've been trying this problem and have been getting a TLE. I've tried every test case i could think of, and I've passed every one of them. I'm pretty sure that my code is infinite looping at some point but I'm not sure. Anyone have some test cases I can try out to see where I'm fucking up?

rosynirvana
New poster
Posts: 4
Joined: Thu Oct 03, 2013 10:16 pm

### Re: 10142 - Australian Voting

It seems that the verdict result is inaccurate -- TLE could be judged as RE.
I got lots of RE first and I moved to a smarter way, then got AC.
But I don't think my first solution will cause a runtime error.

leschiller
New poster
Posts: 1
Joined: Sun May 18, 2014 9:52 pm

### Re: 10142 - Australian Voting

The Output consists of either a single line containing the name of the winner or several lines containing the names of the candidates who tied.
It seems to me the output description is lacking the fact that the names must be written in the same order as the input.
After I solved the problem, I tried resending the code with the following change: the names of the winners would be shuffled.
This turned out as a Wrong Answer. I know little about the judge, but if it only compares the output to a fixed file, that could explain why shuffled sets of winners are not accepted.

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 10142 - Australian Voting

hey !
we all had problem in scanning input
i used the pattern
while(getline(cin , s) && s != "")
the problem is dealing with the last test case
thus for ex. input

Code: Select all

``````2

1
a

2
a
b
2 1
``````
notice that there is no blank line after the last test case
the output is

Code: Select all

``````a

b
``````
but using this pattern the program will output

Code: Select all

``````a

``````
then waits for blank line
however, i got accepted but don't know why
or how to deal with this case &thanks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10142 - Australian Voting

Check input and AC output for thousands of problems on uDebug!

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 10142 - Australian Voting

brianfry713 » Sat Sep 06, 2014 7:58 pm

Code: Select all

``````// Australian Voting_10142_NS.cpp : Defines the entry point for the console application.
//

//#define _CRT_SECURE_NO_WARNINGS

/*#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include <WinUser.h>*/
#include <sstream>
#include <iostream>
#include <string>
using namespace std;

bool isdigit(char c)
{
if(c == '1' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6' || c == '6' || c == '7' || c == '8' || c == '9' || c == '0')
return 1;
return 0;
}
int findm(int p[] , int l)
{
int min = p[1];
for(int i = 2; i <=l; i++)
{
min = (min < p[i])? min : p[i];
}
return min;
}

string t;
int main()
{
int T;
cin>>T;
//getline(cin , t);
//stringstream(t) >> T;

while(T--)
{
int n;
cin>>n;
//getline(cin , t);
//stringstream(t) >> n;

string *names = new string [n+1];
getline(cin , names[0]);

for(int i = 1; i<=n; i++)
{
getline(cin , names[i]);
//cout<<names[i]<<endl;
}

int command[1001][21];

string s;
//getline(cin,s);
int a = 1,b = 1;

// the while loop condition !!!!
while(getline(cin , s) && s != "")
{
int x;
for(int i = 0; i<= s.length()-1; i+=0)
{
if(isdigit(s[i]) && (i+1 <= s.length()-1 && isdigit(s[i+1])))
{
x = 10*(s[i] - '0') + (s[i+1] - '0');
i+=3;
}
else if(isdigit(s[i]))
{
x = (s[i] - '0');
i+=2;
}
else
i++;
command[a][b] = x;
b++;
}
a++;
b = 1;
}
/*
for(int i = 1; i < a; i++)
{
for(int j = 1; j <= n; j++)
cout<<command[i][j]<<" ";
cout<<endl;
}
*/

/*
//int a;
//cin>>a;
for(int i = 1; i<= a; i++)
for(int j = 1; j<= n; j++)
cin>>command[i][j];
*/

bool fin = 0;
int index;
bool *eliminated = new bool [n+1];
for(int i = 1; i <= n; i++)
{
}

again:
for(int i = 1; i < a; i++)
{
//cout<<command[i][1]<<endl;
for(int k = 1; k <= n; k++)
{
if(command[i][1] == k)
{
int j = 2;
while(eliminated[k])
{
k = command[i][j];
j++;
}
//cout<<kk<<endl;///////////////////////////////////
{
fin = 1;
index = k;
break;
}
}
}
//Sleep(500);
if (fin)
break;
}
if(!fin)
{
bool end = 1;
int min = findm(votes , n);
//cout<<min<<endl;///////////////////////////////////////////
for(int k = 1; k<=n; k++)
{
{
end = 0;
break;
}
}
if(!end)
{
for(int k = 1; k<=n; k++)
{
{
eliminated[k] = 1;
}
else if(!eliminated[k])
{
}
}
goto again;
}
}

if(fin)
//cout<<"winner "<<index<<endl;
cout<<names[index]<<endl;
if(!fin)
{
//cout<<"winners "<<endl;
for(int i = 1; i<=n; i++)
{
if(!eliminated[i])
{
cout<<names[i]<<endl;
}
}
}
if(T > 0)
cout<<endl;

}
return 0;
}
``````