Problem Link :
Division 1
Division 2
Practice
Author : pekempey
Tester : Misha Chorniy
Editorialist : Anand Jaisingh
Pre-Requisites :
Properties of digital roots
Explanation :
Digital Sums and properties of digital sums may be common to some participants. Let’s establish 2 very important properties of digital sums required to solve this problem.
Let Dr(x) be a function defined for integer x as :
Dr(x)= x, if 0 \le x \le 9 ,
else
Dr(x)=Dr(Sum-of-digits(x))
This function Dr(x) is called the digital root of a number x. Now,
Dr(a+b) = Dr(Dr(a)+Dr(b)),
Dr(ab) = Dr(Dr(a)\cdot Dr(b))
These are well known properties, and you can find proofs of them here. It is very clear that the minimum value we are trying to find is a single digit number.
Claim 1 : : The minimum value is always the minimum over : Dr(N+kD) for some non-negative integer k.
Proof :
Dr(N+kD)=Dr(Dr(N)+Dr(kD)) ... (1)
Now, Dr(kd) = Dr(Dr(k) \cdot Dr(D)) .
Possible values of Dr(k) are 0,1,2...9 , given by numbers k=0,1,2...9
Now, Dr(x)=Dr(Sum-of-digits(x)) ... (2)
So, the minimum value for N is obviously equal to the minimum value for Sum-of-digits(N). Reducing the answer once and then adding D does not affect the minimum possible value that can be reached. If any any place, we have a reduce operation followed by an add operation, the we can do the add operation and then the reduce operation without affecting the possible roots we can reach. This is proved as a combination of formulae (1) and (2)
Doing a reduce operation followed by an add operation can be replaced by doing an add operation followed any further operations and we can still reach the same set of roots. In short, we can do all add operations first, all reduce operations later, and reach any number that can be possibly reached by any set of operations
So, using these two claims, we can prove the minimum possible value is the minimum of Dr(N+kD) where 0 \le k \le 9
Now, to find the minimum number of steps, we must first note that the relative order of the add and Sum-of-digits operations does affect the answer. However, we can note that the Sum-of-digits function is an extremely fast decreasing function.
Any number \le 10^{10} goes to a number \le 90, any number \le 90 goes to something \le 18 and so on. In short , any number can be reduced to its digital root in \le 3-5 steps.
Via this, we can prove that the value of the minimum steps can never be greater than 15. This is a loose upper bound, not the exact one. Let’s prove this via contradiction : If some process takes > 15 steps, we can always take N to the value of N+kD, k \le 9 that provides the minimum possible value, and then reduce it in 5-6 steps. Using this fact, we can now in-fact construct a brute force algorithm.
We can follow a complete brute force recursion algorithm, that at each step branches in 2 different directions, one x=Sum-of-digits(x), the other being x=x+D, but only until a recursion depth of 15. In this way, we stop after exploring 2^{15} different ways.
After reading all proofs mentioned above, understanding the code should be trivial. Also note that the greedy nature of this problem permits many other solutions too, and you can read about some of them using the comments below.
Overall time complexity O(T \cdot 2^{15} \cdot log_{10} N )
