JOIN
 Match Editorials
TCHS07 Round 1 Delta
Tuesday, March 6, 2007

## Match summary

The early rounds of the TCHS Tournament have two distinct characteristics. The first is that many coders carefully test their submissions to the easy problem to make sure they obtain seats in the next round. The second characteristic is that the top competitors strut their stuff, to show they mean business in later rounds. As a result, there was a 96.15% success rate on the easy, and ahyangyi took first place by over 300 points. Problem solutions follow.

# The Problems

ProductSet
Used as: Division One - Level One:
 Value 250 Submission Rate 26 / 26 (100.00%) Success Rate 25 / 26 (96.15%) High Score hupo001 for 248.13 points (2 mins 28 secs) Average Score 232.02 (for 25 correct submissions)

Using three for-loops we can quickly generate all elements of the described set. The only issue is accounting for duplicates, and this can be done by marking an array, or by using some kind of set data structure. Java code follows:

```    public int howMany(int[] lows, int[] highs) {
HashSet<Integer> hs = new HashSet();
for (int a = lows[0]; a <= highs[0]; a++)
for (int b = lows[1]; b <= highs[1]; b++)
for (int c = lows[2]; c <= highs[2]; c++)
return hs.size();
}
```

Used as: Division One - Level Two:
 Value 500 Submission Rate 23 / 26 (88.46%) Success Rate 14 / 23 (60.87%) High Score ahyangyi for 469.45 points (7 mins 20 secs) Average Score 370.51 (for 14 correct submissions)

In this problem we must determine if the given patterns are consistent, and if so, return the number of matching strings. Since the required string length L is given, we can initialize a character array to contain L question-marks. Each pattern we encounter will lead to one of the following:

• The length of the pattern doesn't agree with L, so we return 0.
• The pattern forces some positions of the array to be particular digits.
• The pattern gives no information.
If two patterns force different digits in a given position, then we can immediately return 0. Otherwise, we process all the patterns, and count how many question-marks remain. Each contributes a factor of 10 to the return value.

WordConnect
Used as: Division One - Level Three:
 Value 1000 Submission Rate 13 / 26 (50.00%) Success Rate 5 / 13 (38.46%) High Score ahyangyi for 767.39 points (16 mins 44 secs) Average Score 600.47 (for 5 correct submissions)

In this problem, a fairly quick precomputation can make most of the work go away. We construct two arrays of booleans, fromStart and fromEnd, which have one entry per table character. fromStart will mark all positions that can be reached by spelling out a prefix of the given word ending on that position. fromEnd will mark all positions that can be reached by spelling out a prefix of the reverse of the given word ending on that position. Both of these arrays can be populated using dynamic programming: mark all positions where the first letter of the word occurs, then all second letters adjacent to first letters, and so forth.

Having these two arrays will allow us to solve the problem with a simple flood-fill. We loop over the entire table of characters. If we find the first letter of the given word and it is marked in fromStart, then we flood-fill, coloring all connected positions. This is possible, since at each position we know whether it can be used to start or finish a word, and whether each neighbor can be used to start or finish a word. Having colored each component with a different color, a final loop over the table can determine the number of components.

By brett1479
TopCoder Member