262 - Transferable Voting

Per · Post by **Per** » Wed Apr 16, 2003 10:51 pm

This seemingly simple problem turned out to be really troublesome for me. Judging from the accept-rate, it seems I'm not the only one having trouble.

So what's the catch? I've tried having testcases with no candidates, no ballots, no valid ballots, etc. It also seems that the input format for candidates is precisely like it should be and that the limits stated in the problem are actually followed. So what's the deal?

Dominik Michniewski · Post by **Dominik Michniewski** » Tue Sep 16, 2003 7:47 am

I've got the same problem as Per. Could anyone help us both ?

Best regrads
DM

Per · Post by **Per** » Tue Sep 16, 2003 8:01 am

I still haven't solved the problem, but using lots of submissions and assertions, this is what I have deduced:

1) The names are properly formatted. I.e the n:th name is of the form "n. XXXX" (and particularly: "2. A candidate" doesn't come before "1. Another candidate")

2) Bounds given on length of names, number of candidates, number of ballots, etc are all correct.

3) There are no empty valid ballots.

4) There is always at least one candidate.

5) There are cases with zero ballots.

6) There are cases with zero ballots and only one candidate.

The last observation is somewhat interesting, since one intuitive interpretation of such a voting is that the only candidate wins. However, if one follows the voting procedure strictly, it should be a draw. I have tried both, but get WA (again, and again, and again).

Per · Post by **Per** » Mon Oct 06, 2003 7:01 pm

The election protocol neglected to mention a very important thing:

If there only is one candidate left, he automatically wins, no matter how many votes he has.

(The problem statement is changed now)

Dominik Michniewski · Post by **Dominik Michniewski** » Fri Oct 24, 2003 3:45 pm

Thanks to Per for help in solving this problem

Finally I got Accepted on this problem and I take one of the last places in ranking

Best regards
DM

little joey · Post by **little joey** » Thu Feb 26, 2004 1:41 pm

The addition Per mentioned is now been removed again, and also there are a lot of extra empty lines in the sample input and output section of the problem description.
I guess they messed it up when translating it from a muti-input problem, so I follow the old description with the addition of the one remaining candidate...

Can someone verify this sample?

Code: Select all

6

1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts
4. Eddy Grant

1 2 3 4

1. Chubby Checker


1. Chubby Checker
2. Kid Creole


1. Chubby Checker

1

1. Chubby Checker

2

1. Chubby Checker

2
1

My WA program gives:

Code: Select all

The winner of the election is Chubby Checker.
There were 1 valid ballots and 0 spoiled ballots.

The winner of the election is Chubby Checker.
There were 0 valid ballots and 0 spoiled ballots.

Chubby Checker with 0 votes is eliminated.
Kid Creole with 0 votes is eliminated.
The election was indecisive.
There were 0 valid ballots and 0 spoiled ballots.

The winner of the election is Chubby Checker.
There were 1 valid ballots and 0 spoiled ballots.

The winner of the election is Chubby Checker.
There were 0 valid ballots and 1 spoiled ballots.

The winner of the election is Chubby Checker.
There were 1 valid ballots and 1 spoiled ballots.

Some other critical input/output would be welcome too.

Per · Post by **Per** » Fri Feb 27, 2004 9:58 am

Your I/O is correct, both in format and content.

Another case:

Code: Select all

2

1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts

1
1
2
3

1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts

1
1
2
2

Output:

Code: Select all

Kid Creole with 1 votes is eliminated.
Rest of the coconuts with 1 votes is eliminated.
The winner of the election is Chubby Checker.
There were 4 valid ballots and 0 spoiled ballots.

Rest of the coconuts with 0 votes is eliminated.
Chubby Checker with 2 votes is eliminated.
Kid Creole with 2 votes is eliminated.
The election was indecisive.
There were 4 valid ballots and 0 spoiled ballots.

little joey · Post by **little joey** » Fri Feb 27, 2004 2:02 pm

That's what my program gives

Am I right in my assumption that there can be more than one elimination rounds? Taking the description strictly, there is only one, but then the second sample would give a different output.

I keep on iterating elimination rounds until:
- one candidate is left; (s)he is declared the winner, no matter how many votes (s)he has.
- no candidate is left; the election is declared indecisive.
- one candidate has more than half of the original number of valid ballots (not the remaining number of valid ballots); (s)he is declared the winner.

Goin' mad over this problem...

Per · Post by **Per** » Sat Feb 28, 2004 11:09 am

Problem wrote:If, after the elimination, there are any remaining candidates, the first-preference votes are counted again to determine a winner.

I've always read this as saying that there can be multiple elimination rounds, but I guess it can be read as saying that after the first elims, there must be a winner. But the answer to your question is yes, there can be multiple elimination rounds.

Your solution description sounds correct as well, so I'm not sure what the problem is.

little joey · Post by **little joey** » Sat Feb 28, 2004 2:41 pm

Well, something must be wrong...
I'll temporarily publish my code, maybe someone can find something.

[c] /* CODE REMOVED */

if(b->votes>1){
/* look for doubles */
for(i=0;i<(b->votes-1);i++) for(j=i+1;j<b->votes;j++) if(b->vote==b->vote[j]) break;
b->valid=((i==b->votes-1)&&(j==b->votes));
}
[/c]

Thanks in advance.

Per · Post by **Per** » Sat Feb 28, 2004 6:32 pm

A small thing that seems rather fishy is your check for doubles. You check that a vote is valid by checking that the loops complete, yet you only break out of the first loop when you find an invalid ballot. So if I'm not mistaken, you'll probably miss that votes like "1 1 2 3" are invalid?

little joey · Post by **little joey** » Sun Feb 29, 2004 9:49 am

Thank you very much, Per, that was exactly the bug in my code. Must have been reading over it at least ten times without noticing... You're good!

SCATOM · Post by **SCATOM** » Tue Nov 23, 2004 4:28 pm

My program accpeted all of tests in this forum thread, but online judge system reply "Wrong Answer"

Writed somebody this problem in Java?

Jan · Post by **Jan** » Mon Dec 26, 2005 12:40 am

Try the following test case...

Input:

Code: Select all

1

1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts

1
1
1
2

Output:

Code: Select all

The winner of the election is Chubby Checker.
There were 4 valid ballots and 0 spoiled ballots.

Hope it works.

Margarita · Post by **Margarita** » Fri Feb 24, 2006 6:07 pm

What should be output on this test:
1

1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts

1
1
2
3

Per wrote that that the output should be

Kid Creole with 1 votes is eliminated.
Rest of the coconuts with 1 votes is eliminated.
The winner of the election is Chubby Checker.
There were 4 valid ballots and 0 spoiled ballots.

but in the description of the problem there is:
"Ballot papers on which an eliminated candidate is mentioned are effectively modified by deleting that candidate, thereby ``promoting" any lower-preference non-eliminated candidates. (A valid ballot from which all candidates have been eliminated remains a valid ballot.)"

so if we've eliminated all the candidates, ballot remains valid and this test should have such output:

Kid Creole with 1 votes is eliminated.
Rest of the coconuts with 1 votes is eliminated.
Chubby Checker with 2 votes is eliminated.
The election was indecisive.
There were 4 valid ballots and 0 spoiled ballots.

can anyone help me?
i'm getting WA...