Match Editorial

The first competition of the 2003 TopCoder Open sponsored by Intel^® came off pretty smoothly, with 3 relatively easy problems and 621 competitors. In fact, 140 out of the 621 people solved all 3 successfully. In order to advance to the next round of the TCO, you needed to get at least 590 points tonight, which amounted to solving the easy and medium problems pretty quickly (in around 25 minutes). In this competition, the strategy pioneered by dmwright of skipping the medium problem might have made sense for some coders, since solving the easy and hard problem all but guaranteed you would make the cut. Only 3 out of 157 coders who solved both the easy and the hard did not have enough points to advance from those two problems alone.

Two relative new comers, mathijs and snewman, took first and second, respectively, each in his second competition. snewman was leading the round going into the challenge phase, but mathijs was able to find two bits of bad code, and gained 100 points, edging out snewman by a meager 14 points. wleite rounded out the top three, 32 points behind mathijs. The top three rated coders going into this match - ambrose, zoidal and Joe - all ended up advancing with respectable scores, so no surprises there.

The Problems

Value	250
Submission Rate	589 / 629 (93.64%)
Success Rate	541 / 589 (91.85%)
High Score	coachbudka for 249.56 points (1 mins 11 secs)
Average Score	221.79 (for 541 correct submissions)

There are a couple of ways to go about this problem. If you know a little bit about your language's string library, you can do something like this (shown here in Java):

   public String getMissingLetters(String sentence){
      String s = sentence.toUpperCase();
      String ret = "";
      for(char c = 'A'; c<='Z'; c++){
         if(s.indexOf(c)==-1)ret+=c;
      }
      return ret;
   }

   string getMissingLetters(string sentence){
      bool present[26] = {};
      for(int i = 0; i<sentence.size(); i++){
         if(sentence[i] >='A' && sentence[i] <= 'Z'){
            present[sentence[i]-'A'] = true;
         }else if(sentence[i] >='a' && sentence[i] <= 'z'){
            present[sentence[i]-'a'] = true;
         }
      }
      string ret;
      for(int i = 0; i<26; i++){
         if(!present[i]){
            ret.push_back((char)(i+'A'));
         }
      }
      return ret;
   }

Value	500
Submission Rate	488 / 629 (77.58%)
Success Rate	387 / 488 (79.30%)
High Score	RaginAzn for 471.30 points (7 mins 5 secs)
Average Score	316.96 (for 387 correct submissions)

Again, familiarity with the string operations in your language makes this problem a lot easier. For each element of commands, you first tokenize the command into two strings - <insert> and <before> - and an integer, <index>. Then, you should go through the working string (which starts out as original) and find the proper occurrence of <before>. This can be done best with the indexOf method in Java (find() in C++). In Java, finding the position of the correct occurrence of <before> goes like this:

//initialize the index of the occurrence to -1 so that we search 
//from character 0 the first time
   int pos = -1;
//loop up to index times, each time finding the next 
//occurrence of before
   for(int j = 0; j < index; j++)
   {
//set pos to the position of the next occurrence of before,
//starting one character after the current position
      pos = original.indexOf(before, pos+1);
//if pos is -1, there are no more occurrences, so break out of 
//the loop
      if(pos==-1)break;
   }
//here, pos is either the position of the correct occurrence of 
//before, or else it is -1

   if(pos!=-1)
      original=original.substring(0,pos)+insert+original.substring(pos);

   public String insert(String[] commands, String original)
   {
      for(int i = 0; i<commands.length;i++)
      { 
         StringTokenizer st = new StringTokenizer(commands[i],"#");
         String insert = st.nextToken();
         st.nextToken();
         String before = st.nextToken();
         int index = Integer.parseInt(st.nextToken().substring(1));
         int pos = -1;
         for(int j = 0; j < index; j++)
         {
            pos = original.indexOf(before, pos+1);
            if(pos==-1)break;
         }
         if(pos!=-1)
            original=original.substring(0,pos)+insert+original.substring(pos);
      }
      return original;
   }

Value	950
Submission Rate	231 / 629 (36.72%)
Success Rate	160 / 231 (69.26%)
High Score	snewman for 876.36 points (8 mins 22 secs)
Average Score	560.26 (for 160 correct submissions)

This problem was a weakly disguised non-deterministic finite automaton (NFA), a data structure commonly used in a number of algorithms. Regular expressions, in particular, make heavy use of NFAs. In this problem, you have a "maze", and there are a number of "time steps" each of which corresponds to a single letter, and tells you which "doors" are open between which "rooms". The maze is analogous to an NFA, the letters represent the input to the NFA, the rooms represent states, and the doors represent state transitions. If you want to read a little more about NFAs, you can probably find out all you ever wanted to know with your favorite search engine. On to the problem:

We start with a boolean array, each of whose elements represents whether or not we can be in a certain room. We initialize all values to false, and then set the element corresponding to start to true. Then, we look at each character in doors, starting from the first. We then initialize another boolean array, each of whose elements represents whether or not we can be in a certain room at the next time step. Now, for each room that we could be in at the previous time step, we see which rooms we can go to at the current time step, given the current letter. We then set the corresponding elements of our boolean array, and move on to the next character of doors. So, we can come up with the following pseudocode to calculate which rooms we can be in after all :

bool pos[lengthOf(rooms)];
pos[start] = true;
foreach character c in doors
   bool next[lengthOf(rooms)];
   for i = 0 to lengthOf(rooms)-1
      if(pos[i])
         for j = 0 to lengthOf(rooms)-1
            if(door from i to j is open on c)
               next[j] = true;
            end if
         end for
      end if
   end for
end for
//return an int array each of whose elements is one a 'true' in pos