JOIN
 Match Editorials
TCHS SRM 41
Saturday, 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 radix-based 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 radix-based 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 radix-based 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 radixk <= n < radixk+1, the length of radix-based 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,

1. if this cell is marked as removed, does nothing and quits.
2. marks this cell as removed; if the cell is colored, increases the score.
3. 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] (0-based indices), adjacent cells will be (i,j-1), (i,j+1) in the same row, and either (i-1,j-1) 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