MULTHREE - Editorial

editorial
, , , , ,
5

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

6

My python solution.

2 Likes
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 CodeChef: Practical coding for everyone 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”.

1 Like
12

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

13
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 CodeChef: Practical coding for everyone.
I have compiled it here Online Compiler and IDE - GeeksforGeeks

21

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

22

there is no dot at the end of the link. Correct link : CodeChef: Practical coding for everyone

23

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

24

The second term gives you \sum d_i \mod 10 \mod 3, and you need \sum d_i \mod 3.