Match Editorial

The Problems

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)

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.

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.