Match Editorials

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

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.

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 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.

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.