MULTHREE - Editorial

cook90
easy
editorial
maths
modulo
multhree

#1

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.


#2

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


#3

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


#4

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


#5

include

using namespace std;

int main() { int t,a,b; cin>>a>>b; int sum=a+b; for(int j=0;j>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; }


#6

My python solution.


#7

Why is this solution showing time limit exceeded?
Link.


#8

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.


#9

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.


#10

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


#11

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


#12

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


#13

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


#14

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


#15

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


#16

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


#17

@aman935 yes it should be d11 only


#18

Got it…


#19

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


#20

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