MULTHREE - Editorial

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

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

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

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

yes. thanks for confirming.

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

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.;
import java.io.
;

class Rextester
{
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

public Reader()
{
  din = new DataInputStream(System.in);
  buffer = new byte[BUFFER_SIZE];
  bufferPointer = bytesRead = 0;
}

public Reader(String file_name) throws IOException
{
  din = new DataInputStream(new FileInputStream(file_name));
  buffer = new byte[BUFFER_SIZE];
  bufferPointer = bytesRead = 0;
}

public String readLine() throws IOException
{
  byte[] buf = new byte[64]; // line length
  int cnt = 0, c;
  while ((c = read()) != -1)
  {
    if (c == '\n')
    break;
    buf[cnt++] = (byte) c;
  }
  return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
  int ret = 0;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();
  do
  {
    ret = ret * 10 + c - '0';
  } while ((c = read()) >= '0' && c <= '9');

  if (neg)
  return -ret;
  return ret;
}

public long nextLong() throws IOException
{
  long ret = 0;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();
  do {
    ret = ret * 10 + c - '0';
  }
  while ((c = read()) >= '0' && c <= '9');
  if (neg)
  return -ret;
  return ret;
}

public double nextDouble() throws IOException
{
  double ret = 0, div = 1;
  byte c = read();
  while (c <= ' ')
  c = read();
  boolean neg = (c == '-');
  if (neg)
  c = read();

  do {
    ret = ret * 10 + c - '0';
  }
  while ((c = read()) >= '0' && c <= '9');

  if (c == '.')
  {
    while ((c = read()) >= '0' && c <= '9')
    {
      ret += (c - '0') / (div *= 10);
    }
  }

  if (neg)
  return -ret;
  return ret;
}

private void fillBuffer() throws IOException
{
  bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  if (bytesRead == -1)
  buffer[0] = -1;
}

private byte read() throws IOException
{
  if (bufferPointer == bytesRead)
  fillBuffer();
  return buffer[bufferPointer++];
}

public void close() throws IOException
{
  if (din == null)
  return;
  din.close();
}

}

public static void main(String[] args) throws IOException
{
Reader in=new Reader();
int test=in.nextInt();
while(test-- >0){
int k=in.nextInt();
int d0=in.nextInt(), d1=in.nextInt();
String D2=d0+“”+d1+“”+((d0+d1)%10);
//System.out.println(D2);
int d2=Integer.parseInt(D2);
String D3=d2+“”+((d0+d1+d2)%10);
//System.out.println(D3);
int d3=Integer.parseInt(D3);
//check for k<=3
if(k==2){
if((d0+d1)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (k==3) {
if((d2)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (k==4) {
if((d3)%3==0)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else if (d3%10==0) {
if(d2%3==0)
System.out.println(“YES”);
else {
System.out.println(“NO”);
}
}
else{
int skip=8+6+2+4;
int skp[]={8, 6, 2, 4};
long sum=d0+d1+d2%10;
//System.out.println(sum);
k=k-4;int index=-1;
if(d3%10==8)
index=0;
if(d3%10==6)
index=1;
if(d3%10==2)
index=2;
if(d3%10==4)
index=3;
int s= k/4;
int m= k%4;
sum= sum+s*skip;
//System.out.println(index);
for(int i=0;i<=m;i++){
sum+=skp[(index)%(skp.length)];
//System.out.println("–> "+sum);
index++;
}
//System.out.println("sum: "+sum);
if(sum%3==0)
System.out.println(“YES”);
else {
System.out.println(“NO”);
}
}
}
}
}

I have no idea why am I getting WA in this. Please help

Can someone help me find a bug in my code. For sample inputs it shows right output and for the other I have tested few using manual calculation. But when I submit it says WA.
codechef.com/viewsolution/31077750

Please help me in checking why it is not working

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class CodeChef2
{
public static void main (String[] args) throws java.lang.Exception
{
//your code goes here
Scanner sc=new Scanner(System.in);
/*int i=0;
System.out.println(" “+i);
i=Integer.MAX_VALUE;
System.out.println(” “+i);
long l=Long.MAX_VALUE;
System.out.println(” "+l);
*/

	int d0,d1,T;
	long k;
	
	T=sc.nextInt();
	
	for(int i=0;i<T;i++)
	{	
		k=sc.nextLong();
		d0=sc.nextInt();
		d1=sc.nextInt();
		int value=0;
		//System.out.print(k+ " "+ d0+ " "+ d1);
		int left;
		int s=d0 + d1;
	//	System.out.println("S:"+s);
		int N=(int)((k-3)/4);
		int cycle= ((2*s)%10) + ((4*s)%10) + ((8*s)%10 )+ ((6*s)%10);
	//	System.out.println("cycle:"+cycle);
		if(k==2)
			value=d0 + d1;
		else
		{
		    value= s + (s) + (cycle*N);
	//	System.out.println("value before left:"+value);
		left=(int)( k-3- 4*N);
	//	System.out.println("left:"+left);
		int p=2;
		for(int j=1;j<=left;j++)
		{  value+=((p*s)%10);
			p=(p*2)%10;
		}
		}	
	//	System.out.println("Value:"+value);
		if(value%3 == 0)
			System.out.println("YES");
		else
			System.out.println("NO");
	}

}

}

please help me to solve MULTHREE everything is oke but final answer is WRONG

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class CodeChef2
{
public static void main (String[] args) throws java.lang.Exception
{
//your code goes here
Scanner sc=new Scanner(System.in);
/*int i=0;
System.out.println(" “+i);
i=Integer.MAX_VALUE;
System.out.println(” “+i);
long l=Long.MAX_VALUE;
System.out.println(” "+l);
*/

	int d0,d1,T;
	long k;
	
	T=sc.nextInt();
	
	for(int i=0;i<T;i++)
	{	
		k=sc.nextLong();
		d0=sc.nextInt();
		d1=sc.nextInt();
		int value=0;
		//System.out.print(k+ " "+ d0+ " "+ d1);
		int left;
		int s=d0 + d1;
	//	System.out.println("S:"+s);
		int N=(int)((k-3)/4);
		int cycle= ((2*s)%10) + ((4*s)%10) + ((8*s)%10 )+ ((6*s)%10);
	//	System.out.println("cycle:"+cycle);
		if(k==2)
			value=d0 + d1;
		else
		{
		    value= s + (s) + (cycle*N);
	//	System.out.println("value before left:"+value);
		left=(int)( k-3- 4*N);
	//	System.out.println("left:"+left);
		int p=2;
		for(int j=1;j<=left;j++)
		{  value+=((p*s)%10);
			p=(p*2)%10;
		}
		}	
	//	System.out.println("Value:"+value);
		if(value%3 == 0)
			System.out.println("YES");
		else
			System.out.println("NO");
	}

}

}

please help me why answer is not coming right

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

Can someone tell me what I am doing wrong here?

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

// Template Begin
#pragma GCC optimize(“O3”)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define le length()
#define sz size()
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
template inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template inline T mod(T x) { if(x < 0) return -x; else return x; }
typedef vector VII;
typedef pair<int, int> PII;
typedef pair<int, PII > PPII;
typedef vector< PPII > VPPII;
typedef vector< PII > VPII;
const int MOD = 1e9 + 7;
const int INF = 1e9;
// Template End
const int MAX = 10;
VPPII adj[MAX];
bool vis[MAX];
int dist[MAX];
int distt[MAX];
int parent[MAX];
//scanf(" %[^\n]s",s);//getline(gets) goes not work when you have to pass test cases because buffer does not take integer while we are inserting string;
int str2int (const string &str) {
stringstream ss(str);
int num;
ss >> num;
return num;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t>0,t–)
{
long long k,d0,d1;
cin>>k>>d0>>d1;
long long firsttotal = 2d0+2d1;
long long secondtotal = ((k-3)/4)* 20;
int reminder = (k-3)%4;
int nextSum = firsttotal;
if(reminder > 0)
{
nextSum += nextSum%10;
reminder–;

	}
		if(reminder > 0)
	{
		nextSum += nextSum%10;
		reminder --;
		
	}
		if(reminder > 0)
	{
		nextSum += nextSum%10;
		reminder --;
		
	}
		if(reminder > 0)
	{
		nextSum += nextSum%10;
		reminder --;
		
	}

	
  if((nextSum + secondtotal)%3 == 0)
  {
  	cout<<"YES"<<endl;
  }else{
  	cout<<"NO"<<endl;
  }

	
}

}
can anyone tell me why this program giving wrong?

My solution to MULTHREE
I have solved the code mathematically on paper and implemented it on my code. i have used following property of modulo operator:

I have expanded the summation terms and applied the above property, but i am getting WA.
If someone can please help me out debug the issue.
Thanking in advance.

Why am I getting ‘Wrong Answer’?
I ran this code on my IDE, it gave the correct answer for all the test cases.

//The code

#include
#include <math.h>
#include
#include
using namespace std;

int main() {
long long t;
cin>>t;
string output[t];
for(long long i=0;i<t;i++){
int d0,d1;
long long k;
cin>>k>>d0>>d1;
long long sum;
long long sum1=(2*(d0+d1))%10+(4*(d0+d1))%10+(8*(d0+d1))%10+(6*(d0+d1))%10;
long long sum2=d0+d1+((d0+d1)%10)+sum1*((k-3)/4);
long long temp=(k-3)%4;
if(temp==1){
sum=sum2+(2*(d0+d1))%10;
}
else if(temp==2){
sum=sum2+(2*(d0+d1))%10+(4*(d0+d1))%10;
}
else if(temp==3){
sum=sum2+(2*(d0+d1))%10+(4*(d0+d1))%10+(8*(d0+d1))%10;
}

    if(sum%3==0){
        output[i] ="YES";
    }
    else{
        output[i]="NO";
    }
}
for(long long i=0;i<t;i++){
    cout<<output[i]<<"\n";
}
return 0;

}

t = int(input())
for xyz in range(t):
    [n,a,b] = map(int,input().split(' '))
    if n==2:
        if a+b%3==0:
            print('YES')
        else:
            print('NO')
    else:
        c = (a+b)%10
        arr_sum=0
        d=[]
        for i in range(4):
            d.append(((2**(i+1))*c)%10)
            arr_sum+=d[i]
        digit_sum = a+b+c
        n-=3
        digit_sum += (n//4)*arr_sum
        left = n%4
        for i in range(left):
            digit_sum+=d[i]
        if digit_sum%3==0:
            print('YES')
        else:
            print('NO')

This code apparently is not able to handle the case when fourth digit is zero. I added a block to handle such cases and it worked fine. But I couldn’t find out why it doesn’t work in that case. I manually gave test cases where 4th digit is zero and it worked. Help !
Click here for my similar C++ solution

This is the simplest solution i could see after seeing other solutions, i thought but its showing TLE. Can anyone please help ?
//sum is sum of digits

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

int main() {
// your code goes here
int tests = 0;
cin >> tests;

while(tests--){
    long long int K = 0, sum = 0;
    int d0 = 0, d1 = 0;
    cin >> K >> d0 >> d1;
    sum = d0 + d1;
    for(int i = 2; i < K; i++){
        sum += (sum%10);
    }
    cout << ((sum%3==0)?"YES":"NO") << endl;
}

return 0;

}

You are missing the case when k=1 and k=2

K=10^12 , a simple for loop is not the efficient algorithm.
try to use cyclic pattern mentioned in editorial

1 Like