SRM 183, D2, 550-Pointer (BridgeSort)

James S. Plank

Tue Feb 28 16:59:28 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2009
Competitors who opened the problem: 215
Competitors who submitted a solution: 153
Number of correct solutions: 118
Accuracy (percentage correct vs those who opened): 54.9%
Average Correct Time: 26 minutes, 50 seconds.

This is a sorting problem. Unfortunately, though, you have to somehow turn "cards" into something on which you can sort. Here are three approaches that you can take. I took the first of these when I solved the problem, but they are all valid solutions.

Solution #1: Convert Cards to Integers and Use a Map

My first step was to turn the string into a vector of two-character strings, so that I could simply focus on these. I used the substr() method to do this. For example the first string:

"HAH2H3C4D5ST" -- becomes -- { "HA", "H2", "H3", "C4", "D5", "ST" }.

Next, I took each string in the vector, and turned it into an integer. I used two helper strings for this:

string suit = "CDHS";
string rank = "23456789TJQKA";

I used the find() method of these strings to convert each card's suit into a number between 0 and 3, and each card's rank into a number between 0 and 12. I then multiplied the suit by 13 and added the rank. For example, the two of clubs is 0, the three of clubs is 1, and the two of diamonds is 13.

Next, I used a map whose keys were integers and whose vals were strings, and I inserted the integer/card into the map. At the end, I traversed the map and created the return string.

Solution #2: Enumerate the possible cards in order

Because the number of possible cards is so small (52), you can simply enumerate the cards in order, and then test to see if each card is in the string. To do this, I used the same two helper strings above, and then a doubly-nested for loop to create each card. I created each card as a string, and then used the find() method of strings to see if the card was in the original string. If so, I added the card to the return string.

As you can see, this solution requires no map and no sorting. It may not be the most efficient in the world, but the constraints of the problem are so small that it doesn't matter.

Solution #3: Convert the cards to integers, sort the integers, and convert back

This solution is similar to the first one, but you don't need to create a vector of strings or a map. Instead, you can traverse the input string two characters at a time, converting each pair of characters to an integer. Push each integer onto a vector, and then sort the vector. Then, traverse the vector, and convert each integer back to a suit character and a rank character, and add them to the return string.