Knowing your libraries

Since I’ve started competing on TopCoder the lesson of knowing your libraries has been really hammered home for me. I was, of course, never against this, but often I would write my own functions to check alphanumeric values, parse integers and doubles, format output, and so forth. These don’t take that much time to write, but it’s still time away from writing the actual solution to the problem. Also, there’s always a chance you’ll make a typo or logic error, which can be costly.

I worried less about this when I use to compete in the ACM competitions because since it’s 5 hours, it’s almost more like a marathon than a sprint. However, on TopCoder, you generally know that the top people are going to solve all 3 problems, the only way to beat them is by being faster.

This can be true for the ACM competitions as well. This year at the Pacific Northwest Regional, something like 10 teams solved 7 problems, but only one of those teams qualified for the world finals. Because UBC was at the top of that heap, they are off to Stockholm for the finals.

Recently, in a practice competition on TopCoder I did a problem where you’re given a string and you need to return a vector containing two substrings of the original string. The first substring has to have the same number of a’s as the number of b’s in the second substring.

This is pretty easy to solve. I did something like the following:

vector getSubstrings(string str) {
  string x, y;
  x = str;

  while(1) {
    int c1 = count(x, 'a');
    int c2 = count(y, 'b');
 
    if(c1 == c2) break;

    y = x[x.size()-1] + y;
    x = x.substr(0, x.size()-1);
  }

  vector ans;
  ans.push_back(x);
  ans.push_back(y);

  return ans;
}

The key here is the “count” function. I actually wrote my own count function. Sure, it’s just a for loop, but it’s an extra 4-5 lines of code. There’s actually a count function built into the C++ STL. The fastest solution for this SRM used this function. With this function, my loop above could be something like this:

while(count(x.begin(), x.end(), 'a') 
        != count(y.begin(), y.end(), 'b')) { ... }

I scored something like 245 points on this problem, but by using a few language built-ins, I probably could have had 247 or 248. Oleg and I have actually had practices where we were separated by this small a margin, so every little bit helps.

Another library I’ve recently opened my eyes to is the C++ istringstream. It’s great for parsing input for certain types of problems. For example, if you had to read in a list of comma separated doubles like “-234.34, 324.234, 3243.22232,876.435”, you can quickly parse this with istringstream. It works similar to cin.

Example:

string s  = "-234.34, 324.234, 3243.22232,876.435";
// replace commas with spaces
replace(s.begin(), s.end(), ',', ' ');

istringstream ss(s);
double d;
while(ss >> d) {
  cout << d << endl;
}

You could of course do this by processing the string character by character, but that can be messy and error prone.

The stringstream class is also useful and works similar to cout. One use is to convert doubles into strings.

Example:

// create a double
double d = 1.22423;

// create a stringstream and put our double into the stream
stringstream ss;
ss << d;

// convert our stream into a string
string s = ss.str();