Hacker Cup 2014 Qualification Round

I passed the Facebook Hacker Cup qualification round last week-end (problems). Unlike other rounds, there’s no real time pressure in the qualification round. I normally use Java for these competitions since the most productive IDE I have is JetBrains’ IntelliJ IDEA. However, since I’m trying to become more adept at the new idioms of C++11, I also tried that (using Xcode) for two of the problems.

The first problem involved identifying a square of ‘#’ characters in a field of ‘.’ characters. After some messy Java code that analyzed the grid as it was read in, my C++ effort read in the whole grid into memory first. The following C++ felt decent for finding the first and last rows not consisting of all ‘.’ characters:

string blank(n, '.');
auto isntBlank = [&blank](const string & row) { return row != blank; };
auto firstRow = find_if(grid.begin(), grid.end(), isntBlank);
auto lastRow = find_if(grid.rbegin(), grid.rend(), isntBlank);

However, I couldn’t subtract those variables to find the difference because the types are different (one is a forward iterator and the other is a reverse iterator). The base() method converts a reverse iterator to the underlying forward iterator, so the count is determined by

  lastRow.base() - firstRow

A few applications of similar find logic provided a solution that contains no explicit loops, which is a nice result.

I implemented the second problem dealing with basketball substitution patterns using a pair of priority queues for each team: one queue for the players on the court and another for the players on the bench. I don’t think there’s a clean way to allocate an array of generic collections in Java, and I ended up with the following for the bench of the two teams:

@SuppressWarnings("unchecked")
PriorityQueue[] bench = new PriorityQueue[2];
...
bench[t] = new PriorityQueue<>(n, new Comparator() {
   @Override
   public int compare(Student a, Student b) {
      if (a.minutes < b.minutes)
         return -1;
      if (a.minutes > b.minutes)
         return 1;
      if (a.draft < b.draft)
         return -1;
      if (a.draft > b.draft)
         return 1;
      return 0;
   }
});

C++ has a built-in pair<> template class that makes the comparison part more compact, but I never found a clean way to declare the array. For each type of queue, the players and the bench, requires a different comparison function, so it can’t be built-in to the object class itself. There’s a constructor to supply a separate comparison function for that case, but I couldn’t get the constructor argument to match the generic comparison type so I ended up specifying the type in the template argument list. It seems to violate the C++ DRY goal, but it’s not too bad using a typedef.

auto benchLess = [](Student const & a, Student const & b)
   { return make_pair(a.minutes, a.draft) > make_pair(b.minutes, b.draft);};
typedef priority_queue<Student, vector, decltype(benchLess)> BenchType;
BenchType bench[]{ BenchType(benchLess), BenchType(benchLess)};

The third problem involved a dynamic programming style probability calculation and contained the statement, “It is guaranteed that the output is unaffected by deviations as large as 10-8. ” I’m now not sure what that means. I took it to mean that conditional probabilities could be rounded to 10-8 and values less than 10-8 could be ignored in order to get the required 6 digits on accuracy. As an optimization I ignored values less than 10-10. However, that led to one of my answers having just less than the required accuracy, so there must be some other meaning to the statement.

Hoping to try round 1 next week.