Match Editorials

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

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++) 
            hs.add(a*b*c);
    return hs.size();
    }

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.

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.