Saturday, January 26, 2008 Match summaryThe 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 ProblemsSimilarWordsUsed as: Division One  Level One:
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. OneTwoThreeUsed as: Division One  Level Two:
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 p^{a} 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. RectanglesArrangementUsed as: Division One  Level Three:
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 + 1th 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.

