262  Transferable Voting
Moderator: Board moderators
262  Transferable Voting
This seemingly simple problem turned out to be really troublesome for me. Judging from the acceptrate, 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?
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?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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).
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).

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
Finally I got Accepted on this problem and I take one of the last places in ranking
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 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 mutiinput problem, so I follow the old description with the addition of the one remaining candidate...
Can someone verify this sample?
My WA program gives:
Some other critical input/output would be welcome too.
I guess they messed it up when translating it from a mutiinput 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
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.
Your I/O is correct, both in format and content.
Another case:
Output:
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
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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 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...
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...
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.Problem wrote:If, after the elimination, there are any remaining candidates, the firstpreference votes are counted again to determine a winner.
Your solution description sounds correct as well, so I'm not sure what the problem is.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 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>votes1);i++) for(j=i+1;j<b>votes;j++) if(b>vote==b>vote[j]) break;
b>valid=((i==b>votes1)&&(j==b>votes));
}
[/c]
Thanks in advance.
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>votes1);i++) for(j=i+1;j<b>votes;j++) if(b>vote==b>vote[j]) break;
b>valid=((i==b>votes1)&&(j==b>votes));
}
[/c]
Thanks in advance.
Last edited by little joey on Sun Feb 29, 2004 9:46 am, edited 1 time in total.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Try the following test case...
Input:
Output:
Hope it works.
Input:
Code: Select all
1
1. Chubby Checker
2. Kid Creole
3. Rest of the coconuts
1
1
1
2
Code: Select all
The winner of the election is Chubby Checker.
There were 4 valid ballots and 0 spoiled ballots.
Ami ekhono shopno dekhi...
HomePage
HomePage
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 lowerpreference noneliminated 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...
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 lowerpreference noneliminated 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...