JOIN
 Match Editorial
SRM 175
Wednesday, December 17, 2003

Match summary

In a relatively hard SRM, SnapDragon marched to another SRM win, bringing his total to 26. In a rare appearance from down under, John Dethridge was a close second, less than 20 points behind. radeye was a distant third, followed by lars, and up-and-comer Eryx in his second SRM. In division 2, coders were faced with a tough hard problem (shared with division one's medium) and no one was able to solve it correctly. xmux, an Argentinian, won handily in his fifth SRM, beating second place telars and third place mthreat by over 100 points. The highest rated new comer was Jasko, who took seventh.

The Problems

ClockWalk
Used as: Division Two - Level One:
 Value 250 Submission Rate 179 / 196 (91.33%) Success Rate 102 / 179 (56.98%) High Score weimazhu for 249.83 points (0 mins 45 secs) Average Score 208.43 (for 102 correct submissions)

Modular arithmetic is the key to solving this problem with a high score. If you are at h on the clock, then moving forward n hours puts you at (h+n)%12. This isn't too hard to see, if you understand the % operator. Basically, what this does is subtract out all the extra twelves, so 13 becomes 1, and 26 becomes 2. The case where you go backwards is a bit trickier. If you get into negative values, %12 will no longer give you the correct position. However, if you add some large number that is divisible by 12, then subtract and finally do %12, then you will get the right result: (h-n+120)%12. Another solution is to just start at some large number that is divisible by 12, and not do any % operations until the end:

```   int h = 6000;
for(int i = 0; i<flips.length(); i++){
h += flips.charAt(i)=='h'?(i+1):(-i-1);
}
return 12-(12-h%12)%12;
```
Note that the fancy return statement returns h%12 if h%12 != 0 and 12 otherwise.

InstantRunoff
Used as: Division Two - Level Two:
 Value 550 Submission Rate 81 / 196 (41.33%) Success Rate 37 / 81 (45.68%) High Score xmux for 428.19 points (16 mins 8 secs) Average Score 262.82 (for 37 correct submissions)
Used as: Division One - Level One:
 Value 300 Submission Rate 150 / 160 (93.75%) Success Rate 85 / 150 (56.67%) High Score ZorbaTHut for 282.67 points (7 mins 7 secs) Average Score 207.71 (for 85 correct submissions)

There weren't any special cases, or advanced algorithms required to solve this problem, but it was still a relatively hard problem, requiring a fair bit of code. There are two ways that you could approach this. First, you could implement your code to follow the 3 steps in the problem statement. If you do it this way, then each iteration you start by looking at all of the ballots, and counting the number of ballots that each candidate is first on. Then, you find the uneliminated candidate(s) with the minimum number of votes, and remove them from each ballot. One important note is that you need to eliminate candidates with no votes first. Then, simply repeat until a candidate has greater than half of the vote. The other popular way to do it is to just mark which candidates are eliminated, as you eliminate them. Then, when you are tallying the votes, simply move down the ballot until you get to a candidate that hasn't been eliminated:

```   boolean[] elim = new boolean[26];
while(true){
int[] cnt = new int[26];
for(int i = 0; i<ballots.length; i++){
while(ballots[i].length()>0 && elim[ballots[i].charAt(0)-'A']){
ballots[i] = ballots[i].substring(1);
}
if(ballots[i].length()==0)return "";
cnt[ballots[i].charAt(0)-'A']++;
if(cnt[ballots[i].charAt(0)-'A']>ballots.length/2)return ""+ballots[i].charAt(0);
}
int min = 100;
for(int i = 0; i<26; i++) if(!elim[i]) min = Math.min(min,cnt[i]);
for(int i = 0; i<26; i++) if(cnt[i]==min) elim[i] = true;
}
```
Finally, I think its worth noting that this voting scheme also has cases where it seems not to elect the person who might make the most sense. Consider a case like {"ACDEFB","ACDEFB","ACDEFB","BCDEFA","BCDEFA","BCDEFA","CADEFB"}. In this case, A will win, but perhaps C would have been the better choice, since C was no worse than second on anyone's list, while A was dead last on 3 ballots.

Books
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 13 / 196 (6.63%) Success Rate 0 / 13 (0.00%) High Score Average Score No correct submissions
Used as: Division One - Level Two:
 Value 450 Submission Rate 63 / 160 (39.38%) Success Rate 39 / 63 (61.90%) High Score tjq for 436.62 points (5 mins 0 secs) Average Score 355.92 (for 39 correct submissions)

In past editorials, I've suggested that a limit of 20 should immediately set off a brute force alarm in your head. While this problem can be solved with brute force enumeration of subsets, a quicker solution to code runs in polynomial time. But, first the brute force solution. For each of the 2n subsets, consider removing that subset of books from the shelf. We can imagine removing the books and reinserting one at a time, but its easier to think of taking them all off at once, and it doesn't make any real difference. So, once we've got our subset of books off the shelf, we need to put them back in such a way that all of the books are ordered. If the books that we left on the shelf are in order, then this is easy - we just put each one where it belongs in the final ordering. If the books left on the shelf are not in order, then its clearly impossible. So, the solution is to take as few books off the shelf as possible, such that the books left on the shelf are in order. Put another way, you want to leave the largest subset of books on the shelf such that all the books left on the shelf are in order. Some of you may recognize this as the longest increasing subsequence (LIS) problem. A subsequence is exactly what we are looking for - the original sequence with zero or more element removed. Furthermore, we want one which is in increasing alphabetical order, and we want the longest one (largest subset). So, then the question becomes how to find the LIS. We can define the following recurrence (where max(null) = 0):
len[i] = 1+max(len[j] s.t. j<i && book[j] <= book[i])
In plain English, the length of the LIS ending at element i is either one plus the length of the LIS ending at j, where the book at j comes before i alphabetically, or else 1 if there is no such book. Implementing the recurrence is a textbook example of dynamic programming, and something that every TopCoder should probably familiarize themselves with:

```   public int sortMoves(String[] titles){
int[] dp = new int[titles.length];
int ret = 0;
for(int i = 0; i<titles.length; i++){
dp[i] = 1;
for(int j = 0; j<i; j++){
if(titles[i].compareTo(titles[j])>=0)
dp[i] = Math.max(dp[i],dp[j]+1);
}
ret = Math.max(ret,dp[i]);
}
return titles.length-ret;
}
```

BinaryQuipu
Used as: Division One - Level Three:
 Value 1000 Submission Rate 8 / 160 (5.00%) Success Rate 6 / 8 (75.00%) High Score SnapDragon for 797.44 points (15 mins 8 secs) Average Score 560.97 (for 6 correct submissions)

```int counter = 0;
set cache;
void recurse(set s){
counter++;
foreach string t in s
remove the first character of t
set s1 = null;
foreach string t in s that starts with 's'