Match Editorial

Match summary

This single round match was realy lucky. Over 1000 of lucky coders, lucky problems, lucky time of the day (especially here, in Ukraine) and of course lucky numbers. What else do you need to have have fun during 100 lucky minutes of TopCoder competition?

Division 1 was won by young Ukrainian star Rizvanov_de_xXx who was able to get higher score than three targets and many other higher ranked coders. He was followed by Petr who took home silver medal again. Bronze this time went to Venezuela, to jbernadas. Those top tree coders of the event together with tomek and rem formed the quintet "We've solved all three problems this time".

Division 2 competition ends up with carlos.guia, asr and tzdin on the top three places.

The Problems

Value	250
Submission Rate	471 / 517 (91.10%)
Success Rate	368 / 471 (78.13%)
High Score	KnightOfTheSun for 249.16 points (1 mins 39 secs)
Average Score	208.46 (for 368 correct submissions)

This problem was realy lucky and everyone who opened it probably was feeling lucky to have such an oppotunity for warm up. Due to constraints all you had to do is just to iterate through all integers from n downto 1 and return the first lucky number. And I think that all of you enjoyed the part of checking whether some number is lucky or not.

Value	500
Submission Rate	343 / 517 (66.34%)
Success Rate	119 / 343 (34.69%)
High Score	jbnpaul for 493.35 points (3 mins 18 secs)
Average Score	327.78 (for 119 correct submissions)

Value	250
Submission Rate	408 / 429 (95.10%)
Success Rate	301 / 408 (73.77%)
High Score	UdH-WiNGeR for 249.54 points (1 mins 13 secs)
Average Score	204.20 (for 301 correct submissions)

The key thing in this problem is to observe that actually there are not so many lucky numbers between 1 and 1,000,000,000. More precisely there are 1022 such numbers in that interval. So one of the easiest way of solving this problem is to generate all lucky numbers below 1,000,000,000 and count how many of them are between a and b. Also during SRM there were implemented some fast and nice recursive solutions based on the same idea. Unfortunately brute force solutions timed out, so not everyone enjoyed this problem in fact.

Value	1000
Submission Rate	68 / 517 (13.15%)
Success Rate	15 / 68 (22.06%)
High Score	iliyafilippov for 788.77 points (15 mins 35 secs)
Average Score	569.02 (for 15 correct submissions)

If someone has counted all lucky numbers below 1,000,000,000, he or she can easily do the same for 1,000,000. The result is 126 (let's denote this number as m). Now we can construct DP solution that finds the smallest amount of lucky numbers needed to represent each integer between 1 and n. For each integer we will try each lucky number as a candidate for first one in a desired representation. Let Res[i] be amount of lucky numbers needed to represent i. Then Res[i] = min(Res[ i - lucky[j] ] + 1) for each j from 1 to 126, where lucky is an array of all lucky numbers below 1,000,000. Having such information calculated, we can easily construct the resulting array trying to take smallest possible lucky number on each step. The complexity of this DP solution is O(n*m) and it is just fine to fit in 2 seconds time limit.

Value	500
Submission Rate	292 / 429 (68.07%)
Success Rate	157 / 292 (53.77%)
High Score	crazyb0y for 457.15 points (8 mins 52 secs)
Average Score	294.14 (for 157 correct submissions)

Let's divide all sequences we are looking for into four classes. First class is the class of sequences that start with a lucky number that has 4 as the most significant digit and ends with lucky number that ends with 4. Let's denote this class (4, 4). Similarly we can define classes (4, 7), (7, 4) and (7, 7). Also let's denote the amount of distinct lucky numbers in numbers that starts with 4 and ends with 4 as lucky44. Similarly lucky47, lucky74, lucky77 are defined.

If we know the number of different sequences of length n for each class (Res44[n], Res47[n], Res74[n], Res77[n]), we can easily calculate those four numbers for sequences of length n+1. For example Res47[n + 1] = Res44[n]*lucky47 + Res47[n]*lucky77. Than the easiest part goes - just to implement these things. But wait. Don't you think that it's too easy for Div1 Medium? Actually there is one more problem - length is too big and you can fill a smell of time out. But after thinking a little bit more one can observe that this process can be represented as matrix multiplication. And well known algo of raising matrix to length power in O(log(length)) is just what you need to speed up your solution.

We have a 2x2 matrix A with lucky44 and lucky47 in the first row and lucky74 and lucky77 in the second one. In general, Aⁿ contains four numbers Res44[n], Res47[n], Res74[n], Res77[n]. And we need to raise A to the length-th power. How can we do it fast? It is easy to calculate the following row of matrices A, A², A⁴, A⁸, ... . Then we can represent A^length as a product of matrices from that row. The number of matrixes in the product will be equal to number of 1's in the binary representation of length. Due to this, there will be no more than log₂(length) matrices in the product.

And one more very interesting author's observation. I have seen several almost correct solution for this problem each having a following problem. Contestants just forgot to check if some element of numbers is lucky. They were considering only the first and the last digits for this purpose. So the conclusion is that you have to be very careful during SRM and to pay attention to each small thing of a problem.

Value	1000
Submission Rate	39 / 429 (9.09%)
Success Rate	10 / 39 (25.64%)
High Score	tomek for 654.58 points (23 mins 25 secs)
Average Score	556.17 (for 10 correct submissions)

At the first sight this problem is very similar to Div2 Hard, but with a little bigger constrains. Thus this two problems should have similar solutions. But unfortunately Div2 Hard solution is not good for this one. So we need to figure out something else.

Let's start thinking together. We have 1022 lucky numbers and an integer n to be represented as a sum of those lucky numbers. One can observe that if we can do this, we don't need more that 9 such lucky numbers. Let a proof of this fact be a lucky homework for you. Denote MAX = 9, N = 1022 and M = 9 (maximal number of decimal positions). Suppose we know how to calculate for an integer n the minimal possible amount of lucky numbers that sum up to n. Let's denote this knowledge as some function F(n). Than for each element in resulting array we can just iterate through all lucky numbers looking for the smallest appropriate one. It means that we are looking for the smallest lucky number m such that F(n) = F(n - m) + 1. After this we will set n = n - m and will be looking for the next element of resulting array, and so on.

Now we have to think about function F(n). Assuming the algo described above it should be quite fast. So how can we calculate minimal number of lucky summands for some integer n? Let's consider DP with three dimentions - amount of lucky numbers, decimal position, carry. DP[x][y][z] will give answer for a question if it's possible to represent m = (n div 10^y) - z as a sum of no more than x lucky numbers. Obviously, if DP[x-1][y][z] = true, then DP[x][y][z] = true. In other cases we have to use exactly x lucky numbers. At the current decimal position we don't care where we'll put 4's and where 7's. The only thing we have to consider is the number of 4's and the number of 7's. Their sum modulo 10 should be equal to m modulo 10 and if so we have to check DP[x][y + 1][(z + {sum of 4's} + {sum of 7's}) div 10].

The complexity of the described algo is O(MAX*N*M*MAX*MAX). So we don't need to worry about running time of the program. This algo is not very hard for implementing and it's working time is quite small. So the last thing you have to do is a homework. Enjoy.