JOIN
 Match Editorials
TCHS08 Online Round 3
Saturday, January 26, 2008

## Match summary

The round started smoothly with very straightforward easy and a medium that also turned out to be not as medium as we expected. Zuza was the first to submit all three problems, but shortly he was overtaken by Loner and ahyangyi. Then, due to two resubmits on the hard he lost the spot in the top ten. After the coding phase, Loner, ahyangyi and yuhch123 were at the top. Unfortunately, ahyangyi's hard failes system test, so yuhch123 took his spot. v3ctor rounded up the top three with marcina007 and PaulDB being very close.

# The Problems

SimilarWords
Used as: Division One - Level One:
 Value 250 Submission Rate 96 / 97 (98.97%) Success Rate 95 / 96 (98.96%) High Score Zuza for 248.96 points (1 mins 50 secs) Average Score 232.81 (for 95 correct submissions)

This problem can be easily solved with brute force. We can iterate over all pairs of words and check their similarity. Computing similarity isn't much effort too. For each letter we just count how many times it appears in one word and how many times in the second one and we take the minimum of these two. The only catch may be the case insensitive comparison, but examples clarified this issue.

OneTwoThree
Used as: Division One - Level Two:
 Value 500 Submission Rate 89 / 97 (91.75%) Success Rate 85 / 89 (95.51%) High Score ahyangyi for 495.13 points (2 mins 49 secs) Average Score 386.96 (for 85 correct submissions)

What does it mean that number K is divisible by all the integers between 1 and n? It simply means that each prime factor of each number between 1 and n is also a prime factor of K. Assume that we are given a prime number p and we want to know the power it appears with in the smallest number that meets our criteria. Of course it will be the greatest a such that pa does not exceed n, as a greater power does not appear in any number between 1 and n. So we can simply iterate over all primes between 1 and n and compute their powers. The only issue here is not to overflow types. You can see a nice and clear implementation of the above in Zuza's solution.

RectanglesArrangement
Used as: Division One - Level Three:
 Value 1000 Submission Rate 37 / 97 (38.14%) Success Rate 25 / 37 (67.57%) High Score Loner for 914.64 points (8 mins 50 secs) Average Score 546.75 (for 25 correct submissions)

The key observation here is that we shouldn't change the initial order of the rectangles. Why? They are all the same, so we won't achieve anything clever by swapping them. So naturally, the first thing we should do is to sort the rectangles. The second thing we now for sure is that the first rectangle must have its left end an the square a. Now assume that we've covered squares from a to a + i, inclusive for some i using j first rectangles. What do we do next? We can try every position of the j + 1-th rectangle and see how many squares we can cover. So, using a simple dynamic programming algorithm we can compute the answer. See Loner's solution for a reference, as it's ideal implementation of the above idea.

By mateuszek
TopCoder Member