JOIN
 Match Editorial
2002 TopCoder Invitational
Online Round #3

Wednesday, October 23, 2002

# The Problems

Billboard
Used as: Level 1
 Div-I 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 Div-II Level One problem.

To solve the problem one should allocate a string array (5 x a.length()*6-1) 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
 Div-I 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
 Div-I 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 floodfill-like algorithm, or a breadth-first 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