Match Editorials

Match summary

The second SRM of a new High School season attracted 78 competitiors, 21 of them newcomers. The first two problems were pretty straightforward and were solved by most contestants. The third problem required lots of careful coding, so there were much fewer submissions on it, and only 3 of them survived system testing. The challenge phase was quite uneventful, bringing down only 4 problems, so it was the third problem that defined the match winners. Zuza won the match by more then 200 points due to his fastest submission on the third problem. tourist took second place thanks to one successful challenge, and miroslavb finished third.

The Problems

Value	250
Submission Rate	63 / 73 (86.30%)
Success Rate	62 / 63 (98.41%)
High Score	petar1 for 249.31 points (1 mins 29 secs)
Average Score	224.11 (for 62 correct submissions)

The problem is clearly a parsing one: after the numbers of votes from each group and the quote text are extracted from each line of the input, the task comes to calculating the total numbers of votes for each quote and returning the quote with the most total votes. See petar1's solution in C++, and Quelloquialism's solution in Java as samples.

Value	450
Submission Rate	59 / 73 (80.82%)
Success Rate	52 / 59 (88.14%)
High Score	DaViDeX for 447.22 points (2 mins 14 secs)
Average Score	401.21 (for 52 correct submissions)

The solution is quite straightforward: you need to perform the given transformation over each number in the input, and compare the results. As for the transformation itself, you need to convert the number to an array of its digits (stored as distinct numbers or as characters), sort it and convert the resulting array back to number (see miroslavb's solution).

Value	1100
Submission Rate	8 / 73 (10.96%)
Success Rate	3 / 8 (37.50%)
High Score	Zuza for 713.11 points (23 mins 50 secs)
Average Score	553.09 (for 3 correct submissions)

The idea of the solution is to calculate distances between each pair of honey cells and shortest distances from each honey cell to one of the boundary cells, and then to find the sequence of visiting exactly n of the honey cells that can be done with the least number of moves.

Distances calculation can be done using breadth-first search. Let's have a closer look at the finding the shortest distance between a pair of honey cells (finding the shortest distance between a honey cell and a boundary cell can be done in a similar way).

First, add the starting honey cell to a queue of cells to be processed with zero distance to the starting cell. When processing the current cell of the queue, check every cell which is adjacent to it, is not filled with wax and was not visited before. If it is the target cell, end the search, otherwise add it to the end of the queue with distance to the starting cell equal to (distance from the current cell + 1). Finally, mark the current cell as visited before and continue to the next cell of the queue. Thus, the first time you get to the target cell will give you the shortest distance to it from the starting cell.

You can read more about BFS in this tutorial.

The only trick in applying BFS to this problem was to define which cells are adjacent to the current one. For a cell in row i and column j adjacent cells will be: (i-1,j), (i+1,j), (i,j-1), (i,j+1) and (i-1.j-1), (i-1,j+1) for even columns or (i+1,j-1), (i+1,j+1) for odd columns.

As for the search of the best honey cells sequence, the constraints were chosen so that an exhaustive search of all possible sequences without any optimizations will run in time. See miroslavb's solution for an implementation of this approach.