MULTHREE - Editorial

editorial
, , , , ,
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.

5 Likes
2

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

1 Like
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

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

6

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

7

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

8

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

9

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;
}

10

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

11

@aman935 yes it should be d11 only

12

My python solution.

13

Why is this solution showing time limit exceeded?
Link.

14

Got it…

15

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.

16

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

17

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

18

i came with the same formula but i didnt get the right result as well can anyone explain please?

19

there is no dot at the end of the link. Correct link : https://www.codechef.com/viewsolution/17135160

20

Well, then we have another problem with weak test cases.