MULTHREE - Editorial

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

yes. thanks for confirming.

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

Try

4 2 5

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

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

//