Match Editorial

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

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("[0-9]*"))return "INTEGER";
    if(var.matches("[0-9]*\\.[0-9]*"))return "DECIMAL";
    if(var.toLowerCase().matches("false|true"))return "BOOLEAN";
    return "STRING";

Value	500
Submission Rate	129 / 183 (70.49%)
Success Rate	93 / 129 (72.09%)
High Score	JWizard for 473.45 points

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.

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;
   }
}

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.

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 "self-synchronizing". 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";
}
};