Euler Totient Function

Hello Coders,

I am writing this blogpost after a very long time. I am really sorry for that. :(

This blogpost is related to a mathematical topic which is Euler Totient function and there are many problems which are based on this mathematical concept.

What is Euler Totient Function?
It is a function which takes the input an integer n and in return it gives the number of relatively prime numbers to n which are smaller than it.

Code Chef: February Challenge First Five

Chef And His Characters:

This problem is straight-forward. Check every substring of length four and find if the 4 characters of string are 'c', 'h', 'e' and 'f'.

Complexity: Linear per case.
Link to my C++ code!  

Code Chef january challenge unofficial editorial for first 5 problems

Rectangle:

This is the easiest problem of the contest. Opposite sides of a rectangle are equal. So use this property to see if there are 2 pairs of equal sides.

Longest increasing subsequence

Contents:

1. Wtf is Longest increasing subsequence?
2. Dynamic programming approach to find the length.
3. O(nlog(n)) solution to find length using binary search.

Heaps and Priority Queue

Contents:

1. Heaps and Priority Queue
2. Types of Heap
1. Min-heap
2. Max-heap
3.  Some uses of heap with their complexities.
4.  Problem from Hackerearth:
1. Brute Force solution
2. Solution using priority_queue

Square Root Decomposition with range updates

Hello guys! Hope you all are doing well.

In Codechef December challenge I came across a very interesting problem which can be solved using square root decomposition. So i am gonna explain the algorithm using that particular problem. Link to problem.

Pre-requisites: properties of XOR operation.

Lazy Propagation on segment tree

LAZY PROPAGATION

This is for the update query in the minimum range query question.The brute force method involves
various updates in the segment tree for just one query.However ,in lazy propogation,the update is
only propogated to the child nodes as and when it is required i.e. we maintain another array which
keeps the track of all the previous updates which have not been made yet in the segment tree and
will update only when there is a query on that particular range.