Match Editorials

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

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 left-to-right or right-to-left. string.find() in C++ or String.indexOf() in Java can be used to check whether a word is found left-to-right in a row of the board. To check if it can be found right-to-left, 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 counter-clockwise. 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.

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(39-5, 5-4) / 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(n-m, m-x) / 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 brute-force 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 time-out.
Solutions with brute-force 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.

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?