Monday, June 21, 2004 Match summary
The turnout for SRM 200 was high as competitors all hoped to get lucky and win some TopCoder Gear. Of the 78 members who competed is SRM 1, jonmac was the only one (that I noticed) who was on hand for the 200^{th} SRM. Thanks to all the TC staff and all the members for making TopCoder such a fun place to learn and compete for the past 3 years. I know that I, for one, have learned a lot from my experiences at TopCoder.
The ProblemsNoOrderOfOperationsUsed as: Division Two  Level One:
Most people were able to solve this problem without much trouble. Since we aren't worrying about order of operations, we can just iterate over the numbers in the string. This is particularly easy because all of the numbers contain only a single digit, and hence occur every two characters. So, we'll start by initializing our return value to the integer value of the first character in the string. Then, we look at two characters at a time, performing the operation requested on the return value and the single digit, storing the result back in the return value. One thing to note is that the best way to convert a single character to an integer is to subtract '0' from it. See CSAddict's solution for a nice clean implementation of this. GravityBombUsed as: Division Two  Level Two:
This problem was clearly inspired by Tetrinet, a multiplayer Tetris game that contains a number of special items, including a gravity block. If you're a Tetris fan and have never played, I suggest you find a friend to play with and download it. Anyhow, there are a couple of approaches to solving this problem. updated = true while(updated) updated = false search for a block over a space if(found) drop the block updated = true end endIf you wanted to be more efficient (which wasn't necessary), another approach was to continue to drop each block until it would drop no further. You could also be sure to start with blocks closer to the bottom so that you never had to drop a block more than once. A solution along these lines might look something like this: foreach (i = 0 to columns1) foreach (j = rows1 to 0) if(board_{j,i} == 'X') k = j+1 while(k < rows && board_{k,i} == '.') //As long as the character in row k is a '.', //move the 'X' from column k1 down one row. //Then increment k so that board_{k1,i} is always an 'X' board_{k1,i} = '.' board_{k,i} = 'X' k = k+1 end end end endWith both of the above solutions, you have to clear the complete lines at the end, which can be done in the same way, regardless of how you decide to drop the blocks: while(board_{rows1} is all 'X's) for(i = rows1 to 1) board_{i} = board_{i1} end set board_{0} to all '.'s endYet another approach, and the best one in my opinion, requires that we start by counting the number of 'X's are in each column. Once we have this information, we can easily compute the number of complete rows that will be formed as the minimum number of 'X's in a column. Thus, the number of remaining 'X's in each column will be equal to the number of 'X's that were originally in the column minus that minimum. If we know the total number of 'X's in each column, it's pretty straightforward to fill in the return with the appropriate 'X's and '.'s. Shavlugin used this approach to get the high score on the problem. WindowManager Used as: Division Two  Level Three: Used as: Division One  Level One:
It has been a long time since a div 1 easy was also a div 2 hard. In the past, this has usually been bad for one of the divisions, as the difficulty never seemed to quite work out. However, while this one was a bit on the hard side for a div 1 easy, it seemed to work out OK, as about 3/4 of div 1 coders submitted it successfully, and it was still hard enough for a div 2 hard. Used as: Division One  Level Two:
Factoring is generally a hard problem to solve for large numbers. Many encryption algorithms rely on this fact. However, a simple brute force algorithm can easily run in O(sqrt(N)), where N is the number being factored. In this problem, the constraints limit N to 10^{14}, which makes sqrt(N) only 10^{7}, plenty small for a brute force solution. Used as: Division One  Level Three:
Bipartite matching and max flow problems are always hard for people, and this problem was no exception. However, if you are familiar with bipartite matching, it is relatively straightforward, and the lexicographic requirement doesn't really add much complexity. If you aren't so familiar with bipartite matching, the next paragraph should provide a brief introduction. main(){ foreach (a in A){ set visited(b) = false for all b in B foreach (b in B){ if((a,b) is in E){ if(recurse(b)){ //If recurse(b) returns true, it means that b was either //free to begin with or else b was matched but has been //successfully unmatched. So, we can add (a,b) to the //matching and move on to the next a add (a,b) to matching break } } } } } //recurse returns true if b is either already unmatched or has been //successfully unmatched from whatever it was previously matched to recurse(b){ //If visited(b) is true, it means that we've already //check if b is free and it was already matched to //something and we couldn't figure out a way to unmatch it if(visited(b))return false visited(b) = true if((x,b) is in matching for some x){ //b is matched to x foreach(b' in B){ if(b!=b' && (x,b') is in E){ //let's try to match x to b' instead if(recurse(b')){ //If we get here, b' is free and we can match x to it remove (x,b) from matching add (x,b') to matching return true } } } return false }else{ //b was unmatched return true } }That was an admittedly brief introduction to a topic which is often covered in whole chapters of textbooks. If you are still unclear about how the matching algorithm works, or if you want a proof, there are a lot of good resources to be found with a simple search. But, back to the task at hand  how does matching apply to Graduations? To start with, we are going to translate our graduation requirements into the set B in the matching problem. For each element of requirements, we are going to make a number of nodes equal to the value of the leading integer in that element of requirements. Next we are going to transform our classes into the set A in the matching problem. For each class, we are going to add an element to set A. Finally, we'll create E. For each pair (a,b) in A x B, if a is present in the element of requirements corresponding to b, then we add (a,b) to E. Now, the goal is to find a matching such that every element of B is matched to some element of A. In other words, every requirement is fulfilled by some class. The nature of the matching problem ensures that no class may fulfill more than one requirement. Therefore, if we can find a matching whose size (the size of a matching is the number of (a,b) pairs in it) is equal to the size of B, we'll have satisfied every requirement. We start by trying to match each of the classes we've already taken (characters in classesTaken) to some requirement. Once we have matched as many of the classes that have been taken as possible, we move on to match classes not yet taken. In order to ensure the lexicographic requirement on the return, we try to match classes to requirements in lexicographic order by class, starting with the lowest. If we find a match for a class, we add that class to our return value, otherwise we don't. Since the matching algorithm only lets us assign one class to a requirement, we can be sure that we are not taking any extra classes. In the end, we need to check and make sure that we have indeed fulfilled all of the requirements (matched every element of B). If so, we simply return the classes we took as a string. Both of the successful submissions use the general approach described here. The biggest difference is that they both used a queue instead of recursion (which amounts to doing a BFS to find an augmenting path, instead of a DFS, for those of you who know about augmenting paths), and Eryx modified his matching a little bit so that he only made a single element for each requirement (it is the same conceptually, but it runs faster if you do it that way). The runtime for all this the way I've described it is O(requirements*100*classes^{2}) if you implement it well, though I'll leave the proof as an exercise. 
