SRM 596, D2, 500-Pointer (ColorfulRoad)

James S. Plank

Sun Nov 3 11:08:44 EST 2013

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: 605b9e31fae6085a152817682d584363
answers.txt. MD5 hash: cec1d84ed35be2485a6eece1a982615e
Problem Given in Topcoder: November, 2013
Competitors who opened the problem: 1035
Competitors who submitted a solution: 660
Number of correct solutions: 616
Accuracy (percentage correct vs those who opened): 59.5%
Average Correct Time: 24 minutes, 29 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are on a road with N segments, each of which is colored either Red, Green or Blue.
The road is described a by string of length N, where each character is either 'R' for Red, 'G' for Green or 'B' for blue.
You start at segment 0, which is always Red.
At any point, may jump forward i segments, but it will take i*i units of energy to do so.
You can only jump to a Green segment from a Red segment.
You can only jump to a Blue segment from a Green segment.
You can only jump to a Red segment from a Blue segment.
You can only jump forward.
Return the minimum amount of energy that it takes for you to get from the first segment to the last, or -1 if you cannot do so.
The topcoder constrains the number of segments to be from 2 to 15. The problem becomes much more interesting if you make that number bigger -- certainly up to 1000 can be done easily, so that's what's done in my tests.sh file.

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.