MINDSUM - Editorial

editorial
, , ,
21

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

2 Likes
22

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

23

wooooh…nice :slight_smile:

24

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

25

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?

26

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

27

@ayush743209 Could you please explain your logic ?

28

My solution (very simple one) : https://www.codechef.com/viewsolution/20612025

29

@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.

30

https://www.icwmachine.net

31

@ayush743209

at

1

1 1

your output is (1,1) , It should be (1,0 ), because we are not doing any operation here , number itself is the minimum one.

I hope it will help you :slight_smile:

32

@sm1dash (sorry, I don’t have enough rep points to comment directly below your post) –

Your code ( Link ) doesn’t actually traverse a tree, which is the essential requirement to solve the problem.

Here’s the key section, lines 32-41 and 46:

		dval=n;
    	while (dval > 9)
		{
			dval=digitSum(dval);
			op2++;
		}
		if (!result[dval])
		{
			result[dval]=op+op2;
		}
...
		n += d;

As you know, the while loop takes the current value of n and iterates digitSum() repeatedly until a value <= 9 is found. Then if you haven’t already come across that value (i.e. if !result[dval]), you store the number of steps. Then in line 46 you increase n by d and continue to the next pass in the loop.

The problem is that digitSum(n + k · d) (for some k, 0≤k≤9) is not always the shortest solution, which is why a binary tree is needed. At each fork point, your options are to add d to the current value, or apply digitSum() to the current value. This leads to 2^x possibilities, where x is max-number-of-steps. Your loop just covers 10 possibilities.

33

Digital root is not just n \bmod{9}, see my answer https://discuss.codechef.com/questions/137819/mindsum-editorial/137857

34

In the editorial it’s mentioned that the relative order of the add and sumofdigit() operations does matter! Could you please give me one testcase where this matters? My code didn’t take this into account and thus i failed 4 out of 8 tasks -> https://www.codechef.com/viewsolution/20638982

35

Thank you @sbatten1969 for identifying my mistake.

1 Like
36

https://www.codechef.com/viewsolution/21684791
Can any one tell me where is my logic wrong.

37

what is it with 2047. I read a few codes of people and many have used i<2047. Can anyone please tell me. Like in this solution:
https://www.codechef.com/viewsolution/21049456 (this is not my code)