SRM 696, D2, 250-Pointer (Ropestring)

James S. Plank

Tue Sep 6 00:32:52 EDT 2016
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.

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: That works, and that's how I did it, but there is a simpler way:

My Solution.