Tuesday, March 6, 2007 Match summaryThe 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 ProblemsProductSetUsed as: Division One - Level One:
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(); }DigitMask Used as: Division One - Level Two:
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:
Used as: Division One - Level Three:
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. |
|