Codephrenia 2.0 Guide

Aakash Jaiswal
Sep 4, 2018 · 3 min read

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

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade