
Match Editorial 
SRM 105Wednesday, July 24, 2002
The Problems
StringSet (Value 250)
Used as: DivisionII, Level 1:
Submission Rate  185/204 (90.69%)
Success Rate  165/185 (89.19%)
High Score  Liam for 247.44 points
Implementation
This problem consists of building and maintaining a set (or rather the complement of a set). Since the alphabet consists of 26 letters (which, even more conveniently, are represented by a contiguous range of ASCII values), we only need a boolean array of length 26. For each letter we encounter, we mark its corresponding index in the boolean array (which is found by subtracting the value 'A' from the character).
After we have iterated through all of the characters, we build a string by iterating through the alphabet in order. For each unmarked index in the array, we append the letter that corresponds to that index (found by adding the value 'A' to the index) to the string. After we traverse the entire alphabet we return the string.
Stream (Value 550)
Used as: DivisionII, Level 2:
Submission Rate  123/204 (60.29%)
Success Rate  75/123 (60.98%)
High Score  FrodoB for 448.12 points
Used as: DivisionI, Level 1: (Value 250)
Submission Rate  121/127 (95.28%)
Success Rate  107/121 (88.43%)
High Score  zoidal for 239.35 points
Reference implementation: FrodoB
Implementation
One needs to be able to perform two complementary tasks in order to do this problem: decompose an integer into its component bits, and compose an integer from a sequence of bits.
Decomposition
There are two ways to do this. If one is using Java, one can simply call the
Integer.toBinaryString
method to get a String representation of the bits (which everyone should know how to manipulate). Be sure to pad the beginning of the strings with as many zeros as are necessary to make the string exactly 32 characters in length.
Another method is to use the bitwise operators to extract bits. The expression value & (1 << n) is nonzero only if the
n th
bit of value is 1. Note that the order of bits in the stream is the opposite of the order of bits in an integer. Bit 0, as obtained by the expression just given, is the last bit in the bit stream.
Composition
Again there are two methods. If one is using Java, one can use the
Integer.parseInt
method with a radix of 2 to convert a string of ones and zeros into an integer. If one is using bitwise operators, then the expression value = (1 << n) will set the n th
bit to 1. One could also shift the value one bit to the left and then set the 0 th
bit using the next bit in the stream, for each bit in the stream (e.g., value <<= 1; value = bit;).
With these tools in hand, the problem is easy. It is just a matter of following directions and being careful about padding.
GridLocks (Value 900)
Used as: DivisionII, Level 3:
Submission Rate  56/204 (27.45%)
Success Rate  7/56 (12.5%)
High Score  pernick for 648.04 points
Reference implementation: Pernick
Implementation
Determining if any cell in the grid is "surrounded" consists of a familiar depthfirst search (e.g., a flood fill). One can either do a DFS starting at the cell in question, or one can do a floodfill from all of the edge cells (thus marking all the nonsurrounded cells of a certain type at once).
PowerPlant (Value 500)
Used as: DivisionI, Level 2:
Submission Rate  89/127 (70.08%)
Success Rate  50/89 (56.18%)
High Score  SnapDragon for 471.96 points
Reference implementation: WishingBone
Implementation
Our initial approach to solving this problem might consist of a depthfirst search. We start on the first day, where we only have one choice for power output. On the next day (assuming the next day is not the last day), we may have as many as three different choices for power output, dependent upon the power output chosen for the previous day. While this method would work, there might be as many as 3 ^{48} possible choices  far too many to compute in 8 seconds.
An alternate approach is dynamic programming. Suppose that for any particular day, we know every output level that we can possibly have that satisfies all constraints for all the previous days, and for each such output level we know the minimum output level over all the days up to and including that particular day. Then from this information we can compute the same information for the next day.
For each possible output level, we know we can either add 100, subtract 100, or leave as is. For each of these actions, we can determine whether the output level will be too low for the next day (or, for the last day, if the output level is not the right one at all). At the same time we maintain our minimum output level for each output level. All we need is an array of pairs of integers (or a pair of arrays of integers) for each day.
Parliament (Value 1000)
Used as: DivisionI, Level 3:
Submission Rate  17/127 (13.39%)
Success Rate  3/17 (17.65%)
High Score  SnapDragon for 544.10 points
Reference implementation: SnapDragon
Implementation
From the statistics it is apparent that this was a devilishly difficult problem. However, once the solution is seen, it seems much simpler.
For each party we maintain a list of coalitions such that the sequence for each coalition ends with the given party. Each coalition can be represented as a simple bitset (e.g., an nbit integer for n parties). Initially each party's list of coalitions consists of a single set containing only that party. We then incrementally grow each coalition until we cannot increase the size of any coalitions.
Suppose we wish to grow a coalition that ends with party X. We iterate through each party Y that X sympathizes with. We create a new set by adding Y to the original set. If none of the parties in this new set dislike each other, and this new set is not the same as any of the sets currently in Y's list of coalitions, then we add the new set as a new coalition in Y's list. For determining whether any parties in the set dislike each other, we can precompute all the impossible sets in advance, by iterating through all the nbit integers (e.g., O(2^{n}n^{2}), which is reasonable for n <= 15).
Once we can make no more new, unique coalitions, we return the size of the largest one we constructed. We can update this value as we build the coalitions, eliminating the need to iterate through all our constructed coalitions before we return.



COMMENTS 
Hey I noticed in the overview of problem set 105 that you guys mention
creating an array of booleans for az and using that to solve the problem.
Well I had a bit of an easier way.
#include <string>
#include <vector>
using namespace std;
class StringSet
{
public:
string compliment(vector<string> input)
{
string output = "";
for(int x = 'A'; x <= 'Z'; x++)
{
bool found = false;
for(int y = 0; y < input.size(); y++)
{
if(input[y].find((char)x) != string::npos)
found = true;
}
if(!found)
output += (char)x;
}
return(output);
}
};
Now, I'm not professing to be the best coder in the world, but
I just happened to think it out this way, and I think it's better,
but I could be wrong. It makes use of the string find algorithm.
Ssmoimo