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():
The other half of the time, he rolls a 6, and his sum is 5. So the contribution of rolling a six to the expected value is 0.5*5. Therefore, the exptected value is 0.5*0 + 0.5*5 = 2.5.
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:
Here's how I did it -- at the beginning of my program, I created two vectors:
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.
/* 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 ); } |