
Match Editorial 
2002 TopCoder Invitational
Online Round #3Wednesday, October 23, 2002
The Problems
Billboard
Used as: Level 1
DivI

Value

250 points 
Submission Rate

250 / 253 (98.81%)

Success Rate

225 / 250 (90.00%)

High Score

venco for 247.10 points

Average Points

217.00

26 out of 251 coders who opened Billboard, received 0 points.
Reference implementation: SnapDragon
Implementation
I think the problem was extremely easy to solve for Round 3 Invitational. The difficulty level of this problem is more like DivII Level One problem.
To solve the problem one should allocate a string array (5 x a.length()*61) and fill this array with '.'
Go through all the letters of the desired string and find their mapping in the input array.
Once we have found a Y coordinate in the input array of the letter to be inserted, copy a 5x5 letter from the input array to the output buffer:
for( x = 0; x < 5; x++ )
for( y = 0; y < 5; y++ )
ret[y][6*i +x] = b[Y][6*y+x+2];
(where i is a desired string index)
Resort
Used as: Level 2
DivI

Value

500 points 
Submission Rate

213 / 253 (84.19%)

Success Rate

99 / 213 (46.48%)

High Score

ZorbaTHut for 439.44 points

Average Points

315.18

144 out of 243 coders who opened Resort, received 0 points.
Reference implementation: SnapDragon
Implementation
One of the ways to solve this problem is to build an adjacency matrix. All values of the matrix shall be initialized to a very high number. 0 node in the matrix is the base of the mountain. Let set the easy level as 0, medium as 1 and hard as 2 inside the adjacency matrix. Now for any three nodes on the mountain a, b and c assume a>b, b>c, a>c then select a max from a>b and b>c then compare that maximum value to a>c and select the minimum and assign to matrix value for a>c.
The outer loop should iterate 'b' nodes. Second nested loop shall iterate 'a' nodes and the third nested loop shall iterate 'c' nodes
for( b = 0; b < nam.size(); b++ )
for( a = 0; a < nam.size(); a++ )
for( c = 0; c < nam.size(); c++ )
path[a][c] <?= path[a][b] >? path[b][c];
Now the matrix is fully solved for all nodes and we just have to pick the
correct one to return.
RiverHill
Used as: Level 3
DivI

Value

900 points 
Submission Rate

119 / 253 (47.03%)

Success Rate

56 / 119 (47.06%)

High Score

ante for 749.62 points

Average Points

505.37

190 out of 246 coders who opened RiverHill, received 0 points.
Reference implementation: ante
Implementation
The brute force approach would work for this problem: try to start a river from all the locations on the map and select the location where river would cover the maximum area.
For every location one shall use a floodfilllike algorithm, or a breadthfirst search, on the map. One shall worry about the efficiency on the floodfill algorithm, since you might be doing it 1600 times on a 40x40 grid, but with some number of optimizations it shall work. Well, it did work for some of the successful submissions.
By
slavik
TopCoder Member