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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Feb 25, 2006 12:42 am

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

Post by Margarita » Sun Feb 26, 2006 12:46 am

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:

Post by Margarita » Sun Feb 26, 2006 1:04 am

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

Post by Project » Sun Feb 26, 2006 10:08 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

Post by Darth » Sun Feb 26, 2006 8:05 pm

Finally got Accepted. Thanks everyone :)

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

Post by Margarita » Sat Mar 04, 2006 7:01 pm

Thanks for help!!! We've with Darth got accepted :)

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

262 Transferable Voting

Post by nealzane » Tue Mar 04, 2008 4:43 pm

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

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

Re: 262 - Transferable Voting

Post by metaphysis » Wed Jun 08, 2016 7:16 am

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

Post Reply

Return to “Volume 2 (200-299)”