262 - Transferable Voting

[Jan]

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.

[Margarita]

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]

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]

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]

Finally got Accepted. Thanks everyone

[Margarita]

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

[nealzane]

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]

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