MULTHREE - Editorial

editorial
, , , , ,
21

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

22

yes. thanks for confirming.

23

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.

24

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

25

Try

4 2 5
26

Hi Akshay,

Thanks for your response. However I see that the number generated by 4 2 5 is 2574. Which is divisible by 3 as per my output, and it is also divisible by 3. Please let me know if I’m wrong somewhere.

Regards,

Ruddra

27

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