MULTHREE - Editorial

editorial
, , , , ,
42

I’ve pretty much followed whatever was mentioned in the editorial. My sol’n is passing the sample test case but gives WA upon submission. Please help me rectify the issue, thanks.

#include <iostream>
using namespace std;

int main() {
	int cases,d0,d1,d2,d3,d4,d5,d6,digitsum,S;
	unsigned long K;
	cin >> cases;
	while(cases--){
	   cin >> K >> d0 >> d1;
	   digitsum = d0+d1;
	   
	   if(K==2){
	       (!(digitsum%3))?cout<<"YES"<<endl:cout<<"NO"<<endl;
	       continue;
	   }
	   
	   d2 = (d0+d1)%10;
	   d3 = (2*(d0+d1))%10;
	   d4 = (4*(d0+d1))%10;
	   d5 = (8*(d0+d1))%10;
	   d6 = (6*(d0+d1))%10;
	   S = d3+d4+d5+d6;
	   
       switch((K-3)%4){
	       case 0: digitsum += d2+(S*((K-3)/4));
	       break;
	       case 1: digitsum += d2+(S*((K-3)/4))+d3;
	       break;
	       case 2: digitsum += d2+(S*((K-3)/4))+d3+d4;
	       break;
	       case 3: digitsum += d2+(S*((K-3)/4))+d3+d4+d5;
	   }
	   
	   (!(digitsum%3))?cout<<"YES"<<endl:cout<<"NO"<<endl;
	}
	return 0;
}
43

#include
#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
for(int i=0;i<t;i++)
{
long long int k;
cin>>k;
long long int d0,d1;
cin>>d0;cin>>d1;
long long int j,count;
count=d0+d1;
k-=2;

    if((d0 + d1)%2!=0)
    {
        count*=2;
        k--;
    }
    int z;
    switch(count%10)
    {
        case 2:
            
            for(z=0;z<k%4;z++)
            {
                count+=pow(2,z+1);
                
            }
            k=k-z;
            count+=(20*(k/4));
            break;
        case 4:
            z=2;
            while(z<4 && k!=0)
            {
                count+=pow(2,z);
                z++;
                k--;
            }
            if(k)
            {
                count+=6;
                k--;
            }
            for(z=0;z<k%4;z++)
            {
                count+=pow(2,z+1);
            }
            k=k-z;
            count+=(20*(k/4));
            break;
        case 8:
            z=3;
            while(z<4 && k!=0)
            {
                count+=pow(2,z);
                z++;
                k--;
            }
            if(k)
            {
                count+=6;
                k--;
            }
            for(z=0;z<k%4;z++)
            {
                count+=pow(2,z+1);
            }
            k=k-z;
            count+=(20*(k/4));
            break;
        case 6:
            if(k)
            {
                count+=6;
                k--;
            }
            for(z=0;z<k%4;z++)
            {
                count+=pow(2,z+1);
            }
            k=k-z;
            count+=(20*(k/4));
            break;
        default:
            break;
    }
    
    if(count%3)
    {
        cout<<"NO\n";
    }
    else
    {
        cout<<"YES\n";
    }
}
return 0;

}

44

almost same but getting wrong answer …
even editorial leads the same method … can anyone guide plz

45

Here the cycle will always be a permutation of 2, 4, 6, 8. So why is it giving WA on putting 20 directly in place of S?
OR
Give me an example where d2, d3, d4, d5 are not the permutation of 2,4,6,8. :slightly_smiling_face:

46

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
while(t–){
ll k,d0,d1,s,sum=0;
cin>>k>>d0>>d1;
ll x=(d0+d1)%10,d2=d0+d1;
s=(2x)%10+(4x)%10+(8x)%10+(6x)%10;
ll y=(k-3)%4,z=2;
while(y!=0)
{
sum+=(zx)%10;
z=(z2)%10;
y–;
}
ll finalsum;
finalsum=d0+d1+d2+s*((k-3)/4)+sum;
if(finalsum%3==0)
cout<<“YES”<<"\n";
else
cout<<“NO”<<"\n";
}
return 0;
}

why does my soln gives tle?

47

This problem is meant to have complexity O(1). Your solution has a complexity of O(n). For k = 10^12, it is very slow.

48

@sidhant007 how can we get to know this algo by seeing the problem

49

My solution at my solution.

@sidhant007
In this solution, I can’t figure out why I am getting a TLE error. If someone can help, that would be great. Thank in advance!

50

If someone could help me find the problem in this code, that would be a great help… Thank you in advance!
https://www.codechef.com/viewsolution/40455729

52

I have also applied this approach because this seems to be a very generic approach other than what others have provided but the answer is wrong as per codechef, is your code working or you can give me some boundary cases which doesn’t satisfy this approach?

54

this pattern is not visible when d0 = 7 and d1 = 8

55

Bro your code is way to optimized, i love it but can you please :pray: explain your code :slightly_smiling_face:

56

I tried to submit my code, but it’s getting wrong somewhere, I don’t know what’s the bug, it would be very helpful, if someone can fix it.

https://www.codechef.com/viewsolution/46732536

57

Consider the test input:

1
2 2 7
58

Thank you so much. I just forgot the base case. Will look to it next time more keenly.

1 Like
59

Hey Zeborg,

Hope by now you would have an answer for this, just in case if it helps actually you are overflowing for digsum ,try using long long.

Thanks,
Satyam

60

Very precise and optimized code. I never would have thought of using the bitwise operator. I would appreciate it if you could spare some time to explain how you would come up with the solution using the bitwise operator.

61 
#include <iostream>
using namespace std;

int main() {
	// your code goes here
	short d0,d1,term1,y;
	int t,sum;
	long long k,repeat;
	cin>>t;
	while(t--) {
	    cin>>k>>d0>>d1;
	    sum=d0+d1;
	    for (int i=2;i<k;i++) {
	        y=sum%10;
	        if (y==0)
	            break;
	        else if (y%2==0) {
	            repeat=(k-i)/4;
	            sum+=repeat*20;
	            term1=(k-i)%4;
	            if (term1==3)
	                sum+=y+((2*y)%10)+((3*y)%10);
	            else if (term1==2)
	                sum+=y+((2*y)%10);
	            else if (term1==1)
	                sum+=y;
	            break;
	        }
	        else
	            sum+=y;
	    }
	    if (sum%3==0)
	        cout<<"YES\n";
	    else
	        cout<<"NO\n";
	    
	}
	return 0;
}

I have tried all kinds of input and the logic is correct but while submission it says wrong answer. Can someone tell me where it’s going wrong?

62

Consider the test input:

1
5 4 2
63

okay replacing 3y with 4y seemed to do the trick but codechef is still saying wrong answer