|
Match Editorials |
TCHS SRM 34Tuesday, July 17, 2007
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
QuoteContest
Used as: Division One - Level One:
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.
NumbersGame
Used as: Division One - Level Two:
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).
ExploringHoneycombs
Used as: Division One - Level Three:
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.
By
Nickolas TopCoder Member