
Match Editorial 
SRM 136Tuesday, February 25, 2003
Match summary
Yarin remained red hot, as only one of two coders (radeye was the other) to solve all three problems
successfully. His hot streak over the last few challenges has propelled him up to 2nd place overall,
58 points behind John Dethridge. SnapDragon, on the other hand had an unusual off night, and dropped 124
points.
The div 2 problems were a little on the easy side, with over 50% of submissions being correct
for all three problems. The div 1 easy and medium problems were quite well balanced, and most people had
little trouble with the easy. The hard on the other hand, was quite difficult, even though it turns out
that the algorithm involved is relatively simple once someone is kind enough to share it with you.
The Problems
Datatype
Used as: Division 2  Level 1:
Value  250 
Submission Rate  164 / 183 (89.62%) 
Success Rate  102 / 164 (62.20%) 
High Score  JWizard for 243.05 points 
Basically, just look at every character, and classify the string. There are a number of useful functions that can
make this even easier. Regular expression, for example, are perfect here:
if(var.matches("[09]*"))return "INTEGER";
if(var.matches("[09]*\\.[09]*"))return "DECIMAL";
if(var.toLowerCase().matches("falsetrue"))return "BOOLEAN";
return "STRING";
MemberCheck
Used as: Division 2  Level 2:
Value  500 
Submission Rate  129 / 183 (70.49%) 
Success Rate  93 / 129 (72.09%) 
High Score  JWizard for 473.45 points 
Used as: Division 1  Level 1:
Value  250 
Submission Rate  145 / 149 (97.32%) 
Success Rate  135 / 145 (93.10%) 
High Score  venco for 248.21 points 
The input here is small enough that runtime is no issue. So, the simplest way to do it is to loop through all
people that go to club 1, and see if any of them also went to clubs 2 or 3. Then, you can check all of the
people who went to club 2 and see if any of them also went to club 3. You have to be careful not to repeat the
elements in the return, but this isn't that difficult, and you can just scan all the dishonest people you have
found so far, before adding a new one.
BowlSim
Used as: Division 2  Level 3:
Value  1000 
Submission Rate  82 / 183 (44.81%) 
Success Rate  62 / 82 (75.61%) 
High Score  kbscores for 926.96 points 
The input is ensured to be a complete game, so there is no need to worry about going out of bounds or anything
like that. So, what we want to do is calculate the score of each frame independently. There are three cases to
consider here: a strike, which takes only one attempt, a spare which takes two attempts, and a normal frame which
takes two attempts. Since we know there are exactly 10 frames, we can do something like this:
int ptr = 0;
int score = 0;
for(int frame = 0; frame<10; frame++){
if(pinsDown[ptr]==10){//STRIKE
score = score + pinsDown[ptr] + pinsDown[ptr+1] + pinsDown[ptr+2];
ptr = ptr + 1;
}else if(pinsDown[ptr] + pinsDown[ptr+1] == 10){//SPARE
score = score + pinsDown[ptr] + pinsDown[ptr+1] + pinsDown[ptr+2];
ptr = ptr + 2;
}else{//NORMAL
score = score + pinsDown[ptr] + pinsDown[ptr+1];
ptr = ptr + 2;
}
}
Cribbage
Used as: Division 1  Level 2:
Value  500 
Submission Rate  102 / 149 (68.46%) 
Success Rate  52 / 102 (50.98%) 
High Score  antimatter for 404.30 points 
No single part of this problem is particularly difficult, but when you put it all together, there are so many
cases and things to remember that it is easy to miss one of them. There are 5 different ways to score:
fifteens, pairs, runs, flushes, and his nobs. Pairs can be counted easily by examining all pairs of cards to
see if they are the same. Fifteens can be done in a couple of ways. A brute force approach to this will work,
as there are only 2^5 combinations of cards. Another way to do this is to use a little bit of simple dynamic
programming, but either way works just as well as the other. Runs are probably the hardest to check, because
we have to be careful not to count a run if another run is longer and uses the same cards. A brute force
approach would work here also. We can keep a set of runs found so far, and if a run is super set of a run
already found, remove the previous one, and if a run is a subset of a run already found, don't add it. A
number of other methods will also work, including recursion, or brute forcing over all possible runs that a
hand might have. Flushes are pretty simple, as they always involve cards 1 through 4. We just have to check if card 0 is also part of a flush, and add 1 if it is. Last, and least, is his nobs. Simply check all the cards but the starter to see if they are jacks of the same suit as the starter.
PrefixSynchronization
Used as: Division 1  Level 3:
Value  1000 
Submission Rate  5 / 149 (3.36%) 
Success Rate  2 / 5 (40.00%) 
High Score  Yarin for 694.29 points 
This deals with an interesting problem that actually comes up in some situations. If you are transmitting
binary data, in a variable length code, like a Huffman code, a transmission error (a 1 instead of a 0 or
vice versa) can have drastic consequences for the transmission of future data. A synchronization code is a
sequence of bits that guarantees the transmitter will become resynchronized with the receiver. The solution to
this problem turns out to be remarkable simple, but it is far from obvious that it will work. First, we want
to define a state space that we can search. In this case, we will define our state to be the set of positions
that the receiver might be at, in each of the code words. Thus, our initial state will be that the receiver can
be in any position in any string. Then, we want to do a standard breadth first search of our state space, and try
to find a state where the only position that we can be at is the beginning of a code word. To do this, we start
with an empty string, that is associated with the initial state. Then we add a 0 or a 1 to the empty string,
and see which of the positions in our start state are invalidated (all those which don't expect a 0 or a 1 
whichever we added  to be the next bit). We add the states reached by adding a 0 or 1 to a queue, and then
successively add bits to the strings, generating new states. The key to making this run in time is to cache the
states so that we never add more than one string which leads to the same state into our queue.
It isn't at all obvious that this approach will work because the state space is potentially very large  greater
than 2^30. However, it turns out that the most states you will even have to examine is less than n^2, where
n is the number of code words. Don't ask me why this is true, but after 2 days of testing random codes,
none of them required more than n^2 states.
Another interesting thing to note about this problem is that most Huffman codes have a synchronizing sequence,
and in fact most codes like this turn out to be "selfsynchronizing". In other words, even if there is a
transmission error, the receiver will usually (though not always) get back on track and start receiving the
proper data again. This fact has been used in fax machines which send data over noisy phone lines.
#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
class PrefixSynchronization {
public:
string shortest(vector <string> codewords) {
int len = codewords.size();
vector<int> pos;
for(int i = 0; i<len; i++){
pos.push_back(0);
for(int j = 0; j<codewords[i].size(); j++)
pos[i] = 1<<j;
}
vector<vector<int> >queue;
vector<string> seq;
vector<int> length;
map<vector<int>,int> cache;
queue.push_back(pos);
seq.push_back("");
int h = 0;
while(queue.size()!=h){
vector<int> p = queue[h];
for(char ch = '0'; ch<='1'; ch++){
vector<int> n;
bool start = false;
bool done = true;
for(int i = 0; i<len; i++){
n.push_back(0);
for(int j = 0; j<codewords[i].size(); j++){
if((p[i] & (1<<j)) && codewords[i][j]==ch){
if(j+1==codewords[i].size()){
start = true;
}else{
done = false;
n[i] = 1<<(j+1);
}
}
}
}
for(int i = 0; i<len && start; i++)n[i] = 1;
if(!cache[n]){
cache[n] = 1;
queue.push_back(n);
seq.push_back(seq[h] + ch);
if(done){
int t = seq.size()1;
cout << t << endl;
return seq[t];
}
}
}
h++;
}
return "NONE";
}
};
By
lbackstrom
TopCoder Member