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 
@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 
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)
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.
was that for me?
@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.
@prophet_james Your code has a very subtle bug which most of the time goes un-noticed. After a through analysis of your code I found out that the data-type which you have declared for storing k is int rather it must be long, look at the constraints imposed on K i.e. 2 <= K <= 10^{13} which cannot be stored in a JAVA int variable because the size of int in JAVA is 4 bytes i.e. 32-bits and obviously the upper-limit of K which is 10^{13} >> 2,147,483,647.
Updated Code is as follows:
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){
long k=in.nextLong();
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());
long 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");
}
}
}
}
}
However, as I have told you earlier that there is simple and elegant code for solving the problem which you can refer below:
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) {
long k = in .nextLong();
long d0 = in .nextInt(), d1 = in .nextInt();
String D2 = d0 + "" + d1 + "" + ((d0 + d1) % 10);
long d2 = Integer.parseInt(D2);
if (k == 2 || ((d0 + d1) % 10) == 0) {
if (((d0 + d1) % 3) == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
continue;
}
long sum_of_digit = d0 + d1 + ((d0 + d1) % 10);
if(k > 3) {
long digit_repeat[] = {((d0 + d1) << 1) % 10, ((d0 + d1) << 2) % 10, ((d0 + d1) << 3) % 10, ((d0 + d1) << 4) % 10};
long sum_digit_repeat = digit_repeat[0] + digit_repeat[1] + digit_repeat[2] + digit_repeat[3];
sum_of_digit += (((k - 3) / 4) * (sum_digit_repeat));
int remainder = (int) ((k - 3) % 4);
switch (remainder) {
case 1:
sum_of_digit += digit_repeat[0];
break;
case 2:
sum_of_digit += (digit_repeat[0] + digit_repeat[1]);
break;
case 3:
sum_of_digit += (digit_repeat[0] + digit_repeat[1] + digit_repeat[2]);
}
}
if((sum_of_digit % 3) == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
NOTE: Do remember next time, in competitive programming (especially) before your write your code for solution, really give a hard look at the constraints. There is a lot of insights present there only which can help you come up with the right algorithm.
You should follow a coding convention while writing the code so that it is easy to follow when you share the code on online forums or with someone.
You can refer to the following links:
- Google Java Style Guide
- For Information on Data-Type Ranges: Chapter 4. Types, Values, and Variables