|
Match Editorial |
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 200th 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 problems in div 2 were pretty typical in terms of difficulty and a veteran TopCoder, hustler, took first with the help of 2 successful challenges. Division 1 had things a little harder, and few people where able to solve the medium problem, let alone the hard, though this was perhaps exacerbated a little by system issues. At the end of the night, SnapDragon pulled out the miracle upset, and won his umteenth SRM. Eryx was the only other coder to complete the hard problem successfully, but his medium failed, and so he ended up a distance second. tomek took third, leading some coders to wonder if his newfound wealth was leading him down a path of indulgence and vice, away from good wholesome TopCoding (he hasn't won an SRM since winning the TCCC).
The Problems
NoOrderOfOperations
Used as: Division Two - Level One:
Value 250 Submission Rate 187 / 217 (86.18%) Success Rate 174 / 187 (93.05%) High Score CSAddict for 246.92 points (3 mins 11 secs) Average Score 204.99 (for 174 correct submissions)
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.
GravityBomb
Used as: Division Two - Level Two:
Value 500 Submission Rate 145 / 217 (66.82%) Success Rate 90 / 145 (62.07%) High Score Shavlugin for 463.62 points (8 mins 5 secs) Average Score 330.31 (for 90 correct submissions)
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.
The first approach is to drop all of the blocks, on square at a time, until you can drop no more. While the order of your loops may vary, all of these solutions follow the same basic structure:
updated = true
while(updated)
updated = false
search for a block over a space
if(found)
drop the block
updated = true
end
end
If 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 columns-1)
foreach (j = rows-1 to 0)
if(boardj,i == 'X')
k = j+1
while(k < rows && boardk,i == '.')
//As long as the character in row k is a '.',
//move the 'X' from column k-1 down one row.
//Then increment k so that boardk-1,i is always an 'X'
boardk-1,i = '.'
boardk,i = 'X'
k = k+1
end
end
end
end
With 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(boardrows-1 is all 'X's)
for(i = rows-1 to 1)
boardi = boardi-1
end
set board0 to all '.'s
end
Yet 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:
Value 900 Submission Rate 53 / 217 (24.42%) Success Rate 28 / 53 (52.83%) High Score Javaholic for 622.20 points (21 mins 4 secs) Average Score 462.91 (for 28 correct submissions)
Value 300 Submission Rate 193 / 204 (94.61%) Success Rate 147 / 193 (76.17%) High Score Eryx for 282.86 points (7 mins 4 secs) Average Score 200.35 (for 147 correct submissions)
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.
A quick glance at the constraints should tip you off to the fact that iterating over every pixel in every window will time out. Though the display is at most 100x100, the windows are potentially huge, and doing anything that loops over tlv and tlh is bound to timeout. One way around this is to treat boxes which extend outside the display region as if they just barely extend outside the display region. In other words, if a window extends all the way to -1,000,000, we might as well treat it as if it extended only to -1.
Once we've done this, it's just a matter of looping over every pixel in each window and drawing them. legakis' solution uses this approach and is pretty easy to follow. schveiguy does something similar, and even has comments in his code. One neat trick that is used in both of these solutions to make the logic a little simpler is to fill in the '+' after the '-' and '|'. This makes our border test a little simpler, since we don't have to worry about the '+' as much. We simply write the '+' last and overwrite any '|' or '-' that we placed there before.
Another approach to this problem is to think about it not in terms of drawing boxes, but in terms of determining what color each pixel is. Hence, we iterate over every pixel in our 2-D array, and then iterate over the windows, in order and color the pixel appropriately. So, for example, you look at the pixel at (0,0) and then iterate over each window. If (0,0) falls within that window (which you can check by comparing (0,0) to the upper left and lower right coordinates of the window) then you color it appropriately. In the end, both approaches wind up looking pretty similar - the difference is mostly conceptual.
Used as: Division One - Level Two:
Value 500 Submission Rate 66 / 204 (32.35%) Success Rate 34 / 66 (51.52%) High Score SnapDragon for 419.70 points (12 mins 56 secs) Average Score 262.44 (for 34 correct submissions)
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 1014, which makes sqrt(N) only 107, plenty small for a brute force solution.
The first step to factoring a the number given to you is to convert it into a regular 64 bit integer, which we'll call N. This is much simpler than you might first think. If there is a 30 in the ones place (the last element of digits), that means that we would normally write down a 0 and carry the 3. But, why bother doing the carrying ourselves? Instead, just add 30 to your running total, and your CPU will take care of the carrying for you. Then, move on to the tens digit, and add 10 times its value to the running total, and so on. In this way, you can construct the value of the input with a single for loop.
Once you've done this, you should take the square root of the N, and write a loop that goes up to this square root. If our loop variable is i, then we have found a factor when N/i is an integer, or when N%i == 0. Once we've found a pair of factors, we simply reconstruct the no-carry product, and check that they match. The simplest way to do this is to multiply pairs of digits, just like we would on paper, and add up the result. To extract the jth digit (indexed from 0) from the right of a number, K, you can do K/10j%10 (assuming integer division). See SnapDragon's solution to see exactly how to do this.
Since we are sort of pushing the limits of the 8 second runtime, it is worth a bit of analysis. In the worst case, we might imagine that every one of the 107 numbers was a factor of N, and each one requires O(|digits|2) iterations. This puts us up on the order of 200,000,000 iterations, which is pretty likely to timeout. Luckily, however, most of the numbers we iterate over are not factors. In fact, we never find more than about 6000 factors, so the majority of our execution time is spent finding the factors, not checking them once they're found.
It is interesting to note that this problem was made considerably easier during development. Originally, the limit was as high as a 64 bit int would hold, and the brute force solution described here would stand no chance of passing. Jan_Kupiers' solution was the first one I saw that used an approach which would have worked with larger inputs. The basic idea is to use recursion with backtracking. You assign digits either from left to right or right to left (left to right seems to be faster), and check that things add up as you go. There are a number of optimizations you can make to break out of recursion early once you've assigned some digits which make finding a solution impossible.
Used as: Division One - Level Three:
Value 1000 Submission Rate 6 / 204 (2.94%) Success Rate 2 / 6 (33.33%) High Score SnapDragon for 705.30 points (20 mins 13 secs) Average Score 593.69 (for 2 correct submissions)
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.
Bipartite matching is a problem that comes up relatively often in some fields. In its simplest incarnation, you are given two sets, A and B, and a set of pairs E in (A x B). The task is then to find the largest subset of E such that no two pairs in the subset contain the same element. Another way to think about this is as a graph problem. You are given a bipartite graph and want to find the largest subset of edges such that no two edges share an endpoint.
The problem is closely related to the maximum flow problem, and there are many different ways to solve it. In this discussion I'll only go into the simplest of these methods, but if you are interested, a search on max flow or bipartite matching should yield many alternative, faster algorithms.
The basic idea behind this algorithm is to iterate over each element of set A and try to match it to some element in set B. A problem arises when we want to match an element of A, a1, to an element of B, b1, which is already matched to some other element of A, a2. In this case, we would like to unmatch b1 and a2 and match a2 to something else so that we can match a1 to b1. It is important that we find something else to match a2 to, otherwise we end up going around in circles.
Now, as you can imagine, we might want to match a2 to some b2, but find that b2 is already matched to a3 and so on. Hence, we must use either recursion, or a queue to explore a number of possibilities where we break some number of previous matches and then add new ones. The trick to making this run fast enough is to notice that, if we couldn't find something else to match a3 to in order to match a2 to b2, then we also won't be able to match a3 to something else in order to match a1 to b2. In other words, if breaking a matching doesn't work out once, it never will.
So, here is some matching pseudocode implementing this algorithm:
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.
