TopCoder Problem Statement - InstantRunoff |
Single Round Match 175 Round 1 - Division I, Level One |
Single Round Match 175 Round 1 - Division II, Level Two |
Determine the winner of a run off election by following the given rules.
1 1 import java.util.HashMap; 2 import java.util.HashSet; 3 import java.util.Map; 4 import java.util.Set; 5 6 public class InstantRunoff { 7 8 public String outcome(String candidates, String[] ballots) { 9 10 SetactiveCandidates = new HashSet<>(); 11 12 for (Character c : candidates.toCharArray()) { 13 activeCandidates.add(c); 14 } 15 16 while (true) { 17 18 // Count the number of first place votes for each candidate. 19 Map firstPlaceVotes = new HashMap<>(); 20 21 for (Character c : activeCandidates) { 22 firstPlaceVotes.put(c, 0); 23 } 24 25 for (String b : ballots) { 26 Character c; 27 28 c = b.charAt(0); 29 firstPlaceVotes.put(c, firstPlaceVotes.get(c) + 1); 30 } 31 32 // Do we have a clear winner? 33 for (Character c : activeCandidates) { 34 if (firstPlaceVotes.get(c) >= 35 ((ballots.length / 2) + 1)) { 36 return "" + c; 37 } 38 } 39 40 // Get the least first place votes 41 int minFirstPlaceVotes = Integer.MAX_VALUE; 42 43 for (Character c : activeCandidates) { 44 minFirstPlaceVotes = Math.min(minFirstPlaceVotes, 45 firstPlaceVotes.get(c)); 46 } 47 48 // Remove all candidates with the most last place votes 49 Set toRemove = new HashSet<>(); 50 for (Character c : activeCandidates) { 51 if (firstPlaceVotes.get(c) == minFirstPlaceVotes) 52 toRemove.add(c); 53 } 54 55 for (Character c : toRemove) { 56 activeCandidates.remove(c); 57 for (int i = 0; i < ballots.length; i++) { 58 ballots[i] = ballots[i].replaceFirst("" + c, ""); 59 } 60 } 61 62 if (activeCandidates.size() == 0) return ""; 63 } 64 65 } 66 67 }
This solution basically just follows the rules for the election as given in the problem statement. First, it creates a set of remaining candidates, then it enters a while loop which will not terminate until either a winner is found, or the set of remaining candidates becomes empty.
For each iteration of the loop, we count up the number of first place votes that each active candidate has received. If any of the candidates receives more than half of the possible votes, then they are declared the winner. Be careful in checking for a majority, the equation on lines 34 and 35 is easy to get wrong.
If there is no clear winner, then we look for the least number of first place votes, and remove any candidate that has that number of first place votes. Here, we remove those candidates from both the active candidates set, as well as from all the ballots. The easiest, although perhaps not the most efficient way is to do the replacement on line 58.
Finally, if there are no more active candidates, then we return the empty string.
No comments:
Post a Comment