MINDSUM - Editorial

[anand20]

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

[pavitra_ag]

I solved this question using bfs on a binary tree

[meet2mky]

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

[sbatten1969]

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?

[algmyr]

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

[garrykevin]

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

[ysumit99]

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

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

Anyone where am I going wrong?

[mr_cyborg]

I did it using Complete Binary Tree.

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

[kshreyans_1]

Please explain the logic behind the binary tree approach.

[mr_cyborg]

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

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

[relaxedrn18]

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

[sshhhh]

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 ) So just iterate over all 2^13 cases possible using bitmask technique and find minimum of all .

[code_report]

Video solution with explanation: https://youtu.be/vJ9LF0h-N1g

[sm1dash]

Can anyone help me with my code.I have implemented the logic correctly but still only two test cases are getting passed on submission.

Code Snippet

[dibbu]

While I have understood the logic of the problem, my solution is still giving WA after multiple attempts.

#include<bits/stdc++.h>
using namespace std;

long long int a[10000000];

int digisum(long long int num)
{
int sum = 0;
while(num != 0)
{
sum += num % 10;
num /= 10;
}
return sum;
}

int solve(long long int n, long long int d, long long int minim)
{
if(n == minim) return 0;

int i; memset(a,0,sizeof(a));
a[0] = n;
for( i=1; ; i+=2)
{
    a[i] = a[(i-1)/2] + d;
    a[i+1] = digisum(a[i/2]);
    if(a[i] == minim || a[i+1] == minim)
        break;
}
return floor(log2(i+1));

}

int main()
{
int t;
scanf("%d", &t);
while(t–)
{
long long int n,d;
scanf("%lld%lld", &n, &d);
d = d % 9;

    if(d == 0)
    {
            int i = 0;
            long long int temp = n;
            while(temp >= 10)
            {
                temp = digisum(temp);
                i++;
            }
            printf("%lld %d\n", temp, i);
    }
    else if(d == 3 || d == 6)
    {
        long long int temp = n;
        while(temp >= 10)
        {
            temp = digisum(temp);
        }
        if(temp - 3 > 0) temp -= 3;
        if(temp - 3 > 0) temp -= 3;

        int level = solve(n, d, temp);
        printf("%lld %d\n", temp, level);

    }
    else
    {
        int level = solve(n, d, 1);
        printf("%d %d\n", 1, level);
    }
}
return 0;

}

Please help me figure out where the fault exists in my code. Thanks in advance

[ruddradev]

Argghh this question made me pull out at least 100 hairs from my head. I can now see a bald spot that I can safely attribute to MINDSUM. What a great problem. It has a greedy approach that passes most of the test cases, but fails at a select few. I threw hundreds of test cases at it, and it passed (The same greedy approach many others also took) One where it fails was 2 82.

To top it off, it has another elegant solution that can be solved in multiple ways. Hats off to the setter.

Follow up question: Can you please explain how to solve the first subtask?

[ayush743209]

My solution got WA on some cases:
https://www.codechef.com/viewsolution/20934792
what is wrong with this solution??

[mr_cyborg]

@ayush743209 Could you please explain your logic ?

[utkarsh911]

My solution (very simple one) : CodeChef: Practical coding for everyone

[ayush743209]

@mr__cyborg,for a given n we know that digits will start repeating after certain time.
I first calculated the digitsum of n and stored the number of operation for that particular digit in an array.
then added d to n and did the same thing as above till the digits started repeating and then i printed the minimum number with its number of operation.