SRM 596, D2, 500-Pointer (ColorfulRoad)

James S. Plank

Sun Nov 3 11:08:44 EST 2013

In case Topcoder's servers are down

Here is a summary of the problem:

The examples

#   Roads            Answer  Comments
-  ----------------- ------  --------
0  "RGGGB"              8    0 to 2 to 4: 2*2 + 2*2 = 8.
1  "RGBRGBRGB"          8    8 Steps of length 1
2  "RBBGGGRR"          -1    Impossible
3  "RBRRBGGGBBBBR"     50
4  "RG"                 1
5  "RBRGBGBGGBGRGGG"   52

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

Please look in: http://web.eecs.utk.edu/~jplank/plank/classes/cs302/Topcoder/ColorfulRoad.html.

This would be a good practice problem for Dijkstra's Algorithm, Dynamic Programming, Topological Sort, or frankly, even Enumeration! The hints above use Dijkstra's Algorithm.