SRM 702, D2, 1000-Pointer (SubsetSumExtreme)

James S. Plank

Sun Nov 20 22:47:08 EST 2016
This one feels like dynamic programming, and indeed it is, but you have to set up your data structures correctly. The constraints on the size of the block vector should give you a clue. How many collections of blocks are there? If there are B blocks, then the answer is 2B, and with B limited to 12, that's a small number (4096).

How can we represent a collection of blocks? Bit arithmetic, of course? If you have B blocks, you can use a B-bit number to represent any subset of the B blocks. (See the "Power Set" section of the CS302 lecture notes on enumeration).

To solve this problem, we are going to write a recursive method: 

double GE(int setid);

This method takes as input the specification of a subset of the blocks (using bit arithmetic), and it returns the expected value of Bob playing the game when he starts with that subset.

Let's use Example 0 to illustrate. In this example, block is {1,2,3}, and face is {6,5}. Here are some calculations of GE():

When Bob first plays the game, he has all of the pieces, so the answer to the problem is going to be GE(0x7).

The general structure of GE()

The way GE(s) works is as follows. Maintain a sum, which starts at zero. For each value f of face, you need to decide:

At the end, divide the sum by faces.size(). There's your expected value.

There's a small subtlety

Given a set s and a value f, how do you determine all of the subsets that result when you remove blocks from s whose total is f?

Here's how I did it -- at the beginning of my program, I created two vectors:

Now, in GE(s), let's assume that SizesOfSets[s] = x. And, assume I'm considering a roll of f. What I do is look at all of the set ids in SetsBySize[x-f]. These are all of the subsets that have blocks sum to x-f, which of course, will be the sum when I remove blocks from x that sum to f. The problem is, though, you may not have the proper blocks to remove from s to get all of these sets.

Here's an example. Suppose that my blocks are { 1, 3, 2, 2 }, my faces are { 2, 6 }, and I am in GE(0xb), considering the face of size 2. The id 0xb corresponds to { 1, 3, 2 }, which has a sum of 6. So, when I consider f=2, I need to look at all sets whose blocks sum to 4. There will be two of these in SetsBySize[2]: { 0x3 and 0xc }. Just so we're on the same page, 0x3 is equal to { 1, 3 }, and 0xc is equal to { 2, 2 }.

Now, you can get to set { 1, 3 } from { 1, 3, 2 }, but you can't get to { 2, 2 }. Therefore, when you are considering face 2, you should be calling GE(0x3) and not GE(0xc). How do you determine that? With bit arithmetic! If you are at set s, and you are considering whether you can get to subset t, you take their intersection and see if it equals t. If so, then you can get to from s by removing blocks. If not, you can't. You can detemine intersection with bitwise AND.

In our example: (0xb & 0x3) is equal to 0x3, which means you can get to 0x3 from 0xb. On the other hand, (0xb & 0xc) is equal to 0x8, so you can't get to 0xc from 0xb.

Putting it all together

So, here are the steps:
My solution. 

/* Topcoder SRM 702, D2, 1000-pointer: SubsetSumExtreme.
   James S. Plank
   November 20, 2016
 */

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class SubsetSumExtreme {
  public:
    vector <int> SizesOfSets;                /* For each set, this is the sum of its blocks. */
    vector < vector <int> > SetsBySize;      /* All of the sets that have the same size. */
    vector <int> F;                          /* This is a copy of "face". */
    vector <double> Cache;                   /* The memoization cache. */

    double GE(int setid);
    double getExpectation(vector <int> block, vector <int> face);
};

double SubsetSumExtreme::GE(int s)
{
                    /* These variable names follow the writeup: */
  double sum;       /* This is the sum for the expected value computation. */
  int x;            /* This is the sum of the blocks in s */
  int f;            /* This is the face of the die that we are currently considering. */
  int t;            /* This holds set ids of sets whose blocks sum to x-f. */
  
  double best;      /* For each value of f, this is the best way to do x-f */

  int i, j;         /* These are temporary variables. */
  double r;

  if (s == 0) return 0;
  if (Cache[s] >= 0) return Cache[s];

  sum = 0;
  x = SizesOfSets[s];

  /* For each face f on the die: */

  for (i = 0; i < F.size(); i++) {

    /* Look at each set t whose blocks sum to x-f. */

    f = F[i];
    best = x;
    if (x-f >= 0) {
      for (j = 0; j < SetsBySize[x-f].size(); j++) {
        t = SetsBySize[x-f][j];

        /* If t is a proper subset of s, then call GE recursively. */

        if ((s & t) == t) {
          r = GE(t);
          if (r < best) best = r;
        } 
      }
    }

    /* Add the best answer for f to the sum. */

    sum += best;
  }

  /* At the end, divide sum by F.size() to complete the expected value computation. */

  sum /= (double) F.size();
  Cache[s] = sum;
  return sum;
}

double SubsetSumExtreme::getExpectation(vector <int> B, vector <int> face)
{
  int i, j;
  int sum;

  F = face;

  /* Do a power set enumeration to enumerate all subsets of the blocks.  
     In this enumeration, you're going to set all of the values of
     SizesOfSets and SetsBySize. */

  SetsBySize.resize(1000*12+1);

  for (i = 0; i < (1 << B.size()); i++) {
    sum = 0;
    for (j = 0; j < B.size(); j++) {
      if (i & (1 << j)) {
        sum += B[j];
      }
    }
    SizesOfSets.push_back(sum);
    SetsBySize[sum].push_back(i);
  }

  /* This loop prints out SetsBySize, in case you want to see it. 

  for (i = 0; i < SetsBySize.size(); i++) {
    if (SetsBySize[i].size() > 0) {
      printf("Size: %4d.  Sets:", i);
      for (j = 0; j < SetsBySize[i].size(); j++) printf(" 0x%x", SetsBySize[i][j]);
      printf("\n"); 
    }
  }
  */

  /* Set the memoization cache, and then call GE() on the set which contains
     all of the blocks. */

  Cache.resize(1 << B.size(), -1);
  return GE( (1 << B.size()) - 1 );
}