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 … Continue reading Codechef Problem – Krillin is dead AGAIN
Tag: coding
Internship
Coding Prep InterviewBit - Highly recommended, a go-to site for preparation and will single handedly fulfill all your preparation needs. Contains various Coding/DSA questions asked in previous interviews to candidates. Allows you to get a feel for how well you know your stuff. Requires basic DSA knowledge, recommended to read a bit of the initial … Continue reading Internship
Problems with Java for Competitive Programming
Many of you who used to do competitive programming in Java might sometimes wonder that why a particular logic is working fine in C or C++ while the same logic gives TLE or RunTime Error(usually it is TLE). Well this is due to internal implementation of functions and classes in Java. To avoid these things you should … Continue reading Problems with Java for Competitive Programming
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 … Continue reading Codechef Problem – Total Diamonds
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 … Continue reading Codeforces Problem – Useful Decomposition
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 … Continue reading Codechef Problem – Best Cake Ever
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 … Continue reading Codechef Problem – Minimum SubArray
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 … Continue reading Solving Linear Recurrence Relation
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 … Continue reading Fast Modular Exponentiation