
Match Editorials 
TCHS SRM 41Saturday, October 13, 2007
Match summary
The match attracted 102 registrants, 37 of them newcomers, and had a rather high success rate,
with 11 people getting all three problems correct.
spencer
won the match with impressive 6 successful challenges.
henryy
took the second place due to the fastest submission on Hard, and a newcomer
ngg
finished third.
The Problems
MajorityElement
Used as: Division One  Level One:
Value

250

Submission Rate

79 / 85 (92.94%)

Success Rate

63 / 79 (79.75%)

High Score

spencer for 249.54 points (1 mins 13 secs)

Average Score

233.00 (for 63 correct submissions)

For each element of the array, you need to count the number of elements in the array
which are equal to it (including the element itself), and compare this number to
half of the array's size. Since there can be at most one majority element, you can return
the first element for which the number of its occurencies exceeds half of the array's size.
This problem had a surprisingly low success rate, with most failed solutions
ignoring corner cases like majority element being equal to 0 or 1000.
See
rogrog's
solution
for a sample implementation.
NotationLength
Used as: Division One  Level Two:
Value

500

Submission Rate

71 / 85 (83.53%)

Success Rate

58 / 71 (81.69%)

High Score

Quelloquialism for 494.73 points (2 mins 56 secs)

Average Score

387.40 (for 58 correct submissions)

The low constraints allowed this problem to be solved in a very straightforward
way: loop through numbers from low to high,
write each number in radixbased notation and in decimal notation, calculate the notation lengths' ratio,
and find the average of ratios.
However, this approach was successfully implemented by the only competitor, who used library method
java.util.Integer.toString(n, radix)
that returns the radixbased notation of n as a String
(see
Quelloquialism's
solution
). Note that using similar method of class java.math.BigInteger results in time limit
(see
smel's
solution
).
Most solutions had implemented analytic approaches.
The essential thing to notice was that we need only the notation length,
not the notation itself, therefore we don't need string notations.
The length of the radixbased notation of n can be calculated in the following way:
divide n by radix while n is positive; the answer will be the number of divisions done
(see
LiuKang's
solution
).
Another way to get this length is to compare n to the consecutive powers of radix:
if radix^{k} <= n < radix^{k+1},
the length of radixbased notation of n is k
(see
henryy's
solution
for a version of this approach).
TrianglesBoard
Used as: Division One  Level Three:
Value

1000

Submission Rate

31 / 85 (36.47%)

Success Rate

12 / 31 (38.71%)

High Score

henryy for 755.81 points (17 mins 22 secs)

Average Score

502.94 (for 12 correct submissions)

To solve this problem, you need to implement the recursive process of removing
cells as described in the statement, starting from each cell in turn,
choose the starting cell which results in the maximal score, and return this score.
Let's have a closer look at the implementation.
The main part of the solution is the function which, given the coordinates
of the cell at the board,
 if this cell is marked as removed, does nothing and quits.
 marks this cell as removed; if the cell is colored, increases the score.
 if the cell is 'A', calls itself for all adjacent cells;
if the cell is colored, calls itself only for adjacent cells of same color;
if the cell is 'R', calls itself for all other cells in the row.
For a cell represented with
board[i][j] (0based indices), adjacent cells will be
(i,j1), (i,j+1) in the same row, and either (i1,j1) in the row above (for odd j),
or (i+1,j+1) in the row below (for even j).
See
henryy's
solution
for a sample implementation.
By
Nickolas TopCoder Member