
Match Editorial 
SRM 175Wednesday, 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 upandcomer 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: (hn+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):(i1);
}
return 12(12h%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 2^{n} 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.lengthret;
}
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)

One way to solve this problem is to think of the BinaryQuipu as a nondeterministic finite automaton (NFA), and then to reduce the NFA to a minimal DFA, and compute the number of knots that the DFA represents. I won't go in to very much detail about this solution, other that to say that it works, and is way more complicated than it needs to be. Instead, we should use SnapDragon's approach of recursion with memoization. We start be defining a recursive solution that takes a set of strings (sequences of knots). To make things a bit simpler, we'll replace the 'top knot' with an 's' by prepending 's' to each string. Then, the recursive method can always assume that the first character of each strings is the same. So, the first step will be to add the set to a cache. Then, we can trim off the first character of each string, which is tantamount to installing a single knot in our network. Then, we split the set of strings into two subsets  those that start with 'b' and those that start with 's'  and recursively calls itself with each nonempty subset. Each time we make a recursive call, we increment a counter to keep track of the number of knots we've added. So far, our code computes the number of knots used if we only merge the common prefixes (which can be done fairly simply with a number of other methods). The harder part is merging some of the suffixes to reduce the number of knots. We handle this only recursing on novel subsets. That is subsets that we have not yet seen. The idea behind this is that if we have already seen an identical set of strings, then we've already created a network of knots to represent this subset, and we can simply add a link to that network, rather than recreating the network. For example, consider the input {"ssb","sb"}. We first call recurse({"sssb","ssb"}), and increment our counter to 1 (this represents the 'top knot' which is handled be prepending 's' to each string). Since none of the strings start with 'b' after we trim off the initial characters, we only make one recursive call, recurse({"ssb","sb"}), and increment our counter to 2. Now, after we trim the initial characters, we have {"sb","b"} and lets say that we branch on the strings that start with 's' first, calling recurse({"sb"}), and incrementing our counter to 3. Then, we make one more call to recurse({"b"}), increment our counter to 4, and once we trim the initial 'b', no strings start with 's' or 'b', so we backtrack. Next, we would call recurse({"b"}), but looking in our cache, we see that we've already made this exact call, so we don't make it again, and we're done. Not making that call is equivalent to adding a link from the first 's' to the final 'b'. In pseudocode (see SnapDragon's solution for an implementation very similar to this, or John Dethridge's solution for a different, but horribly obfuscated solution):
int counter = 0;
set cache;
void recurse(set s){
cache.add(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'
s1.add(t)
if(s1!=null && !cache.contains(s1))recurse(s1);
set s2 = null;
foreach string t in s that starts with 'b'
s2.add(t)
if(s2!=null && !cache.contains(s2))recurse(s2);
}
As a challenge, either find an example where one could make a more compact nondeterministic Quipu (one with multiple branches to the same type of knot), or else prove that one does not exist.
By
lbackstrom
TopCoder Member