Wednesday, April 30, 2003
ZorbaTHut was dominant in SRM 144, outscoring second place SnapDragon by almost 150 points - without the aid of any challenges. His strong performance gave him 116 points, and moved him up to 6th overall. SnapDragon came in second as the only other coder with 3 correct submissions. Overall, the problems were a little more difficult than usual, and were scored as such. In division 2, bladerunner, a new comer, led the pack by an equally large margin, beating second place jorend by almost 200 points. Congrats to ZorbaTHut and bladerunner.
Used as: Division-II, Level 1:
This problem could be solved pretty simply with a couple of division and modulus operators. The important thing here was to understand the % operator which gives you the remainder from a division. Thus, you could find <H>, <M> and <S> easily as follow:
int h = seconds/3600; int m = (seconds%3600)/60; int s = seconds%60;Binary Code
Used as: Division-II, Level 2:
Used as: Division-I, Level 1:
This problem was a little bit tricky at first glance. However, the examples in the problem statement gave you a good idea of how to do it. Once you make an assumption about the value of the first bit, you can then determine the value of the next bit, and so one until you get to the last bit. If, while you are going along, you find that you would have to set a bit to a number other than 0 or 1 to make the sum work out, then the assumption you made at the beginning has caused some sort of inconsistency, and leads to the answer "NONE". One tricky thing is that, when you get to the last bit, you have to look ahead and see what the next bit would have to be for the given encoding to occur. Since the last bit is off the end of the string, it has to be 0. If the encoding requires it to be anything else, you again have an inconsistency. Most people who failed seemed to make mistakes either with the single digit case, or in checking the end digit.PowerOutage
Used as: Division-II, Level 3:
In this problem we are given series of tunnels, which can be represented as a rooted tree, and are asked to find the total path length required to visit every node at least once, starting from node 0. The way to solve this problem is to think about how you would do it if you had to. First, you would go down one tunnel leading away from tunnel 0, and then go down all of the tunnels leading away from that one. In other words, you should completely explore a subtree before returning to the root to explore another subtree. If you think about this a little, and draw some trees, you see that every edge gets traversed exactly once. However, at the end, you don't have to go back to the root. Once you have visited all of the nodes, you are done. So, it makes sense to end your search at the node that is farthest away from the root. That way, you have to traverse all of the edges from the root to that node one less time. Thus, the total distance turns out to be (2 * sum of all edge weights) - (length of the longest path starting at the root).Lottery
Used as: Division-I, Level 2:
There are a couple of different ways to solve this. One of them involves
dynamic programming, and the other involves combinatorics. I will describe the
combinatoric approach, which is simpler to code, if you can come up with it.
Used as: Division-I, Level 3:
A fairly well known theorem states that to go over all of the edges in a connected graph requires numOfOddVertices/2 total paths. This is related to Euler's famous theorem that a graph has an Eulerian walk if and only if the number of odd vertices is less than or equal to 2. So, now how does this apply? Well, if we look at the drawing we are trying to make as a graph, where intersections and endpoints are vertices, and segments are edges, then we are trying to go over all of the edges in this graph n times. This is the same as having n edges between each pair of adjacent vertices. So, once we construct the graph, we should first split it into a number of connected components, and then compute the number of odd vertices in each component. The total number of paths required will be the sum over all components(min(1,numberOfOddVerticesInComponent/2)). Since we get to start anywhere, the actual result will be one less than this. Finding the connected components and the number of odd vertices is pretty simple graph theory and can be done with a depth first search. The tricky part is building the graph. There are probably many ways to do this, and I'll just describe my approach: