MINDSUM - Editorial

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 )

Tester’s Code : : Link

My Code : : Link

2 Likes

I solved this question using bfs on a binary tree

1 Like

That will be very good to learn about digital roots btw solved with bfs. Thanks for adding one more concept! :slight_smile:

Thanks for posting this editorial. A couple of things I’m not following…

Regarding sum-of-digits function, you write:

> In short , any number can be reduced to its digital root in ≤5−6 steps.

Isn’t the max number of steps 3? Is there an x between 1 and 10^10 that reduces in 4 steps?

(For all x between 1 and 10^10, the maximum result of step 1 is 10x9, i.e. a 2-digit number. For all two-digit x between 1 and 99, the maximum result of the second step is 18. For all x between 1 and 18, the maximum result of the third step is 9.)

Nit pick:

> Any number ≤10^10 goes to a number ≤99

While that’s a true statement , isn it a number ≤90? Is there an x between 1 and 10^10 that reduces to 91-99?

1 Like

Some things I feel like mentioning.

Computing digital root in O(1)

You can compute the digital root in O(1). The digital root turns out to be essentially n%9

DR(n) = \begin{cases} 0 & \text{if $n=0$} \\ 9 & \text{if $n\neq0$ and $n\equiv0\pmod{9}$} \\ n \bmod 9 & \text{if $n\not\equiv0\pmod{9}$} \end{cases}

or as a neat but somewhat hard to read expression n%9 + (n%9<1)*9 (works in python, C, C++ and a lot of other languages).

The 2^{15} scaling is unnecessary

If you do BFS and split the current value x into the two cases \text{dsum}(x) and x+d you’ll find your answer visiting at most 2^\text{answer} states.

Actual complexity using BFS

The time complexity is O(\sum_{n,d} \log_{10}{N}\times2^{\text{answer}(n,d)}) and considering that the typical answer is way smaller than 15 this is way smaller than the complexity given in the editorial. In a worst case sense the above complexity can be written a bit more neatly as O(T \times \log_{10}{N}\times 2^{\max(\text{answer})}).

5 Likes

Btw Isn’t time complexity of / and % logn. Does faster than method extended gcd or binary search exist ?

For large integers you’re right. Large integer division in python for example has complexity is something like O(\log{n}^2). For small integers (in this context 32-bit or 64-bit numbers) we can view this as a constant cost (albeit expensive compared to addition or multiplication). In this case we have comparatively small (10^10 fits easily into 64-bits) numbers.

@algmyr if possible could u please explain your solution/approach for tree walk?

I also wanted to know. Opened your soln but was unable to understand.

@vivek_1998299 I won’t go into full detail here. The Berlekamp-Massey algorithm can be used to find the shortest linear feedback shift register that fits a sequence. For this purpose, think of finding k coefficients c_i of a relation a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{a-k} such that the relation recreates a given sequence. When the sequence has been found you can rather quickly find the nth term.

So essentially, simulate for a bit, throw the result into Berlekamp-Massey and extrapolate. Here I ignore some pitfalls, but it’s the essential idea.

3 Likes

My idea is to find the digital root by mod 9 for n.

I do this 9 times by adding d to n and find the min Dr(),then I find the number of steps need to reach the minimum digital root.

Where am I going wrong.Thanks in advance :).

solution

made some changes, thanx

My solution fails on test cases 2,3,4,7.

https://www.codechef.com/viewsolution/20615312

Anyone where am I going wrong?

I did it using Complete Binary Tree.

https://www.codechef.com/viewsolution/20905059

Thanx a lot!!! @algmyr

Please explain the logic behind the binary tree approach.

https://www.codechef.com/viewsolution/21120591

I have added the comments . You can check for the logic .
I hope this will help you.

@admin is it possible for you to share the test cases of this problem??

Check out this bad boy https://www.codechef.com/viewsolution/20625678 :slight_smile:

1 Like

I made a very important observation in this question , i.e. the max number of steps required is 11 .(I kept 13 in my code just for safety :slight_smile: ) So just iterate over all 2^13 cases possible using bitmask technique and find minimum of all .