## 262 - Transferable Voting

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
The problem states..
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.)
This part is really confusing. As I understood..

Suppose there are three candidates numbered from 1 to 3 and the ballots are described as

Code: Select all

``````1 3 2
2
1 2
2 3
3``````
After counting the ballots you will find that..

Code: Select all

``````1. got 2 votes
3. got 1 vote and thus eliminated``````
Now there are only two candidates. As the problem states "Ballot papers on which an eliminated candidate is mentioned are effectively modified by deleting that candidate, thereby ``promoting" any lower-preference non-eliminated candidates.". Now updating the ballots, we get...

Code: Select all

``````1 2
2
1 2
2
// There is no candidate``````
This is the 'effectively deleting' part. So, we have deleted the eliminated candidate and listed the ballots so that the preference of the candidates is same (before deleting).

Now look at the 5th ballot. Its empty. As the problem states (A valid ballot from which all candidates have been eliminated remains a valid ballot.), so the 5th ballot is also valid. But it is empty so, it will not be counted.

And for the input

Code: Select all

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

1
1
2
3 ``````
After counting ballots you get..

Code: Select all

``````1. got 2 votes
2. got 1 vote
3. got 1 vote``````
None gets majority so, 2 and 3 will be eliminated and the ballot configuration becomes..

Code: Select all

``````1
1
empty
empty``````
Empty votes are valid but not counted. So the winner is 1.

Remember that...

1. In a valid ballot the occurrance of any number is at most 1. If more than 1 then the ballot is not valid. So a ballot like 1 2 1 1 is invalid.
2. Suppose there are 3 candidates numbered from 1 to 3. Then a ballot like 1 2 4 is invalid.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:
Thanks, Jan, i've edited my code but i'm still getting WA. i've already done that there is able to be as many empty lines as you wish, and i thought i processed all "dangerous" cases. all test cases from this topic give the same outputs as there but i'm getting WA, WA & WA :'(

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:
The list of ballots is terminated by an end-of-file.
what does it mean? i think it means that after each list of ballots i can meet EOF? i'm in complete confusion

Project
New poster
Posts: 12
Joined: Tue Jul 19, 2005 9:29 am
Margarita wrote:
The list of ballots is terminated by an end-of-file.
what does it mean? i think it means that after each list of ballots i can meet EOF? i'm in complete confusion
It means that in last test there is no empty line after ballots list.

Everything said above is checked and correct:
1. A candidates list is like "1. ", "2. ", ..., "n. " (n<=20).
2. Ballots list can be EMPTY, but there are at list one candidate.
3. You should consider as spoiled ballots only that which contain doubled choise of one candidate or there is not-existed one in the list.
4. You should stop when:
a) one candidate left, he is a winner;
b) someone has more (>) than n/2. voices, where n is a number of valid ballots at the beginning of the voting process; he is a winner;
c) all candidates were eliminated; an indecisive situation.
5. There are blank lines after:
a) total number of test inputs;
b) each candidates list;
c) each ballots list except of last test input.
6. All sample test inputs in this thread are correct.
7. Check if you had initialized all queues with candidates prerogatives at the start of each test [all 1000 ballots should be empty on startup].
8. Look at other global variables. They should be correct before reading stage.
9. Look at your code extensively. There are must be unseen before bugs.

Best luck!

Darth
New poster
Posts: 1
Joined: Sun Feb 26, 2006 8:03 pm
Finally got Accepted. Thanks everyone

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:
Thanks for help!!! We've with Darth got accepted

nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:

### 262 Transferable Voting

One thing should have been but not stated in the problem description that there are invalid candidate numbers in the ballots and ballots containing invalid candidates should be treated as spoiled.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 262 - Transferable Voting

Weird input again, please refer to Project's post above.