October 21st Practice Session

Last night we had our weekly Wednesday night practice session. Based on results from previous competitions, I’ve noticed that typically our top performing team is one problem short of a top tier spot in the contest. Also, in the ACPC competition from last Saturday, UVic White solved 8 problems without any errors, but they had some large gaps between submissions. As a result, we decided to try to work on coding speed.

Everyone was given a set of 8 easy to medium problems selected from the last 2 years of ACPC. They had to work as individuals and try to solve them as quickly as possible.

Unfortunately, the UVA online judge was down, so I wasn’t able to test their solutions until today. Also, unfortunately, the results were not great. There were quite a few wrong answers and time limit exceeded. Some of these issues were due to minor oversights, but a few were due to the use of incorrect approaches for the problems.

The one problem that no one successfully solved was Partitioning the Palindromes. This was the trickiest problem in the set.

In this problem, you are given a single string, and you want to partition it into subsets, where each subset is a palindrome and you want to do this such that the number of subsets is minimized. Also, a valid subset has to be a substring of the original string, you can’t move letters around.

As an example, consider the string “aaadbccb”. You could potentially partition this into individual letters {“a”, “a”, “a”, “d”, “b”, “c”, “c”, “b”}. However, this leads to 8 subsets, you can do better by building larger palindromes, i.e. {“aaa”, “d”, “bccb”}.

To solve this problem, you could potentially do backtracking, but if you look at the contraints, the length of the original string can be up to 1000 characters, which means backtracking will be way too inefficient. This usually leaves one of two choices, a greedy approach or dynamic programming.

It’s easy to see that greedy will not work. Consider the string “abbadabb”. With greedy, you could choose the largest palindrome that you can make with the first letter, “abba”. Then the next two letters must be in their own subsets and finally the “bb” forms the last subset. However, the optimal solution is to split the string into subsets {“a”, “bbadaabb”}.

One way to start to think about this problem is to think about the palindrome subsets as nodes in a graph. For example, let’s take the string “aaadbccb”. Originally, starting on the left hand side of the string, we can form palindromes “a”, “aa”, and “aaa”. Consider those as three different nodes in our graph. If we start with node “a”, what nodes could we get to from here? Well, basically any palindrome starting with the second letter of our string, so this only includes palindrome “a” and “aa”. We can do the same type of expansion for the original “aa” and “aaa” nodes. If we continue this expansion, we get a graph like the one below.

Notice how the shortest path through the graph represents the minimal subset of palindromes. So, we could possibly do a breadth-first search, adding nodes to a queue and stopping when we complete the string. However, this, like backtracking, will be too slow.

The key insight that you need is to realize that a lot of these branches are useless to process. There’s a lot of duplicate construction, or overlapping construction, which generally means memoization or dynamic programming is a good approach.

The way you can use this idea in this particular problem is to keep track of the minimum number of subsets used to create a string of length L. You only process a particular node expansion if you can improve this cost, otherwise, you should cut the branch as you can’t possibly do better than what you have already computed. You could do this recursively or do it BFS style with a queue. In semi-pseudocode, the BFS solution looks like the following:

// create array of min subsets, set values to infinity
int M[1001];
queue q;
  
int minSubsets(string s) {
  addNeighbors(s, 0, 0, 0);
  
  while(q is not empty) {
    Node p = q.dequeue();

   if(p.stringSize == length(s)) return p.subsetSize;
      
    addNeighbors(p.startIndex, p.stringSize, p.subsetSize);
  }
}
  
// add any palindromes that extend the current subset
void addNeighbors(int startIndex, int stringSize, int subsetSize) {
   for(int i = startIndex+1; i < length(s)+1; i++) {
      int stringLength = stringSize+i-startIndex;
      // make sure the new subset is better than a previous one
      // for the given string length
      if(M[stringLength] > subsetSize+1 
          && isPalindrome(substring(s, startIndex, i))) {

          M[stringLength] = subsetSize+1;
          Node n(startIndex, stringLength, subsetSize+1);
          q.enqueue(n);
      }
   }
}

There are many problems that can be solved using a similar method. For example, both of these problems from the 2007 Pacific Northwest Regional competition can be solved this way with a few other tricks added in: Pebbles and Bridged Marble Rings.