Saturday, November 10, 2007 Match summarySRM 375 Division 1 victory was deserved by Petr who showed the fastest time on both 250pointer and 1000pointer. The fastest 500pointer was written by krijgertje who came in second. Two Ukrainians, Gluk and Vasyl[alphacom] were 3rd and 4th respectively, and those are the only four coders who solved all three problems correctly. vot won the Division 2, thanks to his fast code in hard problem, leaving a noticeable gap between him and secondplaced happyFounder. A newcomer averza came in third, proceeding to Division 1 and becoming also the third among all coders from Latvia. The ProblemsMixtureDensityUsed as: Division Two  Level One:
Div 2 coders were asked to calculate the density of some mixture, given masses and volumes of all its ingredients. No trick here, all they had to do was to find the mass of the mixture (as the sum of ingredient masses) and the volume (as the sum of ingredient volumes). The answer then is mass divided by volume. It was also necessary to parse the given strings accurately. ioffe managed to do it fast and neatly. DukeOnChessBoardUsed as: Division Two  Level Two:
As the size of the board was no more than 8 (compare it to 1,000,000 in DukeOnLargeChessBoard problem given to Div 1 competitors), a greedy simulation was the best choice. Consider a duke standing is some cell. He has a few options:
In order to make the path lexicographically greater, it is always favorable to make a move rather than to finish the path. So if there is a neighbor cell that hasn't been visited yet, a move is to be done. What if there are several unvisited neighbors? In this case (to make the path lexicographically greater) the move right is the most preferred one, the second preferred is the move upwards, then downwards and the least preferred one is the move to the left. Continue making such moves greedily until there are no unvisited neighboring cells left. This will be your lexicographically greatest path. avayvod's code illustrates what was asked for in this problem. DivisibleByDigitsUsed as: Division Two  Level Three: Used as: Division One  Level One:
Let's call a number good if it starts with n and is divisible by every nonzero digit of n. (The task was to find the smallest good integer). Consider a number that starts with n and is divisible by lcm(1, 2, ..., 9)=2520. This number is divisible by all nonzero digits 1 through 9, obviously including the nonzero digits of n. Therefore, this number is good. Now note that there is such number somewhere between n0000 and n2519, inclusive. Therefore, the smallest good number is either that one or even smaller. Thus, in order to find the smallest good number, one has to check the following candidates: n, n0..n9, n00..n99, n000..n999 and n0000..n2519. The first number among them that is divisible by every nonzero digit of n is the answer. A solution by kia was the very first submit in this match. It shows an implementation of the algorithm described above. DateFieldCorrectionUsed as: Division One  Level Two:
Since there are only 366 days in the leap year, it was OK to check all the dates and to calculate the distance from input for each one. In order to calculate those distances, it was quite handy to have a table of penalties, which shows the penalty of mistyping i for j for any two valid characters i and j. Now, this table is nothing else than a table of shortest distances in the given keyboard graph from each vertex to each vertex. This problem is called the allpairs shortest path problem, and the easiest algorithm to calculate this table is the FloydWarshall algorithm described in a tutorial on graphs in TopCoder Educational Content section. But before running any algorithms from graph theory, it was necessary to code the graph itself. There were lots of ways to do it, one more tangled than another. A very beautiful one was invented by Pawa after the SRM (unfortunately for him). His idea is to consider the following table: ...................... .qqwweerrttyyuuiioopp. ..aassddffgghhjjkkll.. ...zzxxccvvbbnnmm..... ...... ...... ......................Two keys are neighbors on the keyboard if and only if there is a pair of adjacent cells in this table containing these two keys. This property makes the implementation of the keyboard graph an easy exercise. Another approach was to use the natural coordinate system of the keyboard. The distance between two keys can be calculated using their coordinates on the keyboard. However, this calculation process is rather tricky, for example, Petr had to resubmit his solution. DukeOnLargeChessBoardUsed as: Division One  Level Three:
Unlike the DukeOnChessBoard problem given to Division 2 coders, the constraints in this problem didn't allow to use a greedy simulation to find the lexicographically greatest path of a duke. The supposed approach was the following: consider a much smaller board, say 10×10 instead of 1,000,000×1,000,000; find the lexicographically greatest path starting from each cell on the small board; note all the patterns and regularities; and extends these patterns to the original board. An ethical question arises: why is this extension from the small board to the large board correct? Well, the answer is that for each pattern observed on the small board, a corresponding pattern on the large board also takes place, an in each case a 5minute thinking will give you a proof of this fact. However, the SRM competitors didn't have the time to think over each single pattern, and all they could do was to believe that the natural extension works fine. A good approach was to check that the answers given by your code coincide with the answers found by greedy simulation on all boards of even sizes, say 4×4 through 50×50. Now, let's finally observe the discussed patterns on a 10×10 board. The standard chess notation is used on the picture to make things a bit simpler.
However, many of coders who solved this problem used another approach. They did implement the greedy walking of the duke (see DukeOnChessBoard above). However, unlike the Division 2 competitors they were unable to do it cell by cell: that would take 10^{12} iterations. The smart Div 1 guys noticed that when we leave certain column, the visited cells of this column form a continuous interval. Thus, all we need to store in memory are the 1,000,000 intervals that are visited in each column. Another lucky observation says that we will move from one column to another no more than approximately 2,000,000 times. Therefore, if each movement from one column to its neighbor is implemented to work fast, the overall simulation process will take reasonable time. Petr showed a terrific performance, solving this hard problem extraordinarily fast, which gave him time to find and to fix a bug in his 500pointer. 
