Saturday, November 10, 2007
SRM 375 Division 1 victory was deserved by Petr who showed the fastest time on both 250-pointer and 1000-pointer. The fastest 500-pointer 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 second-placed happyFounder. A newcomer averza came in third, proceeding to Division 1 and becoming also the third among all coders from Latvia.
Used 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.DukeOnChessBoard
Used 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.DivisibleByDigits
Used 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 non-zero 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 non-zero digits 1 through 9, obviously including the non-zero 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 non-zero digit of n is the answer.DateFieldCorrection
Used 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 all-pairs shortest path problem, and the easiest algorithm to calculate this table is the Floyd-Warshall 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.DukeOnLargeChessBoard
Used 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 5-minute 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 1012 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.