349 - Transferable Voting (II)

[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.

[Ming Han]

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

Thanks.

[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]

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

[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]

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?

[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]

Thanks... there must be some careless mistake in my code then. I'll go check it out.

[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]

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.