Basics of Kenken Puzzles

If you don't know the rules of KenKen then you can refer to www.kenken.com for an excellent source of daily puzzles which also explains the rules. I'll summarise it as best I can, it's a puzzle where you need to fill in each cell such that each row and cell contains a unique sequence of numbers respectively. If you are more familiar with Sudoku, it's similar in terms of the fact that each row/column can only contain one 1, one 2, one 3.. one 9. In KenKen's case, you are allowed to use numbers 1,2...,n. Where n is the size of the puzzle. However, unlike Sudoku you must ensure each 'cage' (bolded subareas on the puzzle) adds, multiplies, subtracts or divides to the target number listed on the a top-left corner of the cage. Subtraction and Divisions can be done in any order, so 2 / 4 and 4 / 2 both match 2/ (division). However, the constraints of unique numbers must be adhered to at all times. For more information, just refer to www.kenken.com.

Today we will be solving and walking through a simple 6x6 KenKen puzzle (from www.kenken.com). There are several important concepts which will make your puzzle solving much simpler. KenKen can seem daunting at first, but it's a solvable puzzle without guessing! There is always a way to deduce/use logic to fill in the cells without trial and error. I hope to highlight some of these through this given KenKen puzzle:

So, how do we get started? We don't exactly have any free single 1x1 cage to immediately write down. Usually if there is a simple 1x1 cage you should write down those numbers first because they can give hints to surrounding cages in similar rows/columns.

Now note that today we are solving a 6x6 puzzle, hence we are only allowed to fill in numbers 1 to 6. This is important to note because it limits the number of possibilities for each cage. One of the first things I tend to look for first - is a cage in which I immediately know what numbers are contained in those cages but not necessarily the right order. For a 6x6 puzzle, you should look primarily for 11+ and 5- cages. Why is this? It's because there is only one possibility for each of the cages, namely 5 and 6, and 1 and 6 respectively. (Question: If it was a 8x8 puzzle, what numbers should you be looking for?) Don't worry too much about the ordering at the moment - the correct ordering will come as we fill the puzzle. Noting these down we get:

We can also note several one possibility cages, 15x = 3 * 5. There is no other way of multiplying two numbers less than 6 to equal 15. There's also another subtle one, 36x. How many possibilities does this have? Well it seems like there may be a few, 6*6*1, 6*3*2, 3*3*4. However, in our puzzle 36x exists in a row which means there can be no repeated terms in the factoring! Hence we can rule out 6*6*1 and 3*3*4 being valid possibilities for the 36x cage. This just leaves a single possibility, 6*3*2! Anymore cages that only have one possibility? 20x also looks tempting - let's see, 5*4*1 and 5*2*2. But wait! Again, 20x is on a row and can't have any repeated elements so it just leaves one possibility: 5*4*1! There may be more but let's just put these on the puzzle first:

You may note that we actually haven't even filled a single entry yet! This is quite normal, you'll slowly realise that many possibilities will start collapsing when you fill a few in!

Now we will employ a more tricky technique which is immensely useful in solving KenKen puzzles. In Mathematics, this is called the Pigeonhole Principle. Essentially, the Pigeonhole Principle states that if you have n items and wish to place them into m boxes with n > m, then at least 1 box will contain more than 1 item. How on earth are we going to apply this to the puzzle? We need to look in a vertical manner - note how the 3 rightmost columns (4th to 6th columns) already contain 4 possibilities of having a 5 in them? Wait! 4 possibilities in 3 columns that violates the rules of the puzzle! Hence, one of these must not belong in the 3 rightmost columns. Now look at the bottom-most 11+, the 5 in this cage can exist on the 3rd column! Therefore, if this puzzle has a solution the 5 must belong in the 3rd column. So let's fill this in...

Now the bottom-most 11+ cage must have 6 in the unfilled cell. Now you notice that it also fills in the other 11+ cage in the 3rd row! Because the number 6 exists in the 4th column, it means the 3rd row 11+ cage must have number 6 in the 5th column. This then cascades to 36x! The number 6 for 36x (2*3*6) must go to the rightmost column otherwise it will violate the other 2 columns that we just filled in. For Sudoku solvers this should be in your familiar territory! That one observation allowed us to chain-complete a portion of the puzzle:

What else can we fill in? It's important to consider new point of views after you have filled in a set of entries because by filling in correct positions for cages - it reduces the possibilities for cages that are related to it (relation comes from the single 1 to 6 constraint on the rows/columns). If we observe the 3/ (division) cage on the rightmost column, previously it has the possibility of 3/1, 6/2. However now that we have filled in 6 on the rightmost column, the only possibility is 3/1. If you jot this down on the cage, you notice that we can now fill in 15x because the number 3 in 3*5=15 cannot belong to the rightmost column anymore so hence we have uniquely determined the correct position. Again, a lot of cascading solutions - by solving the 15x, we now know the position of the 5 in 20x and the position in 3x (validate it for yourself). If you fill in the details you'll get something like the following:

Now it looks much better! At this stage, we can fill in 24x because we know the product of its divisors cannot contain a 3 as it will violate the first row only having one 3 (it's taken by the 15x). 24x = 1*4*6. Note that it also can't be 2*2*6 because it exists in a single row and we can't have duplicate elements because it'll violate the rules. Note that the 4- cage on the leftmost column can be uniquely identified to be 6-2. How did we do this?

There are actually multiple ways to view this - the simplest is to note that the first row possibilities are completely filled except for one number. We have used 1,4,6 for 24x and 3,5 for 15x. That leaves only the possibility of 2 in the left and uppermost cell. Now we can't put negative numbers so the only possibility for the other cell in the cage is 6 - making 6-2=4.

The other way to view this will prove to be more useful when solving larger KenKen puzzles. Note that on both row 1 and row 2 we have used the number 5 already. 4- only has two possibilities for a 6x6 KenKen puzzle, 6-2 and 5-1. Hence if 5 cannot go in either of the cells in the cage then it cannot be 5-1, leaving 6-2. Let's fill these in:

So now we have an interesting pattern. the 12x cage is a L-shaped figure. This actually provides useful information that you may not first realise. By filling in the 6 on the 2nd row, we know for certainty that the remainder of the 2nd row is numbers 2,3. Hence we can automatically deduce the 3rd row/3rd column cell to be 2 as shown above. Again, there are multiple ways to view this. We can view 12x as a cage and note that we have 2,3 inside the cage already. This leaves us the unique number remaining to be 2 (12 / (2*3)).

For any L-shaped cage, if there are a repeated element (in this case the number 2), then they will always go on the ends of the L-shape. The reason for this is simple, if they were placed any other way they would conflict and violate the unique number rule. Filling in these numbers yields the following partially complete puzzle:

There is another tip that is useful. If you look at the 4th column in which we have filled in (1,5,3,6). We can actually uniquely and correctly identify the 4th number in the first row by noting that we reduced 24x to 1*4*6. But 2 of these numbers have already been used in the 4th column, hence the missing and correct number to fill in is '4'. This gives the partially solved puzzle:

Give it a try to solve the remainder of the puzzle! Happy Solving! =)

[Spoilers Ahead]
Note:
If you get stuck, I've included the solution below:

TC SRM 487 D1-500 KiwiJuice

Category: Dynamic Programming
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11019

class KiwiJuice {
public:
   int theProfit(int, vector <int>, vector <int>);
};

int dp[51][1<<16];
vector<int> data;
vector<int> price;
int _C;

// f(current volume of the special bottle, bitmask of the used bottles)
int f(int i, int mask) {
   // caching mechanism
   if (dp[i][mask] != -1) return dp[i][mask];
   // base case
   if (mask+1 == (1 << (data.size()))-1) {
      return price[i];
   }
   int res = 0;
   for (int j = 1; j < data.size(); j++) {
      if (mask & (1 << j)) continue;   // already used
      // the next bottle to process
      int next = data[j];
      int d1 = 0;
      if (i + next >= _C) {
         // one of the bottles is full, the other is i+next-_C volume
         d1 = price[_C] + f(i+next-_C, mask | (1 << j));
      } else {
         // change to i + next (and used up the empty for bottle[j])
         d1 = price[0] + f(i+next, mask | (1 << j));
      }
      // don't add more to our current bottle
      // we swap with bottle j and "use" up our bottle
      int d2 = f(next, mask | (1 << j)) + price[i];
      
      // take the maximum of the decision branches
      res >?= max(d1,d2);
   }
   return dp[i][mask] = res;
}

int KiwiJuice::theProfit(int C, vector <int> bottles, vector <int> prices) {
   price = prices;
   int res = 0;
   _C = C;
   memset(dp,-1,sizeof(dp));
   data = bottles;
   return res = f(data[0],0);   // arbitrarily assign bottle 0 to be our special bottle
}

TC SRM 487 D1-250 CarrotJumping

Category: Brute Force, Mathematics
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11022

class CarrotJumping {
public:
   int theJump(int);
};

long long MOD = 1000000007;

// compute 2^n (mod MOD)
long long pow(int v) {
   if (v == 0) return 1;
   if (v == 1) return 2;
   long long x = pow(v/2);
   if (v % 2 != 0) return (x * x * 2) % MOD;
   return (x * x) % MOD;
}

int CarrotJumping::theJump(int init) {
   int res = 100001;
   for (int a = 0; a <= 100000; a++) {
      for (int b = 0; b < 3; b++) {
         long long v = pow(a*3 + b*2);
         long long c = (v * init + (v - 1 + MOD) % MOD) % MOD;
         if (c == 0) {
            res <?= (a + b);
         }
      }
   }
   return res >= 100001 ? -1 : res;
}

SPOJ - Assignments (ASSIGN)

URL: http://www.spoj.pl/problems/ASSIGN/
Category: Dynamic Programming, Bit Manipulation

The problem is quite simple: to calculate the number of different assignments of n topics to n students provided that every student gets exactly 1 topic that he likes. Each student likes different topics which is given in the format of a matrix. The essence of the problem lies in optimisation, a brute force algorithm will clearly time out if that isn't already evident. As a note, the maximum number of assignments for a 20x20 (filled with 1's) matrix is a massive 2,432,902,008,176,640,000. Since we are enumerating we can easily eliminate greedy as a design approach. Naturally we turn to dynamic programming to somehow reduce the running time to an acceptable amount.

As with all dynamic programming problems, we first define the state. The most natural and obvious state is:

D(s,u) = amount of ways to assign up to student s with a bitmask of subjects u used.

The space complexity of this DP state is O(N * 2^N). However, a observation allows us to reduce the memory footprint by a factor of N, giving a complexity of O(2^N). How does this work? The unique property of the problem is that the number of students and subjects are the same, so we can deduce that when we are up to student V, there are also exactly V bits set in the bitmask. Hence, we can simply just use the bitmask to determine which student we are up to!

Now let's define the recurrence relation:

F(u) = sum of all i { F(u | (1 << i) } where student count_of_bits(u) likes subject i

The base case is,

F((1 << total_students)-1) = 1

Note we have done something implicit. That is, we do not define the base case for where we have "left over" subjects that weren't assign to a student - this is implicitly handled by our looping.

We then code a memoised solution using the recurrence above:

long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

long long func(int topicMask) {
   int idx = count_bits(topicMask);
   if (idx >= size) {
      if (topicMask != (1 << size)-1) return 0;
      return 1;
   }
   if (memo[topicMask] != -1) return memo[topicMask];
   long long res = 0;
   for (int i = 0; i < size; i++) {
      if (adjmat[idx][i] == 0 || topicMask & (1 << i)) {
         continue;
      }
      res += func(topicMask | (1 << i));
   }
   return memo[topicMask] = res;
}

Unfortunately, this times out in SPOJ, i.e. it exceeds over 20 seconds for all test cases. This is where bottom-up dynamic programming shines, given that our algorithm is probably close to the time limit (you can check by running on your own machine and noting the speed - if it's quite fast but times out in SPOJ, you are within a constant time factor of passing). Now turning it into a bottom-up dynamic programming is a bit more tricky than usual. The problem lies with the order on which to evaluate.

If we set the same base case as before with,

F((1 << total_students)-1) = 1

We need to somehow traverse backwards whilst also ensuring that we have computed all DP states that are one bit away from the one we are calculating. Turns out due to binary number representation, traversing from (1 << total_students)-1 to 0 is sufficient. This is a rather easy proof and hence left to the exercise of the reader (just list them out for 4-bit numbers and you should see the connection).

The implementation is detailed below:

int adjmat[21][21];
int size;
long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = count_bits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

We can shave off some extra time by using a constant time bit counting algorithm (you can google it):

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int adjmat[21][21];
int size;
long long memo[1<<20];

unsigned numbits(unsigned i)
{
    const unsigned MASK1  = 0x55555555;
    const unsigned MASK2  = 0x33333333;
    const unsigned MASK4  = 0x0f0f0f0f;
    const unsigned MASK8  = 0x00ff00ff;
    const unsigned MASK16 = 0x0000ffff;

    i = (i&MASK1 ) + (i>>1 &MASK1 );
    i = (i&MASK2 ) + (i>>2 &MASK2 );
    i = (i&MASK4 ) + (i>>4 &MASK4 );
    i = (i&MASK8 ) + (i>>8 &MASK8 );
    i = (i&MASK16) + (i>>16&MASK16);

    return i;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = numbits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

TC TCO10 Qualification Round 2

Overview:

This was the second qualification round for TCO10 with around 1300 competitors. As 600 competitors advance through to the next round (provided that at least 600 score a positive score), it provided ample opportunity to qualify for Round 1. The problems were rather simple with two greedy problems and a simple DP problem as the 1000 pointer. Having said that, the system test claimed a decent portion of the 500 pointer solutions due to a corner case which wasn't covered in the examples.

Problem 1 (250 Points): JingleRingle
Category: Greedy
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10896

This problem required us to calculate the maximum profit we can make by buying jingles and selling them to various buyers. We are assumed to have infinite wealth so we can essentially buy all the jingles but we also want to maximise our profits.

The first key observation is to note that we can only use each buyer or seller once. The second key observation is that we only buy jingles from sellers if we can find a suitable buyer in which we can make a net profit (after tax). Now the question that remains is which sellers do we buy from and whom do we sell it to. Since each seller only gives us 1 jingle and we can only sell back 1 jingle at a time, this constraint essentially means that we can match a seller to a buyer (i.e. we are buying at a lower price and re-selling it at a higher price for a net profit). A simple greedy strategy would be then to buy at the lowest price and selling it to the highest price for maximum profit.

Does this greedy strategy work? Let's informally prove it. As we need to match a seller and buyer, if we buy from N people then we also have to sell it to N people. To maximise our profit we need to maximise our revenue, so the optimal choice is to choose the N highest buyers. Then to minimise our expenses we need to choose the N lowest sellers of jingles. It turns out it doesn't matter what order we pair the buyers and sellers as the total profit is the same if we choose the N highest buyers and N lowest sellers. Now all we need is to determine the value of N. Our greedy algorithm keeps pairing the highest available buyer to the lowest available seller until we reach a situation where we no longer profit, this is the value of N. If we assume this is not the value of N, then we have to somehow match a lower buyer to a higher seller or vice versa. But our value of N is at least as good as this on all cases hence our deduced value of N is correct.

A straightforward implementation:

class JingleRingle {
public:
   int profit(vector <int>, vector <int>, int);
};

int calcTax(int p, int tax) {
   return (p * tax) / 100;
}

int JingleRingle::profit(vector <int> buyOffers, 
      vector <int> sellOffers, int tax) {
   int res = 0;
   int buyJ = buyOffers.size()-1;
   sort(buyOffers.begin(),buyOffers.end());
   sort(sellOffers.begin(),sellOffers.end());
   for (int i = 0; i < sellOffers.size(); i++) {
      if (buyJ >= 0 && buyOffers[buyJ] - calcTax(buyOffers[buyJ],tax) 
         - sellOffers[i] >= 0) {
         res += buyOffers[buyJ] - calcTax(buyOffers[buyJ],tax) - sellOffers[i];
      }
      buyJ--;
   }
   return res;
}

Problem 2 (500 Points): FuzzyLife
Category: Greedy, Brute Force
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10911

This problem has us calculate the maximum number of live cells on an infinite 2D plane after one iteration of time. The 2D plane is consisted of cells which are considered either dead or alive at a given slice in time. However, there are unknown cells denoted as '?' and our job is to determine whether each of these cells should be considered alive or dead for the next evolution in time to have the maximum number of alive cells.

The rules are:
- Each live cell with less than 2 or more than 3 live neighbours are dead
- Each dead cell with exactly 3 live neighbours becomes alive
- All other cell remain the same

Each cell has exactly 8 neighbours (even the ones on the "border" of the input because of the infinite plane) - 2 horizontal, 2 vertical and 4 diagonal.

The main observation required for this problem is the constraints of the problem allow us to adopt a greedy strategy and consider the neighbouring cells of a '?' as its own problem subinstance. As no cell will have more than 1 neighbour of type '?' this means that every cell is at most affected by 1 unknown cell. All we need to do is try each '?' cell by placing a '1' and a '0' in its place and simulate how many alive cells we are left with on the next iteration. We then simply choose the maximum of these two choices.

One tricky case is that we also need to take into account the '?' cell, if we place a '1' in it's position does it become alive or dead in the next iteration - vice versa if we place a '0'. We need to add this to our alive count before we compare which one is better. The other tricky case was to add a padding of dead cells around the grid as some of these can turn into alive cells (which need to be included in the answer) - this case however, was covered in the example cases. After we have filled in each of the '?' cells we can then do a single iteration pass and work out the number of alive cells.

The implementation using the ideas above:

class FuzzyLife {
public:
   int survivingCells(vector <string>);
};

// movement vectors
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int FuzzyLife::survivingCells(vector <string> grid) {
   int res = 0;
   // pad the grid with extra 0's around the perimeter
   string str(grid[0].size()+2,'0');
   for (int i = 0; i < grid.size(); i++) {
      grid[i] = '0' + grid[i] + '0';
   }
   grid.insert(grid.begin(),str);
   grid.push_back(str);
   for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[i].size(); j++) {
         if (grid[i][j] == '?') {
            // compute options ('?' = 1)
            grid[i][j] = '1';
            int c1 = 0;
            for (int m = 0; m < 8; m++) {
               int neighX = i + dx[m];
               int neighY = j + dy[m];
               if (neighX < 0 || neighY < 0 || neighX >= grid.size() 
               || neighY >= grid[0].size()) continue;
               int alive = 0;
               for (int n = 0; n < 8; n++) {
                  int mX = neighX + dx[n];
                  int mY = neighY + dy[n];
                  if (mX < 0 || mY < 0 || mX >= grid.size() 
                  || mY >= grid[0].size()) continue;
                  if (grid[mX][mY] == '1') alive++;
               }
               if (grid[neighX][neighY] == '1' && (alive == 2 || alive == 3)) c1++;
               else if (grid[neighX][neighY] == '0' && (alive == 3)) c1++;
            }
            // consider the square itself under '?' = 1
            int selfAlive = 0;
            for (int n = 0; n < 8; n++) {
               int selfX = i + dx[n];
               int selfY = j + dy[n];
               if (selfX < 0 || selfY < 0 || selfX >= grid.size() 
               || selfY >= grid[0].size()) continue;
               if (grid[selfX][selfY] == '1') selfAlive++; 
            }
            if (selfAlive == 2 || selfAlive == 3) c1++;
            // compute options ('?' = 0)
            grid[i][j] = '0';
            int c2 = 0;
            for (int m = 0; m < 8; m++) {
               int neighX = i + dx[m];
               int neighY = j + dy[m];
               if (neighX < 0 || neighY < 0 || neighX >= grid.size() 
               || neighY >= grid[0].size()) continue;
               int alive = 0;
               for (int n = 0; n < 8; n++) {
                  int mX = neighX + dx[n];
                  int mY = neighY + dy[n];
                  if (mX < 0 || mY < 0 || mX >= grid.size() 
                  || mY >= grid[0].size()) continue;
                  if (grid[mX][mY] == '1') alive++;
               }
               if (grid[neighX][neighY] == '1' && (alive == 2 || alive == 3)) c2++;
               else if (grid[neighX][neighY] == '0' && (alive == 3)) c2++;
            }
            // consider the square itself under '?' = 0
            selfAlive = 0;
            for (int n = 0; n < 8; n++) {
               int selfX = i + dx[n];
               int selfY = j + dy[n];
               if (selfX < 0 || selfY < 0 || selfX >= grid.size() 
               || selfY >= grid[0].size()) continue;
               if (grid[selfX][selfY] == '1') selfAlive++; 
            }
            if (selfAlive == 3) c2++;
            // choose the one with better live cells
            if (c1 >= c2) grid[i][j] = '1';
         }
      }
   }   
   // iterate one period and determine number of alive
   for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[i].size(); j++) {
         int alive = 0;
         for (int n = 0; n < 8; n++) {
            int mX = i + dx[n];
            int mY = j + dy[n];
            if (mX < 0 || mY < 0 || mX >= grid.size() 
            || mY >= grid[0].size()) continue;
            if (grid[mX][mY] == '1') alive++;
         }
         if (grid[i][j] == '1' && (alive == 2 || alive == 3)) res++;
         else if (grid[i][j] == '0' && alive == 3) res++;
      }
   }
   return res;
}

Problem 3 (1000 Points): HandlesSpelling
Category: Dynamic Programming, String Manipulation
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10864

This problem required us to play a game and work out the maximum score based on a set of choices we are forced to make. The game is that we have a string of letters in which we can "stamp" a set of pre-determined strings onto it. We need to maximise the score based on A^2 - B where A is the longest contiguous sequence of letters covered by the stampings and B is the number of uncovered letters.

For example, if the string we are given is HELLO and we are given 3 badges namely: E, HE, L. We can stamp them as follows: {HE}{L}{L}O. We stamped HE with the second badge and the 2 L's with the third badge. The value of A is 4 because we have a contiguous sequence of stampings (HELL) and B is 1 because we didn't have a way to stamp the letter O. Hence the score given this set of operations is 4^2 - 1 = 15, which turns out to be the maximum score we can get.

One strategy is to determine the maximum value of A. Why? A is where our score gets maximised, no other measure increases our score except for the value of A so it's only natural that we want to get A as high as possible. We also note that the maximum contiguous sequence (i.e. maximum value A) is in the optimal solution. Why? Consider two configurations:

xxxxx....----n----....xxxxxxxx
xxxxx--m--.......--m--xxxxxxxx

Here the x's denote similar configurations, so we only need to focus on maximising the centre part of m's, n's and dots. We let n be the maximum contiguous length possible in our string, let that be denoted as length x. Let's assign m to be length x-1. Then our goal is to prove that it is always optimal to choose n over the 2 m's.

Then the score for our first configuration is:
F = (x * x) - (x-1) - (x-1) = x^2 - 2x + 2 (length x ^ 2 minus two sections of x-1 uncovered)

The score for our second configuration is:
G = (x-1) * (x-1) - x = x^2 - 3x + 1 (length (x-1) ^ 2 minus one section of x uncovered)

Hence for all positive values of length x, the score for the first is better than the second. In fact, this is a stricter argument than what is required, as if the sections of n and m were disjoint they'll both be covered, hence there must be some conflict between n and m which forces us to choose between one or the other. Our argument will hold for such a scenario.

Our first task is then to find the maximum contiguous sequence of our string - this can be done easily through basic dynamic programming. Then we are tasked with trying all configurations which have the same maximum contiguous sequence to determine the minimum number of uncovered letters. Again, this can be done via a similar dynamic programming algorithm where we divide our main string into a left and right sub-string and count the maximum number of covered cells we can get. Then we simply subtract this by the size of the left and right sub-string respectively to get the number of uncovered letters.

The implementation which uses the strategy above can be seen as:

class HandlesSpelling {
public:
   int spellIt(vector <string>, vector <string>);
};

#define UNI -12345678
#define INF 12345678

vector<string> _badges;
string _S;

// returns true if str is a prefix to S starting at idx
bool isPrefix(int idx, const string& str, string S) {
   if (idx + str.size() > S.size()) return false;
   for (int i = idx; i < idx + str.size(); i++) {
      if (S[i] != str[i-idx]) return false;
   }
   return true;
}

int prefix[1001][51];   // true if badge j is a prefix at index i
int A[1001];   // keeps track of the longest sequence ending with index i
int B[1001];   // left hand side
int C[1001];   // right hand side
int maxSize;

// maximise coverage using ptr as the memoisation table
int func(int idx, int* ptr) {
   int res = 0;
   if (idx >= maxSize) return 0;
   if (ptr[idx] != -1) return ptr[idx];
   for (int i = 0; i < _badges.size(); i++) {
      if (prefix[idx][i] && idx + _badges[i].size() <= maxSize) {
         res >?= func(idx + _badges[i].size(), ptr) + _badges[i].size();
      }
   }
   res >?= func(idx+1, ptr);
   return ptr[idx] = res;
}

int HandlesSpelling::spellIt(vector <string> parts, vector <string> badges) {
   string data;
   for (int i = 0; i < parts.size(); i++) data += parts[i];
   _badges = badges;
   _S = data;
   // pre-compute the prefixes for speed
   for (int i = 0; i < data.size(); i++) {
      for (int j = 0; j < badges.size(); j++) {
         if (isPrefix(i, badges[j], _S)) { prefix[i][j] = 1; }
      }
   }
   // determine the longest contiguous sequence in our string
   for (int i = _S.size()-1; i >= 0; i--) {
      for (int j = 0; j < _badges.size(); j++) {
         if (isPrefix(i, _badges[j], _S)) {
            A[i] >?= A[i+_badges[j].size()] + _badges[j].size();
         }
      }
   }
   int longest = 0;
   for (int i = 0; i < _S.size(); i++) {
      longest >?= A[i];
   }
   // choose the best score out of all combinations which use A[i] == longest
   int res = UNI;
   for (int i = 0; i < _S.size(); i++) {
      if (A[i] == longest) {
         // branch off to left and right
         string left = _S.substr(0, i);
         string right = _S.substr(i+A[i]);
         // reset memo table for each instance
         memset(B,-1,sizeof(B));
         memset(C,-1,sizeof(C));
         int lOffset = 0, rOffset = 0;
         maxSize = i;
         if (left.size() > 0) lOffset = left.size() - func(0,B);
         maxSize = _S.size();
         if (right.size() > 0) rOffset = right.size() - func(i+A[i],C);
         res >?= (A[i] * A[i]) - (lOffset) - (rOffset);
      }
   }
   return res;
}

USACO Training Gateway - "A Game"

Problem Statement:

"Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents.

Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2."

Strategy:

This is a simple dynamic programming problem which involves the theme about games (two players) which is quite common. As no number in the sequence can be skipped, it is sufficient enough to compute one player's score and derive the other player's score by subtracting it from the total sum of the sequence on the board. This allows us to condense our DP state by a factor of 2 by keeping track of only one player's progress.

As with all DP problems we first define the DP state. Here an obvious one can be defined as:

D(n,m) = the best score for player 1 in which the board state is a contiguous subsequence between index n and m. Player 1's turn.
E(n,m) = the best score for player 1 in which the board state is a contiguous subsequence between index n and m. Player 2's turn.

As the maximum board size is only 100, an O(n^2) space complexity easily fits within the memory limits. Next we define our recurrence relation:

For the current player we can choose either the leftmost or the rightmost block, i.e. A[n] or A[m]. The next turn in the game is player 2's turn which is denoted by the E(x,y) relation. The obvious goal of player 2 is to minimise the gain of player 1 which will result in a higher score for him/herself.

Using the two recurrences we can combine them into one to get (using direct substitution from E(n,m) to D(n,m)):

Hence, we have constructed our recurrence for player 1. We keep track of the total sum of the sequence of the board during the input/parsing phase. Player 2's score is simply total sum - D(0, size-1). Lastly, we need to handle our base cases. If n = m, then we are left with one choice - choosing A[n]. If n > m, which means we have finished the game as the current board state is non-existent, then we return 0 as neither player can choose any more integers from the sequence. Hence explicitly the base cases are:

Implementation:

Using the idea above we generate the simple memoisation algorithm:

int dp[101][101];
vector<int> vec;

int func(int n, int m) {
   if (n > m) return 0;
   if (n == m) return dp[n][m] = vec[n];
   if (dp[n][m] != -1) return dp[n][m];
   int res = 0;
   res = max(min(func(n+2,m),func(n+1,m-1))+vec[n],
      min(func(n+1,m-1),func(n,m-2))+vec[m]);
   return dp[n][m] = res;
}

int main() {
   ifstream inFile("game1.in");
   ofstream outFile("game1.out");
   int N; inFile >> N;
   int sum = 0;
   for (int c = 0; c < N; c++) {
      int val; inFile >> val;
      sum += val;
      vec.push_back(val);
   }
   memset(dp,-1,sizeof(dp));
   outFile << func(0,N-1) << " " << sum - func(0,N-1) << "\n";
   return 0;
}

TC SRM 459 D2-1000 (ParkAmusement)

Category: Dynamic Programming, Graph Theory
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10723

The problem describes having N landings in the amusement park. The landings can be terminating (i.e. the ride ends at this landing) which are either proper exits or crocodile ponds. The landings can also be non-terminating which means that you will slide down further or until you are stalled with no valid adjacent landings. All of the N landings have different heights and we can only slide down from a taller landing to a shorter one (by the laws of gravity). We start at a random landing and we wish to calculate the probability that we started at a specific landing given that we only went through exactly K different pipes to get safely home (i.e. at a proper exit and not at either a crocodile pond or a dead-end landing).

This problem is best split into two parts. The first is to calculate the probability we reach home from a specific starting point. The second is to calculate the probability that out of all the viable starting points we chose the specific starting landing. We are already given the adjacency matrix in terms of a vector/array of strings which we proceed to convert into a more usable format. We first keep track of exits - i.e. whether or not they are proper exits (home) or crocodile ponds. This is done by specifically checking whether or not landings[i][i] is '0' or not (based on the problem definition). If it's not '0', then the current vertex is an exit and we proceed to determine which type. Otherwise, we add the edges into our adjacency list. This is shown below:

vector<vector<int> > adjlist;   // adjacency list
int table[51];   // the exit table for each vertex, 0 if it's not an exit, 1 if it's home exit, 2 if it's a pond exit

...
double ParkAmusement::getProbability(vector <string> landings, int startLanding, 
      int K) {
   adjlist = vector<vector<int> >(landings.size(), vector<int>());
   for (int i = 0; i < landings.size(); i++) {
      if (landings[i][i] != '0') {
         // exit
         if (landings[i][i] == 'P') table[i] = 2;   // pond
         else table[i] = 1; // exit
         continue;
      }
      for (int j = 0; j < landings[i].size(); j++) {
         if (landings[i][j] == '1') adjlist[i].push_back(j);
      }
   }
...

Once we have parsed the input into a better format, we need to find out the probability of reaching home from a fixed starting vertex/landing. We can accomplish this through a DFS-like recursive function by keeping track of how many steps we have left to reach home. This involves keeping track of which vertex/landing we are currently at and how many hops left we must use. The base case is when the number of steps left is zero, if we are at an exit and it's the proper one (i.e. an 'E' in the matrix) then we have reached home - otherwise we have failed in our mission.

We utilise basic probability calculations to compute our chances of succeeding. If we arrive at a landing that has M out-going edges, then the probability of choosing a particular edge is 1/M. Therefore, the probability we will survive is simply the sum of 1/M * f(edge i, K-1) for all out-going edges i. The base cases are obvious, probability of surviving is 1.0 if we reach an 'E' exit otherwise it's 0.0. The function below illustrates this concept:

double calcPr(int startNode, int K) {
   if (K == 0) {
      // check if it's the exit
      if (table[startNode] != 1) return 0.0;
      return 1.0;
   }
   double res = 0.0;
   // note: if there are no more valid out-going edges it defaults to a 
   //    0.0 probability
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return res;
}

However, we can optimise this by memoising it. Otherwise we may run into trouble with time limits for the larger cases. This is easily done by setting up a cache table and marking it with a sentinel value to determine whether the state has been computed or not. Since no probability can be negative, we can exploit this fact.

double dp[51][51];

double calcPr(int startNode, int K) {
   if (dp[startNode][K] >= 0.0) return dp[startNode][K];
   if (K == 0) {
      if (table[startNode] != 1) return dp[startNode][K] = 0;
      return dp[startNode][K] = 1.0;
   }
   double res = 0.0;
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return dp[startNode][K] = res;
}

Now, we have finished the first step of the problem. The second step involves calculating out of the many possible landings we have chosen and given that we did arrive home safely, what is the probability we chose startLanding? The easiest way to think of this is to think geometrically. If we let a circle C be the total sum of the probabilities that we arrived safely from all possible landings, we can scale this to 1.0 as we know for certainty that we arrived safely (given in the problem). Now we simply need to calculate how much probability was contributed by starting from startLanding. This is simply calcPr(startLanding, K) / totalSum. This can be visualised as:

double tot = 0.0;
for (int i = 0; i < 51; i++) for (int j = 0; j < 51; j++) dp[i][j] = -1.0;
for (int i = 0; i < landings.size(); i++) {
   tot += calcPr(i, K);
}
return calcPr(startLanding, K) / tot;

Combining all of the above steps, we yield the final code:

class ParkAmusement {
public:
   double getProbability(vector <string>, int, int);
};

vector<vector<int> > adjlist;
int table[51];
double dp[51][51];

double calcPr(int startNode, int K) {
   if (dp[startNode][K] >= 0.0) return dp[startNode][K];
   if (K == 0) {
      if (table[startNode] != 1) return dp[startNode][K] = 0;
      return dp[startNode][K] = 1.0;
   }
   double res = 0.0;
   int poss = adjlist[startNode].size();
   for (int i = 0; i < adjlist[startNode].size(); i++) {
      res += (1.0 / poss) * calcPr(adjlist[startNode][i], K-1);
   }
   return dp[startNode][K] = res;
}

double ParkAmusement::getProbability(vector <string> landings, int startLanding, 
      int K) {
   adjlist = vector<vector<int> >(landings.size(), vector<int>());
   for (int i = 0; i < landings.size(); i++) {
      if (landings[i][i] != '0') {
         // exit
         if (landings[i][i] == 'P') table[i] = 2;   // pond
         else table[i] = 1; // exit
         continue;
      }
      for (int j = 0; j < landings[i].size(); j++) {
         if (landings[i][j] == '1') adjlist[i].push_back(j);
      }
   }
   double tot = 0.0;
   for (int i = 0; i < 51; i++) for (int j = 0; j < 51; j++) dp[i][j] = -1.0;
   for (int i = 0; i < landings.size(); i++) {
      tot += calcPr(i, K);
   }
   return calcPr(startLanding, K) / tot;
}