262 - Transferable Voting

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

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

262 - Transferable Voting

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

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
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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

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
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)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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.
Last edited by little joey on Sun Feb 29, 2004 9:46 am, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
New poster
Posts: 1
Joined: Tue Nov 23, 2004 4:22 pm

problem

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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.
Ami ekhono shopno dekhi...
HomePage

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:

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

Post Reply

Return to “Volume 2 (200-299)”