Match Editorial

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

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.

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.

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)

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.

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:

......................
.qqwweerrttyyuuiioopp.
..aassddffgghhjjkkll..
...zzxxccvvbbnnmm.....
......          ......
......................

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.

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
9 
a10
 a7
a10
 a5
a10
 a3
a10
 a1
a10
 a1
8 
 a9
 a6
 a7
 a4
 a5
 a2
 a3
 b1
 a1
 d1
7 
 a8
 a5
 a6
 a3
 a4
 a1
 a2
 a1
 b1
 a1
6 
 a7
 a4
 a5
 a2
 a3
 b1
 a1
 d1
 a1
 f1
5 
 a6
 a3
 a4
 a1
 a2
 a1
 b1
 a1
 d1
 a1
4 
 a5
 a2
 a3
 b1
 a1
 d1
 a1
 f1
 a1
 h1
3 
 a4
 a1
 a2
 a1
 b1
 a1
 d1
 a1
 f1
 a1
2 
 a3
 j1
 j1
 j1
 j1
 j1
 j1
 j1
 j1
 j1
1 
 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 10¹² 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.