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?