Codechef Problem – Krillin is dead AGAIN

The link to problem : https://www.codechef.com/problems/KRILLIN Solution I would like you to read about segment trees before further reading solution if you don't know as it is a prerequisite for this problem. http://codeforces.com/blog/entry/15890 https://codeforces.com/blog/entry/18051 Now we will build our segment tree in which each node will be storing frequency i.e. the array's elements, the value(index) and …

Codechef Problem – Total Diamonds

The link to problem : https://www.codechef.com/problems/VK18 Solution Let us consider an example for n=6. The room numbers for following 36 rooms can be written as 2   3   4   5   6   7 3   4   5   6   7   8 4   5   6   7   8   9 5   6   7   8   9   10 6   7   8   9  10  11 7  …

Codeforces Problem – Useful Decomposition

The link to problem : http://codeforces.com/contest/981/problem/C Solution The question says that there should be atleast one vertex common for every path and we shall be able to visit every node without repeating any edge. For this we need to firstly make adjacency list for the given inputs. When we have made adjacency list then we need …

Codechef Problem – Best Cake Ever

The link to problem : https://www.codechef.com/problems/KMXOR Solution We take an example to understand the solution. Binary representation of 9 is 1001 Because we have to make maximum XOR so it is obvious for n=1 we will print k. Now, for n=2 what we can observe is that if we take complement of k and XOR with …

Codechef Problem – Minimum SubArray

The link to the problem : https://www.codechef.com/problems/MINSUBAR Solution First of all we will take the prefix sum of the array. eg:- Consider array  4 5 3  -2 -1 4 Prefix array       4 9 12 10 9 13 Now, to find sum of a subarray from index j+1 to i we will do prefixArray[i]-prefixArray[j] Now we …

Solving Linear Recurrence Relation

Definition :  A linear recurrence relation is a function or a sequence such that each term is a linear combination of previous terms. Each term can be described as a function of the previous terms. A famous example is the Fibonacci sequence: f(i) = f(i-1) + f(i-2) Linear means that the previous terms in the …

Fast Modular Exponentiation

The idea is that using modular multiplication rules we can calculate modulus for high power numbers. eg:- 565 % mod where mod is generally (109+7) which is a prime number. 51  % mod = 5 52  % mod = ( 51  x 51 ) % mod 54  % mod = ( 52  x 52 ) % mod 58  % mod …