MULTHREE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY:

easy

PREREQUISITES:

modulo cycle, basic math

PROBLEM:

The key idea behind the solution is the fact that the digits start to repeat after some time in a cycle of length 4.
Firstly, we will find the sum of all the digits and then check if it is divisible by 3 or NOT.

Sum of digits -

We know d_{0} and d_{1}. So what will be d_{2}, d_{3}, ... ?

d_{2} = (d_{0} + d_{1})\mod 10

d_{3} = (d_{2} + d_{1} + d_{0}) \mod 10 = ((d_{0} + d_{1}) \mod 10 + d_{0} + d_{1}) \mod 10 = 2 * (d_{0} + d_{1}) \mod 10

d_{4} = (d_{3} + d_{2} + d_{1} + d{0}) \mod 10 = 4 * (d_{0} + d_{1}) \mod 10

d_{5} = (d_{4} + d_{3} + d_{2} + d_{1} + d_{0}) \mod 10 = 8 * (d_{0} + d_{1}) \mod 10

d_{6} = (d_{5} + ... + d_{1} + d_{0}) \mod 10 = 16 * (d_{0} + d_{1}) \mod 10 = 6 * (d_{0} + d_{1}) \mod 10

d_{7} = (d_{6} + ... + d_{1} + d_{0}) \mod10 = 12 * (d_{0} + d_{1}) \mod 10 = 2 * (d_{0} + d_{1}) \mod 10

If we keep on making d_{i} we will see that the resultant is just looping through the same values.
Rigorously, we can see that d_{0} contributes 1 time(s) to d_{2}, 2 times to d_{3}, 4 times to d_{4}, 8 times to d_{5}, …, 2^{k - 2} times to d_{k}. But since the powers of 2 under modulo 10 cycle from 1, 2, 4, 8, 6, 2, 4, …
Similarly for d_{1}.

Here the cycle length is of 4, where d_{2} is not present in the cycle.
Let S = (2*(d_{0} + d_{1})) \mod 10 + (4*(d_{0} + d_{1})) \mod 10 + (8*(d_{0} + d_{1})) \mod 10 + (6*(d_{0} + d_{1})) \mod 10

So the sum of digits = d_{0} + d_{1} + d_{2} + S * ((k - 3) / 4) + x, here the first 3 terms will be covered by d_{0}, d_{1}, d_{2} and after that the groups of 4 will be covered by S, but this formula will still have not have summed some terms at the end left when (k - 3) is not divisible by 4 (the sum of these terms is denoted by x and the explanation regarding them is given using the example shown below)

Example \rightarrow k = 13, The sum of digits = $d_{0} + d_{1} + d_{2} + S * 2 + x$Then it will have d_{0}, d_{1}, d_{2} then the first S will have d_{3}, d_{4}, d_{5}, d_{6} and the second S will have d_{7}, d_{8}, d_{9}, d_{10}. Now the remaining terms, i.e d_{11} and d_{12} still needs to be added which is being referred to as x in the above formula. For this we can simply say that

d_{11} = 2*(d_{0} + d_{1}) \mod 10

d_{12} = 4*(d_{0} + d_{1}) \mod 10

And x = d_{11} + d_{12}

Time and space complexity of this solution is O(1).

For implementation details please refer to the solutions attached below.

SOLUTIONS

Setter’s solution.
Tester’s solution.

8 Likes

Please attach the link to the setter and tester’s solution. :slight_smile: @sidhant007

1 Like

The testers and setters solution link is not working .The links are directing to their profiles .Please update the links of solutions

my logic is sum%3 = ( ((d0 +d1)%3) +((2^(k-2)-1)*(d0+d1))%10 )%3 , and its giving me wrong answer can someone explain me why it is my code https://ideone.com/uiqUn6 . Thanks in advance

include

using namespace std;

int main()
{
int t,a,b;
cin>>a>>b;
int sum=a+b;
for(int j=0;j<t;j++)
{
cin>>a,b;
sum=a+b;

for(int i=1;i<=k-2;i++)
    {
        sum+=(i*(a+b))%10;
    }
if(sum%3=0)
cout<<"YES";
else
cout<<"NO";
    }

return 0;
}

My python solution.

Why is this solution showing time limit exceeded?
Link.

Hi, can someone please explain why the output is NO when k = 2 and sum of first two numbers is 12, 15 or 18?
For example this test case.
1 (number of test cases)
2 (k : length of number) 9 (first number) 3 (second number)

here the final number must be 93 hence divisible by 3 but the correct solutions are giving output as NO for this test case.

Problem: MULTHREE

My Short solution in PYTHON 3.5:-Time Complexity O(1)

test=int(input())
for y in range(test):
     k,dig0,dig1=input().split()
     k,dig0,dig1=int(k),int(dig0),int(dig1)
     sum1=dig0+dig1
     for i in range(3,k+2):
        y=sum1%10
        sum1+=y
        if(y==2):
           ter1=((k-i)//4)
           ter1*=20
           sum1+=ter1
           ter=k-i
           if(ter%4==3):
             sum1+=18
           elif(ter%4==2):
             sum1+=12
           elif(ter%4==1):
             sum1+=4
           break
         if(y==0):
           break
     if(sum1%3==0):
       print("YES")
     else:
       print("NO")

LOGIC:-

For a number to be divisible by Three sum should be divisisble by 3.Keep on adding sum and finding digits(sum%10); if digit is 0 then break as sum will remain same even after u do any operation so break. Else break when u find a two as 2,4,8,6 block will keep on repeating. therefore add ((k-i)//4)(2+4+6+8) to sum ((k-i)//4) is floor division plus remaining 4 12 or 18 depending on whether 4 or 4,8 or 4,8,6 is remaining. This block’s size is got by (k-i)%4.Then at last check whether sum is divisible by 3.

Hello all,

Thanks for posting the editorial, but I am really at a loss why my solution is failing. I tried all possible boundary cases as well as some that tested big values.

If you could give me a fail case for the below code, and also help me out on how you tested this solution, it will be really helpful.

My Solution for MULTHREE

Warm Regards,
Ruddra

my method https://www.codechef.com/viewsolution/22144353 is by observation of repeating digits, with refer to example 2, N is 8198624862486 which is 819 8624 8624 86, which mean that for k = 13, we try to find how many repeated sequence behind 819, which is (13-3)/4 = 2 and (13-3)%4 = 2 , that mean i sum up 8+1+9 + 2*(8+6+2+4) + (8+6) = 72, since 72%3==0, that mean example 2 answer is “YES”.

why do you think your formula is correct? you are just adding 3rd digit and possibly last digit

http://codeforces.com/blog/entry/57259?#comment-409147

@kasa your formula is correct may be because of some overflow you are getting wrong answer

@divik544 he is correct can u explain y is he adding 3rd digit and possibly last digit?

The example given for k=12.
But won’t x=d11 only? di goes from 2<=i<k, right. Please change that.

@aman935 yes it should be d11 only

Got it…

The answer is “YES”. What “correct solutions” are you talking about?

consider this one https://www.codechef.com/viewsolution/17135160.
I have compiled it here https://ide.geeksforgeeks.org/Ly9Iwu6ROB