SRM 696, D2, 250-Pointer (Ropestring)

James S. Plank

Tue Sep 6 00:32:52 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: August, 2016
Competitors who opened the problem: 242
Competitors who submitted a solution: 211
Number of correct solutions: 151
Accuracy (percentage correct vs those who opened): 62.40
Average Correct Time: 25 minutes, 20 seconds.

To me, the easy part here was articulating a solution. The hard part was rendering that solution into code.

You need to have all of the even "ropes" before the odd "ropes," and because you want your answer to be lexicographically smallest, you want to order the even strings from biggest to smallest, and then the odd strings from biggest to smallest. You also only want one dot between each rope, again, because you want the lexicographically smallest string. All of the remaining dots go at the end of the string.

To solve the problem, I created two multisets.

E holds all of the lengths of even ropes.
O holds all of the lengths of odd ropes.

I also had an integer called dots, which counted the dots, although in the end, I didn't need it.

Task 1 - counting the sizes of the ropes

This is the kind of small problem that often trips students up. The first thing that I did was to add a dot to the end of the string. This is a sentinel, and like all sentinels, it makes the programming less convoluted. Why? Because now you know that every rope will end with a dot. Without the sentinel, you may have ropes that end the string. Adding the dot simplifies your program. You just need to account for the fact that you have an extra dot when you craft your return value.

Here are two approaches to counting the sizes of the ropes. The first uses a single for loop, and a variable RL, which holds the length of the rope that you are currently looking at. RL starts at zero.

Now, you traverse the string, with a single for loop. When you see a dash, you increment RL. When you see a dot, you check RL to see if the dot ended a rope, and if it did, you add the rope length to the proper multiset. Set RL back to zero, increment dots, and move on.

With the second approach, you use a while loop that has an inner for loop. You again traverse the string with an integer, i, which will start at zero. When you encounter a dot, you increment dots and i, and go back to the top of the while loop. When you encounter a dash, you enter a for loop that counts the length of the rope (using i), store that in the proper multiset, and go back to the top of the while loop.

Both approaches work -- personally, I find the first approach cleaner, but the second is fine too. Note how the sentinel makes both approaches easier.

(You can also use vectors instead of sets, and then sort them with the sort() method. That's how I originally solved the problem. I think that the multisets are easier.)

Task 2: Creating the return string

For this task, you are going to do the following:

Traverse E from high to low, adding the proper rope strings to the return string. If a rope string is not the very first one, put a dot before it.
Traverse O from high to low, adding the proper rope strings to the return string. If a rope string is not the very first one, put a dot before it.
Fill in the rest of the dots. Remember to account for the sentinel.

That works, and that's how I did it, but there is a simpler way:

Create your return string to be the proper size (which is the size of the original string), and have it be all dots.
Set an index i to zero.
Traverse E from high to low, setting dots to dashes, starting at i. Increment i by the rope length plus 1.
Traverse O from high to low, setting dots to dashes, starting at i. Increment i by the rope length plus 1.
You're done! This is simpler because you don't have to worry about inserting dots -- since you initialized the string to be all dots, you only have to worry about changing dots to dashes.