This post consist of editorials and solution links to problems of the contest Complexity Analysis + Basics Warm Up in C and Python for your reference if you get stuck.
I highly suggest you try the problem first about 5-10 times then if you are not able to come up with the solution, you can refer to this post.
-
Problem Name: Life, the Universe, and Everything.
Editorial: Just implement what is said in the problem as it is.
Solution-Link: Life, the Universe, and Everything Solution Code.
-
Problem Name: Reverse The Number.
Editorial: In this problem you need to reverse the given number N and as constraints imposed on N are 1 ≤ N ≤ 10^{6} means you can use int variable to store the value. No need to use the strings.
The algorithm for Reversing the Number:
reverse_number = 0
while(n) {
reverse_number = (10 * reverse_number) + (n % 10);
n = n / 10;
}
Time-Complexity: O(\text{Number of Digits in N}).
Solution-Link: Reverse The Number Solution Code.
-
Problem Name: Lapindromes.
Editorial: A string is said to be a lapindrome if with respect to mid-element the frequency of each character in the left-half is equal to the frequency of each character on the right half. In case of odd length, ignore the mid-element.
Time-Complexity: O(N) where N = \text{Length of the string.}
Solution-Link: Lapindrome Solution Code.
-
Problem Name: Smart-Phone.
Editorial: You are given the budget of N potential customers and you are asked to find the maximum possible revenue you can earn by setting a particular price for the app.
If you think, calculating the average budget of N customers will give you the right answer, then you are wrong.
This problem can be solved using the Greedy Approach i.e. you will first sort the customer’s budget in increasing order, then you will calculate for every customer what is the maximum revenue earned if the app price = a[i] \;\forall i\; \text{where }0 <= i < N.
Revenue Earned if app price is a[i] = a[i] \times (n - i).
In last print the maximum revenue.
Time Complexity: O(nlogn) + O(N) where N = \text{Total Customers}.
O(nlogn) is due to sorting and O(N) due to traversing the array for calculating the maximum revenue.
Solution Link: Smart Phone Solution Link.
-
Problem Name: Carvans.
Editorial: CARVANS - Editorial
Time Complexity: O(N) where N = \text{Number of Cars on the straight track,}
Solution Link: Carvans Solution Link.
-
Problem Name: Factorial.
Editorial: Just refer to this nice article from Brilliant: Traiing Number of Zeroes.
Time-Complexity: O(\text{Number of times the loop will iterate until N = 0}). As the maximum value of N can be 10^{9} so, time complexity = O(20).
Solution Link: Factorial Solution Link.
-
Problem Name: Coin Flip.
Editorial: CONFLIP - Editorial
\text{answer} = \begin{cases}
\frac{n}{2} & \text{if $n = \text{even i.e.} \; n \bmod 2 == 0.$}\\
1 + \frac{n}{2} & \text{otherwise}
\end{cases}
Time Complexity: O(1).
Solution Link: Coin Flip Problem Solution.
-
Problem Name: Laddus.
Editorial: Implement what is said in the problem statement.
Time Complexity: O(\text{Number of Activities}).
Solution Link: Laddus Solution Link.
-
Problem Name: Multiple of 3.
Editorial: This problem is good because it teaches you how to arrive at a solution by doing a set of logical deduction from the things which you already know (given) in the problem mathematically which in turn reduces the time complexity of the solution.
If you read the problem statement, the first thing which will come to your mind is a O(K) solution but if you look at the constraints imposed on K i.e. 1 <= K <= 10^{12}, means you cannot go for the O(K) approach.
How to do better?
The problem is asking to first generate the digits of a large number whose first two digits d_{0} and d_{1} are given using the given equation:
\displaystyle d_{i} = \sum_{j = 0}^{i - 1} d_{j} (\bmod \;10),\; 2 \leq i < k.
and then check whether the generated number is a multiple of 3 or not.
What you need to do is first calculate this:
S = d_{0} + d_{1} \;\text{if k = 2.}
S = d_{0} + d_{1} + ((d_{0} + d_{1}) \bmod 10) \;\text{if k =3.}
If k \gt 3
a = ( 2 \times (d_{0} + d_{1})) \bmod 10)
b = (4 \times (d_{0} + d_{1})) \bmod 10)
c = (8 \times (d_{0} + d_{1})) \bmod 10)
d = (6 \times (d_{0} + d_{1})) \bmod 10).
S =S + ( (a + b + c + d) \times \frac{k - 3}{4})
If (k - 3) \bmod 4 == 1 then S = S + a
else if (k - 3) \bmod 4 == 2 then S = S + a + b
else (k - 3) \bmod 4 == 3 then S = S + a + b + c
if S \bmod 3 == 0 print YES else print NO, where S = Sum of digits.
How I arrive at the above formula, refer to the explanation given here: MULTHREE - Editorial - editorial - CodeChef Discuss
Time-Complexity: O(1).
Solution Link: Multiples of 3 Solution..
P.S. Do not copy the solution, try to understand first and write the solution by yourself.
UPD1: If you are going to paste your whole code in the reply section and ask for help for finding error, do format your code (Refer to [Tutorial] CoLoR format the Code! for tutorial on formatting) and also please write in brief what was your thinking behind the code.
Thanks
Be Safe & Take Care
Peace 
25 Likes
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,a,b;
long long k,sum;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>k>>a>>b;
sum=a+b;
if(k==2 && (a+b)%3==0)
{
cout<<“YES”<<endl;
continue;
}
if(k==2 && (a+b)%3!=0)
{
cout<<“NO”<<endl;
continue;
}
if(a+b==5 || a+b==10)
{
cout<<“NO”;
continue;
}
if((a+b)%2==0)
{
k-=2;
sum+=(k/4)*20;
if((a+b)%10==2 && k%4==1)
{
sum+=2;
}
else if((a+b)%10==2 && k%4==2)
{
sum+=6;
}
else if((a+b)%10==2 && k%4==3)
{
sum+=14;
}
else if((a+b)%10==4 && k%4==1)
{
sum+=4;
}
else if((a+b)%10==4 && k%4==2)
{
sum+=12;
}
else if((a+b)%10==4 && k%4==3)
{
sum+=18;
}
else if((a+b)%10==6 && k%4==1)
{
sum+=6;
}
else if((a+b)%10==6 && k%4==2)
{
sum+=8;
}
else if((a+b)%10==6 && k%4==3)
{
sum+=12;
}
else if((a+b)%10==8 && k%4==1)
{
sum+=8;
}
else if((a+b)%10==8 && k%4==2)
{
sum+=14;
}
else if((a+b)%10==8 && k%4==3)
{
sum+=16;
}
}
else if((a+b)%2==1)
{
sum+=((a+b)%10);
k-=3;
sum+=(k/4)*20;
if((a+b)%10==1 && k%4==1)
{
sum+=2;
}
else if((a+b)%10==1 && k%4==2)
{
sum+=6;
}
else if((a+b)%10==1 && k%4==3)
{
sum+=14;
}
else if((a+b)%10==7 && k%4==1)
{
sum+=4;
}
else if((a+b)%10==7 && k%4==2)
{
sum+=12;
}
else if((a+b)%10==7 && k%4==3)
{
sum+=18;
}
else if((a+b)%10==3 && k%4==1)
{
sum+=6;
}
else if((a+b)%10==3 && k%4==2)
{
sum+=8;
}
else if((a+b)%10==3 && k%4==3)
{
sum+=12;
}
else if((a+b)%10==9 && k%4==1)
{
sum+=8;
}
else if((a+b)%10==9 && k%4==2)
{
sum+=14;
}
else if((a+b)%10==9 && k%4==3)
{
sum+=16;
}
}
//cout<<sum;
if(sum%3==0)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}
can you tell me why this code is getting wa?
MULTIPLE OF 3 PROBLEM.
Can you format your code, as the system software has messed it up and also do provide what was your thought process behind the code in brief.
if k==2 then we can check whether a+b%3==0 or not.
if (a+b)=5 or a+b=10 then “NO”.
if(a+b)%2==0 the series will follow a pattern from 3 element
sum=(a+b)
if(a+b)%10==2 series will be 2 4 8 6
if(a+b)%10==4 series will be 4 8 6 2
if(a+b)%10==6 series will be 6 2 4 8
if(a+b)%10==8 series will be 8 6 2 4
k-=2;
sum+=(k/4)*20;
then add other k%4 elements.
if(a+b)%2==1 the series will follow a pattern from 4 element
sum=a+b+(a+b)%10
if(a+b)%10==1 series will be 2 4 8 6
if(a+b)%10==7 series will be 4 8 6 2
if(a+b)%10==3 series will be 6 2 4 8
if(a+b)%10==9 series will be 8 6 2 4
k-=3;
sum+=(k/4)*20;
add other k%4 elements
what is wrong with this approach?
@ashu230899 Can you format the code or can you share your code?
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.
You program is giving wrong answer for the following test-cases:
2
5 11 3
167 181 479
For case 5 11 3 you code is giving NONO as output.
Output should be:
NO
YES
This should help you debug your code.
why the answer for 2 9 5 is yes
and
1 ≤ d0 ≤ 9
0 ≤ d1 ≤ 9
Coin Flip Solution is O(1) which is similar approach but slightly different from the editorial -
#include <iostream>
#include <cmath>
using namespace std;
#define datatype long long int
int main()
{
datatype testcases;
cin>>testcases;
while(testcases--)
{
datatype games;
cin>>games;
while(games--)
{
datatype initialState, numberOfRounds, prediction;
cin>>initialState>>numberOfRounds>>prediction;
int count= 0;
if(initialState == 1)
{
if(prediction == 1 || numberOfRounds % 2 == 0)
count= numberOfRounds/2;
else
count= numberOfRounds/2+1;
}
else
{
if(prediction == 1 && numberOfRounds % 2 != 0)
count= numberOfRounds/2+1;
else
count= numberOfRounds/2;
}
cout<<count<<endl;
}
}
return 0;
}
Well you can combine the different cases into one because the answer can be either of the two i.e. n/2 or n/2 + 1.
It does not make significant difference between the Editorial Vs Solution code as long as both of them have same time and space complexity which in this case is O(1).
In problem statement, K is zero-indexed but digits are from 0 to k-1. It means in your first test case-
2 9 5
K is equal to 2 which means it has digits from d0 to d(k-1) => d(2-1) => d1.
So there are only 2 digits 9 and 5, and as 9+5=14 is not divisible by 3 so the answer should be NO.
You can check 2nd test case given in the problem statement is-
5 3 4
the number N is 34748 which has 5 digits as equal to given k. So i suggest you should yourself read the problem statement carefully.
1 Like
Thanks for pointing out a bug in the program I will update it, but however the solution is accepted by Online Judge even though it is giving wrong answer for the case 2 9 5
I guess this must be the reason I’m not getting AC in the problem.
Please tend to share submission link instead of pasting code.
If you have not solved the problem till now, what you can do is, write a brute force solution and run it on the possible test-cases where you think your optimised solution can give wrong answers. You will know what you are doing wrong.
Can you format your code or share the link, moreover can you tell me which problem you are trying to solve?
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.