PROBLEM LINKS:
DIFFICULTY:
Hard
PREREQUISITES:
EXPLANATION:
It is clear that each positive integer with at most 3 non-zero digits is Cool Number. Let’s call such Cool Numbers - Trivial Cool Numbers (TCN). Other Cool Numbers will be called Non-trivial Cool Numbers (NTCN). Take a few examples:
100230: TCN
189000: TCN
901205: NTCN
9999: NTCN
100000000: TCN
Let’s denote the sum of selected digits by D and let S be defined as (sum of all digits – D) i.e. sum of unselected digits. Let’s first find an upper bound on S. Suppose N contains K digits in all. Then the maximum value of S can be 9(K-1) i.e. S<= 9(K-1). This happens when we select only one digit and the rest of the K-1 digits are all 9. Also, the maximum value of D can be (9x3) i.e. D<=27 (when we select 3 digits and all of them are 9). This means that SD can have a maximum value of (9(K-1))27. We know that for any NCTN we have S>0 and N will divide SD. Since N divides SD it is obvious that N<=SD. Also, we saw that N has only K digits. This means N >= 10(K-1)
This brings us to the following set of inequalities:
10(K-1) <= N <= SD <= (9(K-1))27
Since logarithm is a monotonously increasing function, we can apply log to this set of inequations. By taking logarithm(base 10), we get:
(K-1) <= 27log(9(K-1))
Solving this we can see that K<=77. Thus we will never have to deal with numbers which have more than 77 digits. Thus, the upper bound of S is 9x(77-1) = 684.
The main idea of the solution is to calculate and store all the NTCN’s in a sorted order so that we can easily search for the required number using binary search. So far we have only talked about NTCN’s. We should not forget that TCN’s are also the candidates for our final answer. Our final answer for N will be:
LC(N) = max(Trivial LC(N), NonTrivial LC(N))
UC(N) = min(Trivial UC(N), NonTrivial UC(N))
NonTrivial LC(N) and NonTrivial UC(N) can be found out by binary search on the list of NTCN’s.
Now let’s discuss how to find Trivial LC(N) and Trivial UC(N). This can be easily done in O(K) where K is the number of digits in N. It’s obvious that TLC(N) can be formed by keeping the first 3 non-zero digits intact and converting all the digits to it’s right to 0. If there are already <=3 non-zero digits, then that number itself is the TLC(N). For example,
N TLC(N) 1012341 : 1012000 1000 : 1000 8790000 : 8790000 23000023 : 23000020
Finding TUC(N) isn’t as straightforward as the above method. There are several cases we need to consider. If the number has atleast 3 non-zero digits, keep the first 3 non-zero digits and replace all other digits by 0. Now, increase the 3rd non-zero digit by 1. We have several cases in this case itself.
For example,
N T_UC(N)
1289123 : 1290000
2309808 : 2310000 (you cannot increase 9)
1002900 : 1003000 (mostly the same as the previous but can cause additional WA)
1009900 : 1010000 (2 9's in a row)
999000 : 1000000 (3 9's in a row)
Next comes the case when there are less than 3 non-zero digits. In such a case, TUC(N) = N+1.
For example, TUC(100080) = 100081.
So all these cases can be taken care of in O(K) and we get both TLC(N) & TUC(N). Now let’s try and find out a way to find the NCTN’s. The two solutions given below do it in different ways.
SETTER’S SOLUTION:
Can be viewed here.
APPROACH:
As discussed above, the maximum value of S can be 684. We can see that S can’t have more than 4 distinct prime factors. This is because even 5 of the smallest distinct prime factors give a product of more than 684 i.e. 2 * 3 * 5 * 7 * 11 > 684. Hence, we know that S will have <= 4 prime factors. So for now we should check only those numbers whose radical is no more than 684. To do this, our pseudocode will look something like this:
for(i=2;i is prim and i<684; ++i)
for(poweri=1;i^poweri<10^77;++poweri)
{
candidate_num=i^poweri
check this candidate is it cool
for(j=i+1;j is prim and i*j<684; ++j)
for(powerj=1;i^poweri*j^powerj<10^77;++powerj)
{
candidate_num=i^poweri*j^powerj
check this candidate is it cool
for(k=j+1;k is prim and i*j*k<684; ++k)
for(powerk=1;i^poweri*j^powerj*k^powerk<10^77;++powerk)
{
candidate_num=i^poweri*j^powerj*k^powerk
check this candidate is it cool
for(t=k+1;t is prim and t<684; ++t)
for(powert=1;i^poweri*j^powerj*k^powerk*t^powert<10^77;++powert)
{
candidate_num=i^poweri*j^powerj*k^powerk*t^powert
check this candidate is it cool
}
}
}
}
To know how to check if a number is cool or not, please refer to the tester’s approach.
Clearly, the above procedure take a lot of time. So we try to “hack” the solution in such a way that it runs in time. The approach taken by the setter in this solution is to divide the solution into two parts: fast calculation of a portion of Cool Numbers, and stored Cool Numbers. A few hacks are introduced into the solution in such a way that the program runs in time. But to do this, we sacrifice calculating a few Cool Numbers. The missed out cool numbers which can’t be calculated are stored in some container. This process can be achieved by running a brute force program on your maching and calculating all the cool numbers and storing them in a file. Then we run our hacked program and see which all cool number we can generate. After comparing with the previously generated list of all cool numbers, we get to know which numbers cannot be generated. Such numbers are stored in a container.
The hacks can be of a lot of types. The setter used the following hacks to improve the runtime of his code:
- calculate only those numbers which have <= 3 divisors
- calculate only those numbers which have <= 60 digits
- calculate only those numbers whose radical <= 260
The rest of the “ungenerated” numbers are stored manually inside an array. Now, we can have the list of all the cool numbers during the program run. Now, we have both the NTCN’s and we know to calculate the TCN’s. We can easily get the answer as mentioned earlier.
TESTER’S SOLUTION:
Can be viewed here.
APPROACH:
In this solution, let’s fix S and try to find all NTCN for which we can select at most 3 digits with sum of the remaining digits equal to S such that our NTCN divides SD. Since D<=27, we simply iterate over divisors of S27 and check for each divisor. Let’s look into it in more detail.
It is obvious that generating the divisors of S27 for all S will give us all the NTCN’s. Note that we are only talking about NTCN’s because the upper bounds we got was only for NTCN’s.
We can factorize S into prime factors. Suppose S = Aa x Bb x Cc. Then S^27 will be equal to A27aB27bC27c. Now we can generate all the divisors, Ai BjCk using simple recursion and satisfying the conditions 0<=i<=27a, 0<=j<=27b and 0<=k<=27c. The pseudocode of such a function can look like:
generate(index_of_factor, divisor) { // check for Coolness of divisor here for i = 0 to max_power_of_factor[index_of_factor] divisor *= factor[index_of_factor] generate(index_of_factor + 1, temp) }
It is clear that these numbers can be quite large. To handle these, use a BigInt Class. For a better and faster implementation of handling these large numbers, please go through the tester’s code. It is interesting to note here that S cannot have more than 4 distinct prime factors. This is because the product of even the least 5 primes (2,3,5,7,11) exceeds the maximum value of S(684). Thus we can safely assume that there won’t be more than 4 distinct prime factors. Now once we have all the divisors, we check if each divisor is an NTCN or not. Suppose we are checking for a particular value of S = s. And the divisor we are considering for it is div. Let sum be defined as the sum of all the digits in div. This implies that d = sum – s. Thus, the sum of selected digits comes out to be sum – s. If div is an NTCN, there must be a group of at most 3 digits in d whose sum is equal to d. If we find such a group, we can say that div is a cool number and add it to the set of NTCN’s. We perform these calculations for all values of S (<=684). And finally we have all the values of NTCN’s in our hand. These operations can be performed and the numbers can be pre-calculated.
Now arriving at the answer is very easy. For any given value of N, we perform a binary search on the array of stored NTCN’s as we showed and get the candidates for NTLC(N) and NTUC(N). And as we showed earlier, we calculate the values of TLC(N) and TUC(N) in O(K) time. Once we have all the 4 values, we calculate the values of LC(N) and UC(N) as shown earlier.
