349 - Transferable Voting (II)

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

349 - Transferable Voting (II)

Post by Ming Han »

I see nothing special with this problem, but I got wrong answer.

I tested with the test sets given and they are correct.

Are there any test cases which will not work for me?

Thank You.

Here is my source (if you want to take a look):

[cpp]// ACM Problem 349
// Transferable Voting (II)
// Done by Teh Ming Han

#include <stdio.h>

int main(){
int c,n,i,a,elec=0,b;

while(scanf("%d %d",&c,&n)==2){
if (c==0 && n==0) break;
elec++;

int nbad=0,ngood=0,good[100][5]={0};

for (i=1;i<=n;i++){
int check[5]={0};
int wrong=0;
int temp[5]={0};

for (a=1;a<=c;a++){ //read voters choices
scanf("%d",&temp[a]);
//check that vote is distinct and within candidates limit
if (check[temp[a]]==0 && temp[a]<=c) check[temp[a]]++;
else wrong = 1;
}
if (wrong==1) nbad++;
else{ //valid votes
ngood++;
for (a=1;a<=c;a++) good[ngood][a] = temp[a];
good[ngood][0] = c;
}
}

int towin,tie,can[5]={0};

towin = int(ngood/2)+1;

for (i=1;i<=c;i++){ //rounds
int max=0,votes[5]={0},nout=0,out[5]={0};
tie=0;
for (a=0;a<=5;a++) can[a]=0;

for (a=1;a<=ngood;a++){
votes[good[a][1]]++;
if (votes[good[a][1]]>max) max = votes[good[a][1]];
}

for (a=1;a<=c;a++){
if (votes[a]==max || votes[a]>=towin){
tie++;
can[tie] = a;
}else{
nout++;
out[nout] = a;
}
}

for (a=1;a<=ngood;a++)
for (b=1;b<=nout;b++)
if (good[a][1]==out){
good[a][0]--;
for (b=1;b<=good[a][0];b++) good[a] = good[a][b+1]; //advance votes
}

if (nout==0 || tie==1) break;
}

//output
printf("Election #%d\n",elec);
printf(" %d bad ballot(s)\n",nbad);
if (tie==1) printf(" Candidate %d is elected.\n",can[1]);
else{
printf(" The following candidates are tied:");
for (i=1;i<=tie;i++) printf(" %d",can);
printf("\n");
}
}
return 0;
}[/cpp]


Once again, thank you.
:: HanWorks ::

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Can anybody...

Post by Ming Han »

Can anybody please provide me with any test cases which will not work for my solution above??

Thanks.
:: HanWorks ::

jiayaoyu
New poster
Posts: 5
Joined: Fri Jun 14, 2002 1:10 am
Location: Lancaster.UK

If there were any invalid ballots, print an additional line

Post by jiayaoyu »

[c] //output
printf("Election #%d\n",elec);
printf(" %d bad ballot(s)\n",nbad);
[/c]

You should not output "0 bad ballot(s)" if there is none. [/cpp]

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Problem 349 - Transferable Voting (II)

Post by LawrenceT »

The problem description says that
If there had been several candidates with the fewest first choice votes, any of them, selected at random, could be selected for elimination.
Consider this input data:

Code: Select all

3 4
1 2 3
2 1 3
3 2 1
3 1 2
Candidate 1 has 1 vote, candidate 2 has 1 vote and candidate 3 has 2 votes. Since no one has an absolute majority, we can select either candidate 1 or candidate 2 for elimination. If we eliminate candidate 1, then candidate 2 will have 2 votes and candidate 3 still has 2 votes, and the output will be

Code: Select all

   The following candidates are tied: 2 3
If on the other hand, we choose to eliminate candidate 2, then candidate 1 will have 2 votes and candidate 3 will have 2 votes, and the output would be

Code: Select all

   The following candidates are tied: 1 3
According to the problem statement, both output are correct. However, there is no special correction program for this problem. Is there something I've missed out? Thanks :wink:
Those who stand for nothing, fall for anything.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

I agree. There are potentially many things that can go wrong with that line, but I don't think the judge has any test cases where two candidates have the same number of minimal votes.

Also, I doubt that it has any cases where something like 3 candidates are left and all 3 have the same number of votes. Is this considered a tie, or does someone get randomly thrown off the island?

If they ever decide to add these types of cases though, then they'll probably need a special correction judge, or at the least, have something like choose the lowest numbered candidate instead of random.

But for now, nothing like this seems to be in there.

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Post by LawrenceT »

Someone said on another post somewhere that if such a case (as above) appears, then u remove all of them, not just any one of them. Perhaps someone who has solved this problem would like to say something?
Those who stand for nothing, fall for anything.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

I already did, and I just removed the first one minimal count I found.

Code: Select all

if (count[candidate] < mincount)
    mincount = count[candidate]
    minindex = candidate
Got AC, so I highly doubt there are any such cases where two candidates have the same minimal vote count, or if so, that it doesn't matter how you get rid of them.

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Post by LawrenceT »

Thanks... there must be some careless mistake in my code then. I'll go check it out. :wink:
Those who stand for nothing, fall for anything.

Viktor
New poster
Posts: 1
Joined: Sat Mar 20, 2004 5:50 pm
Location: Spain, Barcelona, Gav

Transferable Voting (II) #349

Post by Viktor »

If we have 3 candidates and all of them have the same number of votes, are they tie or we have eliminate one of them at random? The maxim of candidates tied are 2 or they can be more?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

If we have 3 candidates and all of them have the same number of votes, are they tie or we have eliminate one of them at random?
My Accepted code returns all of them.
The maxim of candidates tied are 2 or they can be more?
I m not sure. But I believe it can be more than 2.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”