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.
- 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.