JOIN Match Editorial
2003 TopCoder Open
Qualification Round 1

Tuesday, October 7, 2003

Summary

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

MissingLetters  Used as: Division One - Level One:
 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;
}
```
Without the indexOf() and the toUpperCase() function, you could always initialize a boolean array with 26 elements, each of which represents whether or not a character is present. It would go like this (in C++ this time):
```   string getMissingLetters(string sentence){
bool present = {};
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;
}
```

Inserter  Used as: Division One - Level Two:
 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
```
Once you've found the proper position to do the insert, you can easily add <insert>, like this:
```   if(pos!=-1)
original=original.substring(0,pos)+insert+original.substring(pos);
```
That's pretty much it, you just run through all of the commands, tokenize them, do the insert, and then return the modified original string at the end:
```   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;
}
```

Rooms  Used as: Division One - Level Three:
 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
```
Translating this into code is a bit of work, but the parsing is relatively straightforward, and there aren't really any special tricky cases to worry about. By lbackstrom
TopCoder Member 