
Match Editorials 
TCHS SRM 57Saturday, September 20, 2008
Match summary
TCHS SRM 57 was easier than a typical TCHS SRM, with higher than 50% success rate in all 3 problems. More than 30 coders submitted all 3 problems, and 16 coders were able to get all 3 correct. The winner was v3ctor, who finished 3 problems within 20 minutes after the challenge started.
The Problems
WordFindPuzzle
Used as: Division One  Level One:
Value

250

Submission Rate

95 / 114 (83.33%)

Success Rate

73 / 95 (76.84%)

High Score

petar1 for 245.71 points (3 mins 46 secs)

Average Score

172.54 (for 73 correct submissions)

The problem itself is very easy and straightforward. You are given a few words (or possibly none) and a board. You are asked to find those words on the board. One tricky thing is that the word must be found both horizontally and vertically. Another is that the word can be reversed so that 'abc' can be found if there is 'cba' on the board, for instance.
To check if a word can be found horizontally on the board, we need to go through each row of the board and to check if a word can be found in the row lefttoright or righttoleft. string.find() in C++ or String.indexOf() in Java can be used to check whether a word is found lefttoright in a row of the board. To check if it can be found righttoleft, we can simply reverse the word and do the same thing.
Once a word is found horizontally, we now want to check if the word can also be found vertically. One trick is to rotate the given board by 90 degrees either clockwise or counterclockwise. Once the board is rotated, we can try finding a word horizontally on the rotated board so see if it were to be found vertically on the original board. In practice, it can be done by constructing a string object representing a column instead of row (which was given).
petar1's solution can be a good reference.
TwoLotteryGames
Used as: Division One  Level Two:
Value

500

Submission Rate

63 / 114 (55.26%)

Success Rate

55 / 63 (87.30%)

High Score

v3ctor for 496.84 points (2 mins 16 secs)

Average Score

396.83 (for 55 correct submissions)

In many countries, it is not rare to see lottery advertisements like 'choose 6 numbers out of 45 numbers, blah blah...' or 'take 5 numbers out of 39 numbers, blah blah...'. When you pass by the newsstand near your home, school, or work, you might compute the winning probability, from time to time.
In New York, USA, for instance, there is this lottery game called 'TAKE 5' where you choose 5 numbers between 1 and 39, inclusive. The winning probability (where you get all 5 numbers that will be chosen later) is easy to compute: 1 / Binom(39, 5) = 1 / 575757. Now there could be a second place where you get only 4 numbers correctly, and it is not very hard to compute. Out of 5 numbers that you choose, 4 numbers MUST BE chosen by the organizers and the other number MUST NOT BE chosen: Binom(5, 4) * Binom(395, 54) / Binom(39, 5) = 5 * 34 / 575757.
Now it can be generalized. the probability that you get exactly x numbers correctly is Binom(m, x) * Binom(nm, mx) / Binom(n, m). Thus, for the given problem, where it states 'at least k numbers', we can just sum up the probabilities for evrey x between k and m, inclusive.
See tkleczeksolution as a reference to this approach.
It is worth to note that this problem can be solved by bruteforce approach as well since n is small enough. Since there can be at most 8 numbers from which you can choose, you can try all possible combinations of m numbers chosen out of 1..n, inclusive. Without loss of generality, we can assume that the organizers will choose m numbers (1, 2, ..., m). Then, we can easily count the number of permutations that contain more than or equal to k numbers between 1 and m, inclusive. Take an example with n = 5, m = 3, k = 2. Then, there are 5C3 = 10 possible combinations:
(1, 2, 3) (1, 2, 4)
(1, 2, 5) (1, 3, 4)
(1, 3, 5) (1, 4, 5)
(2, 3, 4) (2, 3, 5)
(2, 4, 5) (3, 4, 5)
Out of these 10 combinations, there are only 7 combinations that contain 2 or more numbers between 1 and 3, inclusive:
(1, 2, 3)
(1, 2, 4) (1, 2, 5)
(1, 3, 4) (1, 3, 5)
(2, 3, 4) (2, 3, 5)
This approach will take roughly O(n!). n is fairly small so that this approach would not cause a timeout.
Solutions with bruteforce approach can be shorter than the classic binomial, probability approach. Because, at the end of the day, what we want to achieve during the competition is get a high score one each problem, you might better off writing a inefficient, short solution than a very elegant solution.
LostSortingAlgorithm
Used as: Division One  Level Three:
Value

1000

Submission Rate

35 / 114 (30.70%)

Success Rate

19 / 35 (54.29%)

High Score

v3ctor for 965.78 points (5 mins 23 secs)

Average Score

694.58 (for 19 correct submissions)

This problem came to my mind when I was in Decision Theory class. You are given a number of prioritized attributes and a list of objects represented by the attribute values. Can you sort all the objects such that the prioritization of attribute will not violated by any pair of two objects? This problem is too trivial for TopCoder members as it just involves a sorting algorithm. One question came to my mind: 'if you are given such sorted objects, could you recover the prioritization of the attributes?' It is a fairly easy question as long as the number of attributes is small, like in this problem LostSortingAlgorithm.
To solve this problem, you can try all permutations of attributes, and check if there is a conflict between two houses; alternatively, you can also sort the houses with the chosen permutation and check if newly sorted houses have the same order as the given list of houses  either way, n is fairly small. If you can find a successful permutation of attributes, you just return it. If you find more than one, report that there are too many possible ways. Otherwise, report that no permutation can make it  Helen must have sorted in the wrong way in this case.
See v3ctor's solution using this approach.
Question: if the number of attribute can be up to 15 and the number of houses up to 1000, can you find an efficient solution?