10142 - Australian Voting

[devil]

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;
		readCandidates(cand, n);

		vector<vector<int> > ball;
		readBallots(ball, n);

		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]

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]

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]

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;
        cads:array[1..21] of candidate;
        bal:array[1..1000,1..21] of integer;

function minimum:real;
	begin
		p:=1;
                while cads[p].u=0 do
                      inc(p);
                minimum:=cads[p].res;
		for p:=1 to num do begin
			if (cads[p].res<minimum) and (cads[p].u<>0) then
				minimum:=cads[p].res;
		end;
	end;

procedure calc;
          begin
               for p:=1 to num do
	           cads[p].res:=0;
               for p:=1 to s do
	           cads[bal[p][1]].res:=cads[bal[p][1]].res+1;
	       for p:=1 to num do
	           cads[p].res:=cads[p].res/s;
         end;

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

             end;
             calc;
             {check for general equality}
             p:=1;
             while (p<=num) and (cads[p].res=cads[1].res) do
                   inc(p);
             if p=num+1 then begin
                for p:=1 to num do begin
                    if cads[p].u=1 then writeln(cads[p].name);
                end;
                writeln;
                end
             {end}
             else begin
                     p:=1;
		while (p<=num) and (cads[p].res<=0.5) do
		      inc(p);
		if p<=num then begin
		   writeln(cads[p].name);
                   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;
	readln(cases);
	for index:=1 to cases do begin
		readln(num);
		for p:=1 to num do
			readln(cads[p].name);
		readln(d);
		while d<>'' do begin
			inc(s);
			make(s,1,1);
			readln(d);
		end;
		for p:=1 to num do
			cads[p].u:=1;
                calc;
               	p:=1;
                p:=1;
             while (p<=num) and ((cads[p].res=cads[1].res) or (cads[p].res=0)) do
                   inc(p);
             if p=num+1 then begin
                for o:=1 to num do  begin
                    if cads[o].res<>0 then writeln(cads[o].name);
                      end;

                end
                else begin
                p:=1;
		while (p<=num) and (cads[p].res<=1/2) do
			inc(p); 
		if p<=num then begin
			writeln(cads[p].name);
			writeln;

		end
                else
		declare;

                end;
end;
end.

[Spribo]

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]

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_VOTES = 1000;
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 maxNumVotes = 0;
	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)
		{
			tallyVotes(totals, ballots, numBallots, numCandidates, loserIndices);
		}
		
		/*cout << endl; //debug
		for (int i = 0; i < numCandidates; ++i) //debug
		{
			cout << totals[i] << endl;
		}*/
		
		int minNumVotes;
		if (loserIndices.size() == 0)
		{
			minNumVotes = MAX_VOTES + 1;
		}
		else
		{
			//find candidate with least votes who isn't
			//already in loserIndices
			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];
				}
			}
			minNumVotes = tempMin;
		}

		for (int i = 0; i < numCandidates; ++i)
		{
			if (totals[i] > maxNumVotes)
			{
				maxNumVotes = totals[i];
				winnerIndices.clear();
				winnerIndices.push_back(i);
			}
			else if (totals[i] == maxNumVotes)
			{
				winnerIndices.push_back(i);
			}
			else if (totals[i] < minNumVotes && firstTally == true) 
			{
				minNumVotes = totals[i];
				curLoserIndices.clear(); 
				curLoserIndices.push_back(i);
			}
			else if (totals[i] == minNumVotes)
			{
				curLoserIndices.push_back(i);
			}
		}
	
		//
		int totalWinnerVotes = 0;
		for (int m = 0; m < winnerIndices.size(); ++m)
			totalWinnerVotes += totals[winnerIndices[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;
			tallyVotes(totals, ballots, numBallots, numCandidates, loserIndices);
		}
	}
}

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]

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

Instead of:
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.

[tropiciel]

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]

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]

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]

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]

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]

I can't understand your issue, seeing your code might help.

[fresher96]

brianfry713 » Sat Sep 06, 2014 7:58 pm

I can't understand your issue, seeing your code might help.

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];
		*/

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

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;///////////////////////////////////
					votes[k]++;
					if(votes[k]*1.0/a > 0.5)
					{
						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++)
			{
				if(votes[k] != min && votes[k] != 999999)
				{
					end = 0;
					break;
				}
			}
			if(!end)
			{
				for(int k = 1; k<=n; k++)
				{
					if(min == votes[k])
					{
						//cout<<k<<"  "<<votes[k]<<endl;/////////////////////////////
						votes[k] = 999999;
						eliminated[k] = 1;
					}
					else if(!eliminated[k])
					{
						votes[k] = 0;
					}
				}
				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;
}

thanks in advanced !
really appreciating your interest

[brianfry713]

Try solving it without using floating point.