Codephrenia 2.0 Guide
Hello everyone.In this article we would briefly discuss all the ques that appeared in https://www.codechef.com/COPH2018 (Codephrenia 2.0).
Problem 1:
https://www.codechef.com/COPH2018/problems/HBDANA
Difficulty : Cakewalk
Well this can easily be solved in O(n*log n) by first sorting the array and then finding sum of k max elements.
Bonus :
Try solving this ques in complexity O(n*log k)
Problem 2:
https://www.codechef.com/COPH2018/problems/ALLFACT
Difficulty: Easy
Well one of the optimal solution for this problem is finding the gcd of entire array by Euclidean Algorithm.This algorithm has time complexity of O(Log min(a, b)). After this we can run a loop from 1 to the gcd of the array and compute the ans.
Problem 3:
https://www.codechef.com/COPH2018/problems/SECPRIME
Difficulty :Easy
All the prime factors of a no can be easily be calculated till running a loop from 2 to sqrt of that number and dividing the number by all its prime factors in each step.If after all iterations the resultant number is greater than 1 the number is prime.
Eg for n=12(initially)
Iteration — — — — — — — value of i(possible divisor) — — — — — — value of n
1 — — — — — — — — — — — — 2 — — — — — — — — — — — — — 6
2 — — — — — — — — — — — — 2 — — — — — — — — — — — — — 3
as 3 is not divisible by 2 increment value of i by 1
3 — — — — — — — — — — — — 3 — — — — — — — — — — — — — 1
Store all this factors in a set or any other equivalent ds and output the value of second last element (if any) or output -1.
Problem 4:
https://www.codechef.com/COPH2018/problems/SAVEANA
Difficulty: Easy-Medium
Time Complexity:O(n)
Prerequisite dynamic programming
Well, this problem can be solved by pre-computing the frequencies of all occurrences of numbers and storing them in a map in O(n)
(More precisely store cumulative prefix and suffix sums )
Now in a single traversal of the array (start from 2nd element till second last element). Implement following algo
initialise ans=0
for i=2 to second last array index(1 based indexing):{
if(element at i is divisible by 3):{
ans+=(no of elements having index less than i and equal to i/3 )*(no of elements having index greater than i and equal to i*i/9)
}
}
print(ans)
Setters solution:
https://www.codechef.com/viewsolution/19955472
Problem 5:
https://www.codechef.com/problems/FINDPSUM
Difficulty: Easy
Time Complexity O(n + q*logn*logn)
Prerequisites : Binary Search , Binary Search Tree/Segment Tree
If we know the time prefix sum at any index in rational time and the prefix sums is strictly increasing monotonically we can use binary search to find the answer. If the presum at any index is more the x, the ans will be sure behind the that and vice versa is also true
To the find sum at any index we can BIT/segment tree (BIT is easier to implement but segment tree is more versatile). Both query and update operation require O(logn)
Solution Link : https://www.codechef.com/viewsolution/19952809
Problem 6:
Difficulty :Easy
Prerequisites : Fermat s little theorem,catalan numbers,fast exponentiation
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
https://en.wikipedia.org/wiki/Catalan_number
Well this is an obvious case of one of the many applications of catalan numbers.
Applying this approach by pre-computing could give run-time error as a large number
Raised to a large number could not fit in limits of long long in C/C++
So we need Fermats little theorem.
To calculate (P raised to power Q)%(prime no say p)
We do:
(P raised to power (Q%p-1))%(p)
Here p was 1e9+7 which is indeed prime.
The only time taken will be to run fast exponentiation which takes almost logarithmic time of the power which the number was raised.
Problem code:
https://www.codechef.com/COPH2018/problems/ANANOEIS
Setters solution:
https://www.codechef.com/viewsolution/19955368
Editorialist solution:
https://www.codechef.com/viewsolution/19814246
For any queries contact undersigned:
Aakash Jaiswal
aakashjaiswal@hotmail.co.in