Get Time
statistics_w  Match Editorial
SRM 375
Saturday, November 10, 2007

Match summary

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.

The Problems

MixtureDensity rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 473 / 517 (91.49%)
Success Rate 414 / 473 (87.53%)
High Score alabastern for 248.98 points (1 mins 49 secs)
Average Score 195.54 (for 414 correct submissions)

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.

DukeOnChessBoard rate it discuss it
Used as: Division Two - Level Two:
Value 550
Submission Rate 197 / 517 (38.10%)
Success Rate 178 / 197 (90.36%)
High Score Alex_KPR for 486.26 points (10 mins 34 secs)
Average Score 297.62 (for 178 correct submissions)

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:

  • Finish his path here.
  • Move to a neighbor cell.

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.

DivisibleByDigits rate it discuss it
Used as: Division Two - Level Three:
Value 950
Submission Rate 142 / 517 (27.47%)
Success Rate 83 / 142 (58.45%)
High Score vot for 868.53 points (8 mins 52 secs)
Average Score 586.40 (for 83 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 387 / 421 (91.92%)
Success Rate 323 / 387 (83.46%)
High Score Petr for 247.33 points (2 mins 57 secs)
Average Score 197.40 (for 323 correct submissions)

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.

A solution by kia was the very first submit in this match. It shows an implementation of the algorithm described above.

DateFieldCorrection rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 302 / 421 (71.73%)
Success Rate 171 / 302 (56.62%)
High Score krijgertje for 445.55 points (10 mins 11 secs)
Average Score 265.89 (for 171 correct submissions)

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:

......          ......
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 rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 18 / 421 (4.28%)
Success Rate 8 / 18 (44.44%)
High Score Petr for 757.48 points (17 mins 16 secs)
Average Score 467.27 (for 8 correct submissions)

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.

10  a9 a10 a7 a10 a5 a10 a3 a10 a1 a10
a10 a7 a10 a5 a10 a3 a10 a1 a10 a1
a9 a6 a7 a4 a5 a2 a3 b1 a1 d1
a8 a5 a6 a3 a4 a1 a2 a1 b1 a1
a7 a4 a5 a2 a3 b1 a1 d1 a1 f1
a6 a3 a4 a1 a2 a1 b1 a1 d1 a1
a5 a2 a3 b1 a1 d1 a1 f1 a1 h1
a4 a1 a2 a1 b1 a1 d1 a1 f1 a1
a3 j1 j1 j1 j1 j1 j1 j1 j1 j1
a2 a1 b1 a1 d1 a1 f1 a1 h1 a1
a b c d e f g h i j

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.

Petr showed a terrific performance, solving this hard problem extraordinarily fast, which gave him time to find and to fix a bug in his 500-pointer.

By darnley
TopCoder Member