The Problems

StringSet (Value 250)
Used as: Division-II, 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: Division-II, Level 2:

Submission Rate - 123/204 (60.29%)
Success Rate - 75/123 (60.98%)
High Score - FrodoB for 448.12 points

Used as: Division-I, 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 non-zero 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: Division-II, 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 depth-first search (e.g., a flood fill). One can either do a DFS starting at the cell in question, or one can do a flood-fill from all of the edge cells (thus marking all the non-surrounded cells of a certain type at once).

PowerPlant (Value 500)
Used as: Division-I, 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 depth-first 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 ⁴⁸ 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: Division-I, 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 bit-set (e.g., an n-bit 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 n-bit integers (e.g., O(2ⁿn²), 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.

By Logan
TopCoder Member



	COMMENTS

Hey I noticed in the overview of problem set 105 that you guys mention creating an array of booleans for a-z 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