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 multiple three. Please help
Please format your code, and explain in brief what was your logic?
However you can debug your code with the test cases provided here Competitive-Programming/Code-Chef/Multiples-of-3/test-cases at master · strikersps/Competitive-Programming · GitHub which will help you find the bug in your code.
my solution answer is correct but unable to submit
https://www.codechef.com/viewsolution/30963128
I cannot access the link (Access Denied), why? because you cannot share your solution link from an ongoing contest.
Use pastebin to share the solution.
Hi @striker22. Thanks for the editorials. I was able to solve the first 8 problems comfortably. But the MULTHREE too me a lot of time and I also needed to see your code to solve it. Is it bad for a beginner(no exposure to modular arithmetic) to be not able to solve that problem within a day ? I put my best efforts to complete it without outside help but was not able to.
BTW, thanks for the code on GitHub it saved my day 
1 Like
@krish_na Thanks for the kind words.
I won’t say it’s bad because you can always learn whatever you want to learn and as far as competitive programming is concerned, well modular arithmetic is a very important concept or tool which you must have in your arsenal because the concept of modular arithmetic is used very much in competitive programming especially when dealing with recursive equation and when you want to do modular/ matrix exponentiation because it reduces the time complexity of your program drastically.
Apart from competitive programming modular arithmetic is very important when you are dealing with crypto-systems (Encryption & Decryption Algorithms) or in general, if you are interested in Cyber Security.
If you want to learn modular arithmetic refer to the following points and links:
- (a + b) \bmod c = (a \bmod c + b \bmod c) \bmod c.
- (a - b) \bmod c = (a \bmod c - b \bmod c) \bmod c.
- (a \times b) \mod c = (a \bmod c \times b \bmod c) \bmod c.
- a^{b} \bmod c = (a \bmod c \times a \bmod c \times a \bmod c \cdots a\bmod c) \bmod c.
Refer to Modular Arithmetic for the basics. However, if you refer to any number theory book, it consists of everything you need to know about modular arithmetic.
-
For modular exponentiation technique i.e. calculation of a^{b} \bmod c in O(log n), refer to Modular Exponentiation.
-
For Matrix Exponentiation i.e. calculation of A^{n} \bmod c \;\text{where A = matrix} in O(K \times logn) where K = \text{Complexity of Matrix Multiplication}, refer Matrix Exponentiation.
These are basic kinds of stuff (using which you can solve most of the problems as far as I know) you need to know, then you can go for advance kinds of stuff.
Thanks for Reading
Peace 
2 Likes
@striker22 Thanks for the links man 
Cheers 
1 Like
Your code is printing an extra output than the required number.
Refer to your updated/accepted code as follows and follow through the comment: The following block of code is updated, previously due to this, the code is printing one extra output in STDOUT.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int t;
cin >> t;
while(t--) {
string s;
cin>>s;
int arr1[26];
int arr2[26];
for(int i=0; i < 26; i++) {
arr1[i] = arr2[i] = 0;
}
int length = 0;
length = s.length();
if(length >= 2 && length <= 1000) {
if(length % 2 == 0) {
for(int i=0; i < length/2; i++) {
arr1[(int(s[i]) - 97)]++; //convert ascii into decimal
}
for(int i = length/2; i < length; i++) {
arr2[(int(s[i]) - 97)]++;
}
} else {
for(int i = 0; i < length/2; i++) {
arr1[(int(s[i]) - 97)]++;
}
for(int i = (length + 1)/2; i < length; i++) {
arr2[(int(s[i]) - 97)]++;
}
}
/*
* The following block of code is updated, previously due to this, the code is printing one extra output in STDOUT.
*/
int flag = 1;
for(int i=0; i < 26; i++) {
if(arr1[i] != arr2[i]) {
flag = 0;
break;
}
}
if(flag == 1) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
return 0;
}
However, your code is a little messy due to messy indentation, in the future do write the code which is easy to understand and you are doing a lot of unnecessary computation. You can refer to Lapindrome Solution for a simple solution in C++.
ok so I went through that github link. I think it’s old. In test input three the last input is wrong. (2 9 5)
Also my code passed all the other test cases but is still getting WA.
so my approach is this
I found a pattern in the number…
there is a repeating pattern of 8 6 2 4 from k=3
so I made a variable sum as (d0= 1st no and d1= 2nd no)
s= k/4
m=k%4
sum = (sum of digits of 3rd number) + s*(8+6+4+2)
now I add the remaining digits. For ex if last digit of k=4 is 8 then the next in line is 6 and then 2 and then 4
I think I ve covered everything, but still getting WA.
import java.util.*;
import java.io.*;
import java.math.*;
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 summ=d0+d1+d2%10;
BigInteger sum= new BigInteger(String.valueOf(summ));
//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;
//long s= k/4;
// BigInteger s= new BigInteger((k/4).toString());
int m= k%4;
//sum= sum+s*skip;
sum= sum.add(BigInteger.valueOf((k/4)*skip));
//System.out.println(index);
for(int i=0;i<=m;i++){
int temp=skp[(index)%(skp.length)];
sum=sum.add(BigInteger.valueOf(temp));
//System.out.println("--> "+sum);
index++;
}
//System.out.println("sum: "+sum);
if(sum.mod(BigInteger.valueOf(3)).intValue() == 0)
System.out.println("YES");
else {
System.out.println("NO");
}
System.out.println("SUM: "+sum);
}
}
}
}
//https://github.com/strikersps/Competitive-Programming/tree/master/Code-Chef/Multiples-of-3/test-cases
@prophet_james I have already updated my code yesterday with rectified bugs.
However in your code you had an System.out.println("SUM: "+sum); which is one of the reasons for WA.
I would suggest you to take a look at your source-code other functions because even after removing the above mentioned line from your code, it is still giving WA but I am not able to find a bug in your program even after running it through 100 test cases and it’s giving right answer for those cases.
IKKKKKKK that is the thing. Do you know where I can find the test cases used in the DSA learning series? I have been stuck here for last 2 days and I have done everything.
Smart Phone
Hey there could you please explain the formula used in finding max revenue. Explain the logic in here:
- In solutions.py file
max_revenue(arr[i]) = arr[i] * (n-i)
- In Editorials
max_revenue(arr[i]) = arr[i] * (i+1)
1 Like
I think you are right. I have complicated it very much.
I first calculate the k=3 number which is stored in d3. Then I check the last digit of this number. If that is 8 then I assign variable index as 0, 6 then index=1, 2 then index =2 and 4 then index =4.
PS: I am not assuming that the pattern is repeating after the k=3. I am assuming that any one of these 4 (8, 6, 2, 4) comes at k=3 and then rest come in subsequent numbers in cyclic order (i.e. 6 after 8, 2 after 6, 4 after 2)
Now once I have the index, I calculate the sum of the number when k=2
long summ=d0+d1+d2%10;
and then
sum= sum.add(BigInteger.valueOf((k/4)*skip));
this performs sum= sum+s*skip; where s is k/4;
now I am adding the remaining numbers. which are not added by k/4…
took a loop and added them via a cyclic array.
TBH I think I did everything as you’ve mentioned in your approach. Maybe I am missing something, or IDK, there is nothing that I can find as the reason for WA. Any way I can get the test case for which it is failing would be helpful. Thanks
Did you get AC? if not can you share the link of your source-code through pastebin.
Thanks for finding out the typo, I updated it in the editorial part.
It should be \text{Max Revenue} = a[i] \times (n - i) \;\forall i\; \text{where } 0 <= i < N.
Hey @striker22 could you please explain me the logic = a[i] x (n-i) the use of (n-i)
@dhairyaostwal n - i represents the total number of people who have the minimum budget to buy that app whose price is set to a[i].
OR
The array is sorted in increasing order the number of people who will be able to buy the app will be n - i where n = Total number of potential customers.
1 Like