[Algorithms] Suffix Automata (DAWG)

KeyWords: string-matching, pattern-matching, indexing, inverted text, finite-automata, suffix-trees, suffix-automata,suffix-tries, factor-automata, music identification, Directed Acycle Word Graph (DAWG).

Let me name some common problems on string.

finding Least Common String of strings, Sub String search, Palindromes, Angarams, Dictionary search, Commonly occuring string (Atom String), unique significant substring/pattern, least common prefix, least common suffix, whats not in the list.

The key point for solving all of these problems is , maintain all data about a string.
All data about a string means {All prefix substrings,All suffix substrings, All sub-strings} .

What matters here ??

You can solve string related problems using, either Brute Force method or using some Data Structure which will allow you to store data about string, considering your time/space complexities.

    the way your data-structure stores data about  the string? -Time and space taken for processing of the string.
    the way your data-structure retrieves data about the string?- Query response time /time taken to retrieve the data.

If you are going to use data-structures, here are the few structure that you'll obvisouly look out for.



Data about strings can be comprised in either a Suffix-Tree/Trie or Suffx-Array or Finite-Automata or Factor-Oracle.

So many people did a vast research on the area of string processing.If this area interests you as well, then you should go throught the sources mentione at the end of this post.

Since, space-time are driving factors in dealing with large data, i prefer to construct a suffx automata(DAWG), for the problems on strings.

Examples of DAWGs:

For String ""

For String "a"

For String "aa"

For String "ab"

For String "aba"

For String "abb"

For String "abbb"

Explanation(Example String: "GCAGAGAG"):

State-3 is cloned as State-6 while inserting 2nd 'A', after state-4, to allow DAG Flow for the suffix string AGAGAG,AGXXXX
State-4 is cloned as State-8 while inserting 2nd 'G', after state-6, to allow DAG Flow for the suffix string GAGAG,GAXXX.
...Just do some work around on this string further, you will understand.

Constructing Suffix-Automata in O(N)-Time / O(N logK) space(Forward DAWG Matching algorithm):

Forward DAWG Matching algorithm, which is smallest suffix automation with Deterministic Finite Automaton.

How to Construct:
1. Define the state
    typedef struct state{
        int length;             //Length of the DAWG till this state
        state* prev;            //Link to previous transition state in the DAWG
        state* next[ALPHA_MAX]; //Links to next transition state in the DAWG
    } state;

2. Automata is constructed with set of states and transition from state-to-state. 
So define your Automata which comprises of the states, variables to track states and methods that enables to do state transitions.
    typedef struct SAM{
        /*FSM Variables*/
        state pool[MAX];        //You need a pool of states, from where you can pick a raw state to include in the DAWG.    
        int count;              //You need to track number of states present in the DAWG.
        state* head,last;       //You need to track your head of the DAWG and last State of the DAWG.

        /*FSM Methods*/
        void SAM_init();            //Initialize your Finite state Machine.
        voidSAM_extend(int input);  //Based on the  input extend states in your FSM(Finite State Machine)
    } SAM;

3. Initialization of FSM.
    void SAM::SAM_init(){
            memset(pool,0,sizeof(pool));
            count=0;
            head=last=&pool[count++];
    }

4. Extending the FSM.
    void SAM::SAM_extend(int input){
        state* new_state = &pool[count++];
        new_state->length = 1 + last->length;
        state* p = last;
        for( ; p && !p->next[input]; p->next[input]=new_state,p=p->prev);
        if(!p){
            new_state->prev = head;
        }else{
            state* q = p->next[input];
            if(p->length +1 == q->length){
                new_state->prev = q;
            }else{
                state* clone = &pool[total++];
                *clone = *q;
                clone->length = p->length +1;
                for(;p && p->next[input]==q;p->next[input]=clone,p=p->prev);
                new_state->prev = q->prev = clone;
            }
        }
        last = new_state;
    }

5. You can include other methods, If required (like below method, which i used it for the traversal of the DAWG.)
    void SAM::SAM_traverse(state** p,int& len,int input){
        while(*p!=head && !(*p)->next[input]){
            *p = (*p)->link;
            len = (*p)->length;
        }
        if((*p)->next[input]){
            *p = (*p)->next[input];
            len++;
        }
    }

Sources:
http://www.cs.nyu.edu/~mohri/pub/nfac.pdf
http://cbse.soe.ucsc.edu/sites/default/files/smallest_automaton1985.pdf
http://www-igm.univ-mlv.fr/~lecroq/string/fdm.html#SECTION00220
http://e-maxx.ru/algo/suffix_automata
http://www-igm.univ-mlv.fr/~lecroq/string/node1.html

Practise problems:
http://www.spoj.com/problems/LCS/
http://www.spoj.com/problems/LCS2/

SPOJ-2916::Can you answer these queries V

http://www.spoj.com/problems/GSS5/

Typical problem statement can be seen as below.

Problem: Given a array of numbers a[1...n] , and a Query(x1,y1,x2,y2).
Query(x1,y1,x2,y2) = Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.

Lets analyze this query...
Wait a minute...!!
    Have you read my post on GSS1 problem ??
    Have you ever Solved GSS1 problem ??
If your answer is NO, then I suggest you to do that problem first.
http://code.karumanchi.me/2013/07/spoj-1043can-you-answer-these-queries-i.html


Here two cases araises based on {x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.
 Case-1: (x1,y1) and (x2,y2) doesn't overlap.
 Case-2: (x1,y1) and (x2,y2) overlaps.

Case-1::No Overlapping
 result would be (x1,y1).bestRightSum + (y1+1,x2-1).Sum +(x2,y2).bestLeftSum;

Case-2::No Overlapping
 result would be max of
   {
   (x1,x2-1).bestRightSum  + (x2,y2).bestLeftSum,
   (x1,y1).bestRightSum  + (y1+1,y2).bestLeftSum,
   (x2,y1).bestSum
   }




Implementation of the Same - Solution

// =====================================================================================
//       Filename:  GSS5.cpp
//    Description:
//         Author:  BrOkEN@!
// =====================================================================================
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<fstream>
#include<iostream>
#include<sstream>
#include<streambuf>
#include<algorithm>
#include<iterator>
#include<new>
#include<string>
#include<utility>

template< class T >
inline T maxOfThree(T a, T b, T c){
    return max(max(a,b),c);
}

#define FOR(i,a,b) for(typeof((a)) i = (a); i <= (b) ; ++i )
#define REV_FOR(i,b,a) for(typeof((b)) i = (b); i >= (a) ; --i )
#define FOREACH(it,x) for(typeof((x).begin()) it=((x).begin()); it != ((x).end()); ++it)
#define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=((x).rbegin()); it != ((x).rend()); ++it)


using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;

typedef struct node{
    int bestLeftSum,bestRightSum,Sum,bestSum;
   
    node merge(node& l,node& r){
        bestLeftSum = max(l.bestLeftSum,l.Sum+r.bestLeftSum);
        bestRightSum = max(l.bestRightSum+r.Sum,r.bestRightSum);
        Sum = l.Sum + r.Sum;
        bestSum = maxOfThree(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);
    }
   
    node setNode(int val){
        bestLeftSum = bestRightSum = Sum = bestSum = val;
    }
       
} node;


const int MAX = 1<<14;

node T[MAX<<1];
int A[MAX];

void init(int Node,int i,int j){
    if(i==j){
        T[Node].setNode(A[i]);
        return;
    }else{
        int m = (i+j)/2;
        init(2*Node,i,m);
        init(2*Node+1,m+1,j);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

node range_query(int Node,int i,int j,int L,int R){
    if(L > R) return T[0];
    if(i==L && R==j){
        return T[Node];
    }else{
        int m = (i+j)/2;
        if(R<=m){
            return range_query(2*Node,i,m,L,R);
        }else if(L>m){
            return range_query(2*Node+1,m+1,j,L,R);
        }else{
            node resultNode,left,right;
            left = range_query(2*Node,i,m,L,m);
            right = range_query(2*Node+1,m+1,j,m+1,R);
            resultNode.merge(left,right);
            return resultNode;
        }
    }
}

int query(int N,int x1,int y1,int x2,int y2){
    int result =0;
    if(y1<x2){
        result += range_query(1,0,N-1,x1,y1).bestRightSum;
        result += range_query(1,0,N-1,y1+1,x2-1).Sum;
        result += range_query(1,0,N-1,x2,y2).bestLeftSum;
    }else{
        result += maxOfThree(
                    range_query(1,0,N-1,x1,x2-1).bestRightSum  + range_query(1,0,N-1,x2,y2).bestLeftSum,
                    range_query(1,0,N-1,x1,y1).bestRightSum  + range_query(1,0,N-1,y1+1,y2).bestLeftSum,
                    range_query(1,0,N-1,x2,y1).bestSum
                    );
           
    }
    return result;
}

int main(){
    int T=0;
    scanf("%d",&T);

    int N=0,Q=0,x1=0,y1=0,x2=0,y2=0;
    FOR(t,1,T){
        scanf("%d",&N);
        FOR(i,0,N-1){scanf("%d",&A[i]);}
        init(1,0,N-1);
        scanf("%d",&Q);
        FOR(q,1,Q){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            --x1;--y1;--x2;--y2;
            printf("%d\n",query(N,x1,y1,x2,y2));
        }
    }

    return 0;
}

SPOJ-1043::Can you answer these queries I

http://www.spoj.com/problems/GSS1/

Typical problem statement can be seen as below.

Problem: Given a array of numbers a[1...n] , and a query range [x,y].
query(x,y) should return the sub-sequence sum, whose sum is maximum in the interval [x,y].

Lets analyze this query.
Query(x,y) is the maximum of below values where sum(i,j) = a[i]+a[i+1]+......+a[j];

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Seriously whats wrong with coloring -we will come to that part.

Blue::The Color of Left Sum.
Where the range starts at 'x' but ends at any where in [x,y].

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Red::The Color of Right Sum.
Where the range starts at somewhere in [x,y] and ends at 'y'.

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Grey::The Color of Sum of the Elements.
Simply sum of all elements in interval [x,y].

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Green::The Color of nested Query ;).
Well, you can see this as the Query(x+1,y-1).

sum(x,x)	sum(x,x+1)	sum(x,x+2)	..........	sum(x,y-1)	sum(x,y)
	sum(x+1,x+1)	sum(x+1,x+2)	..........	sum(x+1,y-1)	sum(x+1,y)
		sum(x+2,x+2)	..........	sum(x+2,y-1)	sum(x+2,y)
			..........	..........	..........
				sum(y-1,y-1)	sum(y-1,y)
					sum(y,y)

Now, you can understand why i had to use these colors.


Lets maintain 4 values.
 bestLeftSum  - Best of all the Left Sums
 bestRightSum  - Best of all the Right Sums
 Sum  - Sum of all the elements
 bestSum  - well we need this to store resultSum of each query (Nested Query ;))
Logically, Query(x,y).resultSum = max (bestLeftSum,bestRightSum,sum,Query(x+1,y-1).bestSum);

But still the nested query stuff isn't so good O(N^2) :'(.
Why can't we use a tree(SegmentTree) ?? Why not a O(logN) for query??

Lets call the above info {bestLeftSum,bestRightSum,Sum,bestSum} as QueryNode.
and given information about QueryNode(L,M) and QueryNode(M+1,R).

Can't you be able to determine the QueryNode(L,R) with above information??
 QueryNode(L,M) -> l
 QueryNode(M+1,R) -> r

 Then For QueryNode(L,R),
  bestLeftSum = max (l.bestLeftSum,l.Sum+r.bestLeftSum);
  bestRightSum = max (l.bestRightSum+r.Sum,r.bestRightSum);
  Sum = l.Sum+r.Sum;
  bestSum = max(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);

How?? - Check below graphical representation 



Implementation of the Same - Solution

// =====================================================================================
//       Filename:  GSS1.cpp
//    Description:  
//        Created:  05/23/2013 06:41:42 PM
//         Author:  BrOkEN@!
// =====================================================================================
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>

#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)

using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;

inline int max2(int a, int b) {return ((a > b)? a : b);}
inline int max3(int a, int b, int c) {return max2(a, max2(b, c));}

const int MAX = 1 << 16;
int a[MAX];

struct node
{
    int Sum,bestLeftSum,bestRightSum,bestSum;
    
    node split(node& l, node& r){
    } // No Need of Split Function
    
    node merge(node& l, node& r)
    {
        Sum = l.Sum + r.Sum;
        bestLeftSum = max( l.Sum + r.bestLeftSum , l.bestLeftSum );
        bestRightSum = max( r.Sum + l.bestRightSum , r.bestRightSum );
        bestSum = max( max( l.bestSum , r.bestSum) , l.bestRightSum + r.bestLeftSum );
    }
    
    node setValue(int val){
        Sum = bestLeftSum = bestRightSum = bestSum = val;
    }
};

node T[MAX << 1];

void init(int Node, int i, int j) {
    if(i==j) { // Initialize Leaf Nodes
        T[Node].setValue(a[i]);
        return;
    }else{ // Summerize Descendant Nodes Nodes
        int m = (i+j)/2;
        init(2*Node, i, m);
        init(2*Node+1, m+1, j);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

void update(int Node, int i, int j,int idx, int val) { 
// Update element with index 'idx' in the range [i,j]
    if(i==j && i == idx) { // Update the LeafNode idx
        T[Node].setValue(val);
        return;
    }else{ // Summerize Descendant Nodes Nodes
        int m = (i+j)/2;
        if(idx <=m)
            update(2*Node, i, m, idx, val);
        else
            update(2*Node+1, m+1, j, idx, val);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

void range_query(node& resultNode,int Node,int i, int j, int L, int R){ // Search for Node having interval info [L,R] in [i,j]; (i<=L<R<=j)
    if(i==L && j==R){
        resultNode = T[Node];
        return;
    }else{
        int m = (i+j)/2;
        if(R<=m)
            range_query(resultNode, 2*Node,  i, m, L, R);
        else if(L>m)
            range_query(resultNode, 2*Node+1, m+1, j, L, R);
        else{
            node left, right;
            range_query(left, 2*Node,  i, m, L, m);
            range_query(right, 2*Node+1, m+1, j, m+1, R);
            resultNode.merge(left,right);
        }
    }
}


int solve(){

    return 0;
}


int main(){

    int N=0,M=0;
    node res;
    scanf("%d",&N);
    FOR(i,0,N-1){
            scanf("%d", &a[i]);
    }
    init(1, 0, N-1);
    scanf("%d",&M);
    int x,y;
    FOR(i,0,M-1){
            scanf("%d%d",&x,&y);
                range_query(res, 1, 0, N-1, --x, --y);
                printf("%d\n", res.bestSum);
    }

    return 0;
}

SPOJ-1557::Can you answer these queries II

This is one of the difficult problems that i have solved. So i've decided to write an article about how to solve this problem.

Logically the problem statement is exactly like below.

Problem: Given a array of numbers a[1...n] (where duplicates are allowed), and a query range [x,y].
query(x,y) should return the sub-sequence sum, whose sum is maximum in the range [x,y] by satisfying uniqueness criteria.

Assume that a[x...y] is a sub-sequence having unique elements(i.e. with out duplicates).
Lets analyze the query asked for this range.
Query for range {x...y} can be expressed as below, assuming that all the queries {query(i,j) where j<y} were answered already.

query(x,y) =  max {
                 b(x,y),
                b(x+1,y),
                b(x+2,y),
                .
                ..
                ...
                b(y,y)
            }

where b(i,j) is defined as below.

b(i,j) = max {
            a[i],
            a[i]+a[i+1],
            a[i]+a[i+1]+a[i+2],
            ......
            a[i]+a[i+1]+a[i+2]+......+a[j]
        }

Lets go little further, do some sample calculations based on n values.

n-value	possible Queries	b-elements
1	query(1,1)	b(1,1)
2	query(1,1),query(1,2) query(2,2)	b(1,1),b(1,2) b(2,2)
3	query(1,1),query(1,2),query(1,3) query(2,2),query(2,3) query(3,3)	b(1,1),b(1,2),b(1,3) b(2,2),b(2,3) b(3,3)

So you might have already observed the pattern that we are looking for.
Now Formal definitions of query(x,y) and b(i,j).

query(x,y) -> is the sub-sequence sum, whose sum is maximum in all sub-sequences by satisfying uniqueness criteria.
b(i,j)     -> is the maximum sub-sequence in the range[i...j] by satisfying uniqueness criteria.

Algorithm:
    Create an array/segment Tree as 'b'. (Segment tree is suggested, will explain that later)
    For i = 1 to N
        ->update the 'b' by inserting the element a[i].
        ->Answer all the queries query(x,y) where x<=y and y=i. 

How to handle repeativeness of the elements ??

 Assume that a[j] is the element to be inserted, 
           a[j] will make its contribution towards the elements b(i,j) {where i<=j}.
 Insertion operation is done based on the assumption that, 
           all the elements in the range a[i...j] will be unique.

 Lets assume that there is an element a[m] {where i <= m <= j} which is duplicate of a[j].
 By our theory, a[m] might have already made contribution towards the elements b(i,m) {where i<=m}.
 so elements b(k,j)  {where m+1 <= k <= j} can include a[j] which is unique for them now.

 In Other words, a[j] can make contribution to the elmements b(k,j) 
             {where m+1 <= k <= j and m-is the last know position of a[j].}
 i.e
 a[j] can be updated in the range b(last[a[i]]+1,j) which preserves our uniqueness condition.        

Complexity of the Query. ??

    To calculate each b(i,j), logN operations are required.(Worst case).
    To find max of b(i,j), for a query it will take y-x+1 no.of calulations under that element.

    ** b(i,j) is calculated based on below, so total j-i+1 child element calculations.
    {b(i+0,i+0), b(i+0,i+1), b(i+0,i+2).........b(i+0,j)
               b(i+1,i+1), b(i+1,i+2).........b(i+1,j)
                             b(i+1,i+2).........b(i+1,j)
                                      ...........
                                       b(j,j)}

    Total Complexity = O(N) = (j-i+1)O(logN) = O((j-i+1)*logN);
    worst case O(NlogN).
    *** Save the processing time by updating child elements by maintaining a segment Tree. 
        So the complexity will come down to O(logN)

How to maintain the Segment Tree Node.??

/*
    Suppose a[j] is to be updated.
    Please be aware that all the queries with y<j are already Calculated before hand.
    So update the tree only to maintain the queries where y==j.

    i.e. At a certain point of time, after updating a[j],
        Leaf Nodes: will contain info about the range queries required query(1,j),query(2,j),query(3,j).....query(j,j).
        Non-Leaf Nodes: will contain info about controling interval mentioned below them.

    So maintain 4-values at each node.
*/

    struct node{
        int max;  //-> Indicates maximum sum in the interval.
        int evermax;  //-> Indicates maximum sum the history of this range.
        int change;   //-> Indicates the value to be modified in the given range.
        int everchange; //-> Indicates the value to be modified in the history of this range.
    };

For example take the below input.

4
4 -2 3 -2

Inserting the A[4] = -2 in the sequence, the tree will look like.

                        (5,5,0,0)
        (5,5,0,0)                (3,3,-2,0)
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0)

Look at the Leaf nodes, these nodes will address these queries with y==4. May be you can name them as result nodes. :D

                        (5,5,0,0)
        (5,5,0,0)                (3,3,-2,0)
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0)
 q(1,4)          q(2,4)          q(3,4)          q(4,4)  

Look at the Non-Leaf nodes, they will have the control information(change,everchange), may be you can name them as control nodes. ;)

                        (5,5,0,0) -> control the interval (1,4)
        (5,5,0,0)              (3,3,-2,0)
   control the interval (1,2)      control the interval (3,4) -> -2 will be included in (3,4) range only
(0,0,5,5)       (0,0,1,1)       (0,0,3,3)       (0,0,0,0) 

Operations required:
You might have figured out that, after inserting a elment a[j] we are no longer looking at queries query(x,y) where y<j.
Hence we are updating the childrens with the current values as they are being updated.
so Operations required will be,

        updateChilds(node& left,node& right)//with the current insertion values(i.e changes required are propagated.)
        clearNode()                     // Clear the non-Leaf nodes.
        updateNode(node& left,node& right)  // Make control nodes are also capable of mataining the result information.
        setNode(int val)                 //Set result nodes to the respective values.

Following is my code,for which i have got AC after 20 attempts :P.
Be sure to look out for 'long long' ;)

// =====================================================================================
//       Filename:  _GSS2.cpp
//    Description:  
//        Created:  07/25/2013 08:42:25 PM
//         Author:  BrOkEN@!
// =====================================================================================
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>

#define TIMER 0
#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)
template< class T > inline T _max(const T a, const T b) { return (!(a < b) ? a : b); }


using namespace std;

const int MAX = 100001;
const int INF = 0x7f7f7f7f;
//const int INF = 0;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef long long int __int;

typedef struct node
{
    __int max,evermax,change,everchange;
    
    node split(node& l, node& r){
    } // No Need of Split Function
    
    node updateChilds(node& l, node& r){
        l.everchange = _max(l.everchange,l.change+everchange);
        l.change += change;
        r.everchange = _max(r.everchange,r.change+everchange);
        r.change += change;
    }
    
    node setNode(int val){
        change += val;
        everchange = _max(change,everchange);
    }
    node clearNode(){
        change = 0;
        everchange = -INF;
    }
    node updateNode(node& l, node& r){
        max = _max(_max(l.max,l.evermax+l.everchange),_max(r.max,r.evermax+r.everchange));
        evermax = _max(l.evermax+l.change,r.evermax+r.change);
    }
    
} node;

typedef struct query{
    int l,r,p;
} query;

int a[MAX],lastp[MAX<<1],lastq[MAX];
__int ans[MAX];
node T[1<<18];
query q[MAX];


void update(int node, int i, int j, int a, int b, int val) {
    if(a <= i && j <= b) {
            T[node].setNode(val);
    }
    else {
        int m = (i + j)/2;
        T[node].updateChilds(T[2*node],T[2*node+1]);
        T[node].clearNode();
        if(a <= m) update(2*node, i, m, a, b, val);
        if(m < b) update(2*node+1, m+1, j, a, b, val);
        T[node].updateNode(T[2*node],T[2*node+1]);
    }
}

__int range_query(int node, int i, int j, int a, int b) {
    if(a <= i && j <= b){
        return _max(T[node].max,T[node].evermax + T[node].everchange);
    }
    else {
        int m = (i + j)/2;
        T[node].updateChilds(T[2*node],T[2*node+1]);
        T[node].clearNode();
        T[node].updateNode(T[2*node],T[2*node+1]);
        return _max((a <= m ? range_query(2*node, i, m, a, b) : -INF), 
                    (m < b ? range_query(2*node+1, m+1, j, a, b) : -INF));
    }
}

int main(){

    int N=0;    
    scanf("%d",&N);
    FOR(i,1,N){    
        scanf("%d", &a[i]);    
    }
    
    int M=0;    
    scanf("%d",&M);
    FOR(i,1,M){
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].p = lastq[q[i].r];
     lastq[q[i].r]=i;
    }

    FOR(i,1,N){
        update(1, 1, N, lastp[a[i]+100000] + 1, i, a[i]);
        lastp[a[i]+100000] = i;
        for(int j=lastq[i];j;j=q[j].p){
                ans[j]=range_query(1, 1, N, q[j].l, q[j].r);
        }
    }

    FOR(i,1,M){printf("%lld\n", ans[i]);}
    


    return 0;
}

[Algorithms] Binary Indexed Trees

Sources:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
http://demonstrations.wolfram.com/BinaryIndexedTree/
http://www.algorithmist.com/index.php/Fenwick_tree

Basic Idea:
Given a set of 'n' Elements(Set F), then summarize set-F with a resulting data structure Tree(set T), with the equal number of elements as F.

For Each index in T , T[index] summarizes the information about the elements from 'index-2^r+1' to 'index' in F.

In other words, T[index] is responsible for elements F[index-2^r+1] .....F[index], where 'r' is the position of the last occurance of '1'.

Eg: See the below calculation to find out the range of each index[Max Value of index is 15 here].

Note: Neither set F is defined here nor T is derived here. This calculation is given to explain how ranges are considered at each Index of the Tree.

Table of Responsibility

 

Table of Responsibilty (Each index'ed element represents range [m,n]

 

 

Pictorial representation

 

Define the Tree:
Now, since we know responsibility of ranges, set 'Tree' can be derived from a defined set 'F'.

Pictorial Representation

 

How to Implement:
To implement the above idea, we need to follow the below procedures.
1. Find 'r' - i.e the last occurance of '1'.
2. Calulate the range[m,n] for each index based on r of that 'index'.
3. Represent set F as Cumulative frequencies.
4. Build the Tree based on the ranges given. T[index] = C[n]-C[m-1]; where [m,n] is the range covered by index.
5. Supporting required Operations on the implemeted Tree.
    a.Read the cumulative frequency.
    b.Read the actual frequency.
    c.Update the frequency and Update the tree
    d.Given a cumulative frequency, find the index. [This is not required As of now]
    e.UpScale/Downscale the entire frequencies in the Tree and update tree accordingly. etc.

Finding the Last Digit:
Okay, you are given a number 'N' and we need to find the position of last digit '1'.

representing N in binary format binary(N) = a1b   [where 'b' is sequence of 0's and 'a' is sequence of 1's&0's , B is Sequence of all 1's]
representing N'( N's Complement) in binary format binary(N') = (a1b)' +1 = a'1'b'+1 = a'0B +1 =  a'1b

N&N' = a1b & a'1b = (0..0)1(0..0) -> Last occurance of '1' is isolated.

Steps - 2,3,4 are easy to implement. At the end of step-4 , building of the BIT would be completed.

BIT should support necessary operations which are useful in range queries, otherwise its useless.
 

Reading the Cumulative Frequency:
For example, we want to read cumulative frequncy at index=13.

C[13]=C[1101] = Tree[1101] + Tree[1100] + Tree[1000] + T[0000]   = 3 + 11 + 12 + 0 = 26;
(i.e. Toggle the 1's from Right to left till the last; T[0000]=0 always coz we never use T[0], we leave that as it is in BITs;)

//psuedoCode:
    int readCumulative(int idx){
        int sum=0;
        while(idx>0){
            sum += Tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

Reading the Actual Frequency:
Simple approach: Actual frequency can be expressed as below.
    F[idx] =  C[idx]-C[idx-1];

//psuedoCode:
    int readActual(int idx){
        return readCumulative(idx) - readCumulative(idx-1);
    }

But the complexity will be more(2*O(log maxVal)). So think of an optimal way.

C[13] = C[1101] = Tree[1101] + Tree[1100] + Tree[1000] + T[0000];
C[12] = C[1100] = Tree[1100] + Tree[1000] + T[0000];
Their Trees are matched after 12. So start with sum at idx=13 and substract the nodes till they match.

//psuedoCode:
    int readActual(int idx){
        int sum = Tree[idx];
        if(idx>0){
            int z = idx - (idx & -idx);
            idx--;
            while(idx!=z){
                sum -= Tree[idx];
                idx -=(idx & -idx);
            }
        }
    }

Update the frequency and Update the tree:
If index 'idx''s frequency is updated , then all the Tree indexes which holds responsibility for this index are have to be updated.[Where ever the r of this idx is toggled.]

//psuedoCode:
    void update(int idx,int val){
        while(idx <=maxVal){
            Tree[idx] += val;
            idx += (idx & -idx);
        }
    }

UpScale/Downscale the entire Tree:upscale/downscale by factor c.

//psuedoCode:
void scale(int c){
    for(int i=1;i<=maxVal;i++){
        update(i, -(c-1)*readActual(i)/c);
    }
}

//or Simple way is

void scale(int c){
    for(int i=1;i<=maxVal;i++){
        Tree[i] = Tree[i]/c;
    }
}

[Algorithms] Segment Trees

Sources: TopCoder, LetUsKode, StackOverFlow and Google. 
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
http://zobayer.blogspot.in/ 

Segment Trees mostly used for storing data and to provide easy access in range queries.

Basic Idea:

Each non-Leaf Node summarizes the information stored at descenedent leaves.
In Other words, Node 'i' will have summarized info about child Nodes at Kth Level.
    i.e. childs from i*2^k to (i+1)*s^k -1

Majorly two Operations are can be performed on a node in segTrees.
    Merge:     Summarize info stored at descendant nodes.
    Split:    Applying certain operations on descendant nodes.

And the following operations are done one the whole segTree.
    Initialize:    Initialize the segment tree.
    Update:     Update info of the leaf node and propagate the change till the root.
    Query:    Query function to be run over a Range or on a specific node(To check balanced state).

Generalized Code Template (In C++): [Node Structure and Operations done on a Node]

//
//Node Structure
struct node{
        <type> <variable> ;

        node merge(node& l, node& r){
            //Apply your merge logic here.
        }

        node split(node& l, node& r){
            //Apply Split logic here if you have any
        }

        node setValue(){
            //Initialize variable in case of Leafnode creation or updation of a LeafNode
        }

};

Generalized Code Template (In C++): [Operation that can be performed on segTree]

//
// initialization of Nodes
    void init(int Node, int i, int j) {
        if(i==j) { // Initialize Leaf Nodes
            T[Node].setValue();
            return;
        }else{ // Summerize Descendant Nodes Nodes
            int m = (i+j)/2;
            init(2*Node, i, m);
            init(2*Node+1, m+1, j);
            T[Node].merge(T[2*Node],T[2*Node+1]);
        }
    }

//
// Update element with index 'idx' in the range [i,j]
void update(int Node, int i, int j,int idx, <values>) {
        if(i==j && i == idx) { // Update the LeafNode idx
            T[Node].setValue();
            return;
        }else{ // Summerize Descendant Nodes Nodes
            int m = (i+j)/2;
            if(idx <=m)
                update(2*Node, i, m, idx, <values>);
            else
                update(2*Node+1, m+1, j, idx, <values>);
            T[Node].merge(T[2*Node],T[2*Node+1]);
        }
    }

//
// Search for Node having interval info [L,R] in [i,j]; (i <= L < R <= r)
 void range_query(node& resultNode,int Node,int i, int j, int L, int R){
        if(i==L && j==R){
            resultNode = T[Node];
            return;
        }else{
            int m = (i+j)/2;
            if( R <= m )
                range_query(resultNode, 2*Node,  i, m, L, R);
            else if( L > m )
                range_query(resultNode, 2*Node+1, m+1, j, L, R);
            else{
                node left,right;
                range_query(left, 2*Node,  i, m, L, m);
                range_query(right, 2*Node+1, m+1, j, m+1, R);
                resultNode.merge(left,right);
            }
        }
    }

Practice Problems:
http://www.spoj.pl/problems/BRCKTS/  
http://www.spoj.com/problems/GSS3/
http://www.spoj.pl/problems/GSS1/       

[Practice Mode] HackerCup-2013 Round-1 :: DeadPixel

Lession-11: General approach is always successful. For this problem,Just imagine how 'ROBO't Scans the book.
i.e. From left to right or top to bottom or right to left or bottom to top.
If you don't know yet, watch ROBO Movie :P ...Seriously.

Lession-12: Set is another beautiful STL Container that you need to know.

Lession-13: If you want to make use of sort at the best, I recommend not to use any comparator function. Believe it or not It runs out of memory if you use any comparator function.

Lession-14: Love C++ More and More, especially when there is no need to write Deque or Queue or Hashmap or Multimap or Set and other Standard function. Of course there are many languages which are having rich libraries but C++ has its own mark. May be my love towards pointers :P is coming out in dis way :D.

Lession-15: Jintak tak Jintak...Jinta...Jinta tha Thahhh...!! Working on Other problems.

// =====================================================================================
//       Filename:  deadPixel.cpp
//    Description:  
//        Created:  02/07/2013 04:06:57 PM
//         Author:  BrOkEN@!
// =====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iterator>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>

#define TIMER 1
#define MAX 40000

#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
#define FOREACH(it,a) for(typeof(a.begin()) it=a.begin(); it != a.end(); ++it) 

using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef deque<PI> DQ;
typedef long long LL;

int W=0,H=0,P=0,Q=0,N=0,X=0,Y=0,a=0,b=0,c=0,d=0;
VI v;
DQ xs;


int getPossible(){
	set<int> k;
	FOREACH(i,xs){k.insert((*i).second);}
	k.insert(H);	
	
	int d=0,pre=-1;
	FOREACH(i,k){
		if((*i)-pre-1 >= Q){
			d+=((*i)-pre-1)-Q+1;
		};
		pre= *i;
	}

	return d;
	
}

LL solve(){
	v.clear();

	v.push_back(PI(X,Y));
	FOR(i,1,N-1){
		v.push_back(PI((v[i-1].first * a + v[i-1].second * b + 1) % W ,(v[i-1].first * c + v[i-1].second * d + 1) % H));	
	}	
	
	sort(v.begin(),v.end());

	LL sum=0LL;
	xs.clear();
	
	VI::iterator it=v.begin();
	FOR(d,0,W-P){
		while(!xs.empty() && ((xs.front()).first<d)){
			xs.pop_front();
		}

		while(it!=v.end() && (*it).first<=P-1+d){
			if(	(xs.empty()) || 
				((xs.back()).first<(*it).first) || 
				(((xs.back()).first==(*it).first) && ((xs.back()).second<(*it).second))
			){
				xs.push_back(*it);
			}
			++it;
		}
		sum+=(LL)getPossible();
	}
	return sum;
}

int main(){
#ifdef TIMER
	clock_t t=clock();
#endif
	int T=0;
	scanf("%d",&T);
	FOR(t,1,T){
		scanf("%d %d %d	%d %d %d %d %d %d %d %d",&W,&H,&P,&Q,&N,&X,&Y,&a,&b,&c,&d);
		printf("Case #%d: %lld\n",t,solve());
	}

#ifdef TIMER
	printf ("It took %f seconds to run.\n",((float)(clock()-t))/CLOCKS_PER_SEC);
#endif	
	return 0;
}

[Practice Mode] HackerCup-2013 Round-1 :: Security

Lession-7: Match finding is always an easy job, If you know HopCraft-Karp algorithm.

Lession-8: Lexicographic means Lexicographic, nothing else. You have a very small meta-dictionary Keep that in Mind. :P

Lession-9: Continue to read standard algorithms. :D

Lession-10: If you think that it can be fixed, It can be fixed.

// =====================================================================================
//       Filename:  security.cpp
//    Description:  
//        Created:  02/03/2013 01:22:50 AM
//         Author:  BrOkEN@!
// ====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>

#define TIMER 1
#define NIL 0
#define INFINITE 1000
#define KMAX 101
#define MMAX 51
#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef set<VI> vS;

char k1[KMAX],k2[KMAX];
int m=0,l=0;
bool dp[MMAX][MMAX];
int H[2*MMAX][3];



bool compare(int a,int b){
 int x=l*a,y=l*b;
 for(int i=0;i<l;i++){
  if( (k1[x+i]!='?') && (k2[y+i]!='?') && (k1[x+i]!=k2[y+i])){
   return false;
  }
 }
 return true;
}


bool bfs(){
 queue<int> Q;
 FOR(v,1,m){
  if(H[v][1]==NIL){
   H[v][0]=0;
   Q.push(v);
  }else{
   H[v][0]=INFINITE;
  }
 }
 H[NIL][0]=INFINITE;
 while(!Q.empty()){
  int v=Q.front();Q.pop();
  if(H[v][0] < H[NIL][0]){
   FOR(u,1,m){
    if(v<=m && dp[v-1][u-1] && H[H[u+m][2]][0]==INFINITE){
     H[H[u+m][2]][0]=H[v][0]+1;
     Q.push(H[u+m][2]);
    }else if(v>m && dp[u-1][v%m -1] && H[H[u][2]][0]==INFINITE){
     H[H[u][2]][0]=H[v][0]+1;
     Q.push(H[u][2]);
    }
   }
  }
 }
 return (H[NIL][0]!=INFINITE);
}


bool dfs(int v){
 if(v!=NIL){
  FOR(u,1,m){
   if(v<=m && dp[v-1][u-1] && (H[H[u+m][2]][0]==H[v][0]+1) && dfs(H[u+m][2])){
    H[u+m][2]=v;
    H[v][1]=u+m;
    return true;
   }else if(v>m && dp[u-1][v%m -1] && (H[H[u][2]][0]==H[v][0]+1) && dfs(H[u][2])){
    H[u][2]=v;
    H[v][1]=u;
    return true;
   }
  }
  H[v][0]=INFINITE;
  return false;
 }
 return true;
}

bool hopCK(){
 FOR(i,0,2*m){H[i][0]=INFINITE;H[i][1]=NIL;H[i][2]=NIL;}
 
 int matching=0;
 
 while(bfs()){
  FOR(v,1,m){
   if((H[v][1]==NIL) && dfs(v)){ matching++; }
  }
 }

 return (matching==m); 
}

bool solve(){
 l=strlen(k1)/m;
 
 FOR(i,0,m-1){FOR(j,0,m-1){dp[i][j]=compare(i,j);}}

 if(!hopCK()){return false;} // Do you there won't be a matching exists, then just quit :P

 FOR(i,0,strlen(k1)){
  if(k1[i]=='?'){
   k1[i]='a';
   while(k1[i]<='f'){ 
    FOR(j,0,m-1){dp[i/l][j]=compare(i/l,j);}
    if(hopCK()){ break; }
    k1[i]++;
   }
   if(k1[i]=='g'){ return false; }
  }
 }
 
 return true;
}

int main(){
 clock_t t=clock(); 
 int T=0;
 scanf("%d",&T);
 FOR(t,1,T){
  scanf("%d\n%s\n%s",&m,k1,k2);
  if( solve())
   printf("Case #%d: %s\n",t,k1);
  else
   printf("Case #%d: IMPOSSIBLE\n",t);
 }
  
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}

[Practice Mode] HackerCup-2013 Round-1 :: CardGame

Lession-1: Don't rush...Keep calm and settle down when you know the logic already.

Lession-2: 1,000,000,007 Is a Magic Number :P and Do Not IGNORE it.

Lession-3: Remember the Rule when working with Modulus Operation, "Apply mod before the result".
If you wait until the result to be computed, answers will be tossed away.

(a+b)mod m = (a mod m + b mod m) mod m;
(a*b)mod m = (a mod m * b mod m) mod m; 

Lession-4: Arrays are the Most beautiful data structure that you ever seen :D. Do not hesitate to use them to compute nCr and etc.

Lession-5: Every problem will have simple solution. Think smart not Bigger.

Lession-6: If you see a Modulus, be ready to solve it. Because modulo randomization always periodical. So Gear up.

// =====================================================================================
//       Filename:  cardGame.cpp
//    Description:  
//        Created:  02/02/2013 11:44:39 PM
//         Author:  BrOkEN@!
// =====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>


#define TIMER 1
#define NMAX 10001
#define MOD 1000000007L

#define FOR(i,a,b) for( typeof(a) i=(a); i < (b) ; ++i )

using namespace std;

int N=0,K=0;
long a[NMAX];
long nCr[NMAX][NMAX];


long solve(){
 sort(a,a+N);
 long sum=0L;K--;
 FOR(i,K,N){
  sum+=(a[i]%MOD * nCr[i][K]%MOD)%MOD;
 }
 return sum%MOD;
}

void preCompute(){
 FOR(i,0,NMAX){
  FOR(j,0,i+1){
   if(j==0) nCr[i][j]=1%MOD;
   else nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%MOD;
  }
 }
}

int main(){
 clock_t t=clock();
 preCompute();
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%d %d",&N,&K);
  for(int i=0;i<N;i++){scanf("%ld",&a[i]);};
  printf("Case #%d: %ld\n",t,solve()); 
 } 
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}

Facebook Hacker Cup 2013 Qualification Round(Solutions)

No intro is required.

you can find the qualification round problems in the below link.

https://www.facebook.com/hackercup/problems.php?round=185564241586420

Among the three problems, Problem1 and Problem2 are very easy if you come up with the logic soon.
And the third one is straight forward question with a very good logic.

Beautiful strings:
Like every one i started thinking very straight forward for this question, i.e. I need to process the sample data first to get the key string/algorithm as it is appears to be some kind of ciphering method is behind the scenes. 

ABbCcc with the answer 152, so i thought Ca(a)=24, Ca(b)=25 and Ca(c)=26.
So I was started thinking that its Caesar Cipher with shift 24.

So i continued to the second example. Kabooooommm...I was wrong :P

Still i was checking all the ciphering algorithms i knew substitution,transposition, rotational and Affine cipher etc etc.

Wait a minute, what if characters are assigned with values such that the Beauty(a.k.a. weight) of the string is maximized....it will become more beautiful right :P

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 501

char str[MAX];

int findBeautyOfString(){
 int d[26]={0};
 int sum=0,i=0;
 while(str[i]!='\0'){
  if(isalpha(str[i])){d[tolower(str[i])-'a']++;}
  i++;
 } 
 sort(d,d+26);
 for(int i=1;i<=26;i++){sum+=i*d[i-1];} 

 return sum;
}


int main(){
 //ios_base::sync_with_stdio(false);

 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//tweak to skip first line

 for(int t=1;t<=m;t++){
  cin.getline(str,MAX); 
  printf("Case #%d: %d\n",t,findBeautyOfString());
 }

}

Balanced Smileys
Simple logic. Process the characters in forward direction and based on the result of the remaining string evaluate whether it is a balanced string or not.
Its like balanced parenthesis problem, but here we need to ensure that additional decisions have made proper if a smiley is observed.

#include<iostream>
#include<sstream>
#include<fstream>

#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 101

char str[MAX];
int n=0;

bool balanced(int index,int right){
 if(index==n){
  if(right>0){
   return false;
  }
  return true;
 }

 if(str[index]==')' && right==0)  return false;
 if(str[index]=='(')  return balanced(index+1,right+1);
 if(str[index]==')')  return balanced(index+1,right-1);
 if(str[index]==':' && index<n-1 && (str[index+1]==')'||str[index+1]=='(')){
   return balanced(index+2,right)|balanced(index+1,right);
 }
 return balanced(index+1,right);
}


int main(){
// ios_base::sync_with_stdio(false);
 
 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//Tweak to skip first line due to the usage of scanf to get m.

 for(int i=1;i<=m;i++){
  cin.getline(str,MAX);
  n=strlen(str);
  printf("Case #%d: %s\n",i,(balanced(0,0)?"YES":"NO"));
 }
}

Find the Min
This is the problem in which i felt ashamed for never trying to code python.
And I came to know about the power of python.
Logic is simple but the implementation is cumbersome for this problem considering the large data set range, which will make you to go mad to think.

For this one, i have first implemented with the use of hash map in cpp.
But i adopted a brute force method to find the n elements.
For small data set it was working but when it comes to large data set, memory allocation problems(Out of memory and glibc errors as i was coding in ubuntu) etc etc.

/*
Based on Hashmap
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define INS pair<int,int>

using namespace std;


map<int,int> m1,m2;
map<int,int>::iterator it1,it2;



int findNthNumber(int n,int k,int a,int b,int c,int r){
 m1.clear();
 m2.clear();
  
 printf("FindNumber: %d %d %d %d %d %d\n",n,k,a,b,c,r); 
 m2.insert(INS(-1,-1));
 m2.insert(INS(9999999,9999));
 m1.insert(INS(0,a));
 m2.insert(INS(a,0));
 it1=m1.begin();
 for(int i=1;i<k;i++){
  m1.insert(INS(i,(((b*(*it1).second)+c)%r)));
  ++it1;
  m2.insert(INS((*it1).second,(*it1).first));
 } 
   for(;it1!=m1.end();++it1){
    cout<<(*it1).first<<"\t"<<(*it1).second<<endl;
   }

 map<int,int>::iterator min,max,del1,del2,last;
 min=max=m2.begin();
 max++;
 int i=k;
 while(i<n){ 
  while((*min).first+1==(*max).first){
   last=m2.end();
   --last;
   if(max==last){
    min=max=m2.begin();
   }else{
    min=max;
   }
   ++max;
  }
  
  while((*min).first+1<(*max).first){
   
   
   m1.insert(INS(i,(*min).first+1));
   m2.insert(INS((*min).first+1,i));
   ++min;
   
   del1=m1.find(i-k);
   del2=m2.find((*del1).second);
   
   
   m1.erase(del1);
   if(del2==min){
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if((*del2).first < (*min).first){
    min=del2;
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if(del2==max){
    ++max;
    if(max==m2.end()){
     min=max=m2.begin();
     ++max;
    }
    m2.erase(del2);
   }else{
    m2.erase(del2);
   }
   
   if(i==n-1){
    last=m1.find(i);
    return ((*last).second);
   }
   i++;
  }
 }


 return 0;
}

int main(){
// ios_base::sync_with_stdio(false);
 
  
 
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  int n=0,k=0,a=0,b=0,c=0,r=0;
  scanf("%d %d\n%d %d %d %d",&n,&k,&a,&b,&c,&r); 
  if(t==3) 
  printf("Case #%d: %d\n",t,findNthNumber(n,k,a,b,c,r)); 
 }
}

Later wrote the code in python, which was working fine but still the same result with large data set. But you know what , I liked python  and it is uber kewl :D.

A pattern was observed when i printed all the elements of the array in the end for a case, in the brute force method. Tada...!! there it is :D simplified. n I have google'd to find out more about "modulo randomization".

Start with 0, keep inserting the numbers if you don't find them last k. 

if you are deleting a front number which is less than the current number inserted you are free to insert that number just after the current number. 

Otherwise increase the number and continue with the procedure.

So on the whole next k+1 elements will have numbers from 0 to k(order will be different). But the same order will be repeated again for next k+1 elements also.
so you need to determine just k+1 elements from which you can make out the nth element.

/*
Based on Array
*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define __int64 unsigned long long int

#define KMAX 100001
#define MAX 200001


using namespace std;

__int64 n=0ULL,k=0ULL,a=0ULL,b=0ULL,c=0ULL,r=0ULL;
__int64 m[MAX]={0ULL};
int s[MAX]={0};

__int64 findNthNumber(){
 for(int i=0;i<MAX;i++){m[i]=0ULL;s[i]=0;} 

 __int64 sMax=k+k+1ULL;
 
 m[0]=a;
 if(m[0]<sMax) s[m[0]]++;
 for(__int64 i=1;i<k;i++){m[i]=(b * m[i-1] + c)%r;if(m[i]<sMax) s[m[i]]++;}
 
 __int64 i=0,j=k;
 
 while(j<sMax){
  while(s[i]==0){
   m[j]=i;
   s[i]++;
   if(m[j-k]<sMax){
    s[m[j-k]]--;
    if(m[j-k]<i && (s[m[j-k]]<=0)){ i=m[j-k]-1;}
   }
   i++;
   j++;
   if(j==sMax){break;}
  }
  i++;
 }
 
 return (m[k + (n - k - 1) % (k + 1)]);
}

int main(){
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%llu %llu\n%llu %llu %llu %llu",&n,&k,&a,&b,&c,&r); 
  printf("Case #%d: %llu\n",t,findNthNumber()); 
 }
}

Linked List Related

Brief list of simple problems based on linked list and their solutions.
Most of them are recursive approaches and they can be written iteratively also.

1.Given a linked-list and 2 integers k & m. Reverse the linked-list till k elements and then traverse till m elements and repeat.
2.Reverse a Linked List(Recursion and Iterative methods).
3.Print Linked List in Reverse & Alternative nodes.

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;



struct node{
 int data;
 struct node *next;
};


void push(struct node **head_first,int data){
 struct node *new_node=NULL;
 new_node=(struct node*)malloc(sizeof(struct node));
 
 new_node->data=data;
 new_node->next=(*head_first);
 *head_first=new_node;
}

void printAll(struct node *head){
 while(head!=NULL){
  cout<<head->data<<"\t";
  head=head->next;
 }
}

void printInReverse(struct node *head){
 if(head==NULL){
  return;
 }
 printInReverse(head->next);
 cout<<head->data<<"\t";
}

void printAlternative(struct node *head){
 if(head==NULL){
  return;
 }
 cout<<head->data<<"\t";
 if(head->next!=NULL){
  printAlternative(head->next->next);
 }
}

struct node* reverseListRecursion(struct node** head_first,struct node** head){
 
 struct node *curr=(*head_first);
 
 if(curr->next==NULL){
  *head=curr;
  return curr;
 }
 
 struct node **next=NULL;
 next=&(curr->next);
 
 reverseListRecursion(next,head)->next=curr;
 
  
 return curr;
}

struct node* reverseListIteration(struct node* head){
 if(head!=NULL){
  struct node* prevN=NULL;
  struct node* currN=head;
  struct node* nextN=head->next;
  
  while(nextN!=NULL){
   currN->next=prevN;
   prevN=currN;
   currN=nextN;
   nextN=nextN->next;
  }
  currN->next=prevN;
  return currN;
 }
}


struct node* reverseList(struct node** root,struct node** head,struct node** revHead,int i,int k){
    if(root==NULL && i<k){
        return NULL;
    }
    
    if(i==k){
        (*head)=(*root)->next;
 (*revHead)=(*root);
        return *root;
    }
    
    struct node* curr=*root;
    struct node* nextN=reverseList(&(curr->next),head,revHead,i+1,k);
    if(nextN!=NULL){
        nextN->next=curr;
    }else{
        return NULL;
    }
    
    if(i==1 && *head !=NULL){
        curr->next=(*head);
        return *head;
    }
    
    return curr;
}

void reverseAndTraverse(struct node *root, int k,int m){
    struct node *kNode=NULL; // K th Node - Assuming Node count from 0 :P
    struct node *revHead=NULL;

    kNode=reverseList(&root,&kNode,&revHead,1,k);
    
    if(kNode==NULL){
        printf("InSufficient Linked List\n");
        return;
    }
    
    int i=0;
    while(i<m && kNode!=NULL){
        printf("%d ",kNode->data);
        kNode=kNode->next;
 i++;
    }    

 cout<<endl; 

  while(revHead!=NULL){
  printf("%d ",revHead->data);
  revHead=revHead->next;
 }
}



int main(){
 struct node *head=NULL;
 
 push(&head,6);
 push(&head,5);
 push(&head,4);
 push(&head,3);
 push(&head,2);
 push(&head,1);
 
 
 cout<<"Printing In Normal:\t";
 printAll(head);cout<<endl;
 
 cout<<"Printing In Reverse:\t";
 printInReverse(head);cout<<endl;

 cout<<"Printing In Alternative:\t";
 printAlternative(head);cout<<endl;
 
 cout<<"Converting to Reverse:\n";
 struct node* revHead=NULL;
 reverseListRecursion(&head,&revHead)->next=NULL; 
 head=revHead;
 
 cout<<"After the Reversal-1:\t";
 printAll(head);cout<<endl;
 
 cout<<"Converting to Reverse Again:\n";
 head=reverseListIteration(head); 
 
 cout<<"After the Reversal-2:\t";
 printAll(head);cout<<endl;
 
 cout<<"Perform Reverse of K and Traversal of M \t";
 int n=1;
 scanf("%d",&n);
 reverseAndTraverse(head,n,3);cout<<endl;

 
}

Create a list of Vertical sum of a given binary tree.

A simple recursive solution would be sufficient enough to solve this.

The approach is to weight each node in the tree as below, starting with root node's weight as 0.

1. Weight of the left child of the node will be less than weight of the root by one.
2. Weight of the right child of the node will be more than weight of the root by one.

By this way the whole tree can be weighted,
and now Sum up all the nodes with same weight which gives the vertical sum of the column of nodes.

Below is implementation, and the results can be stored in either array or list or any DS.

/*
Q: Create a list of Vertical sum of a given binary tree.
*/

struct node{
 int data;
 struct node* left;
 struct node* right;
}

int getHeightOfTree(struct node* root){
 if(root==NULL){
  return -1;
 }
 int l= getHeightOfTree(root->left);
 int r= getHeightOfTree(root->right);
 return ((l>r)?(l+1):(r+1));
}


void buildVerticalSum(struct node* root, int A[], int h, int w){
 if(root!=NULL){
  buildVerticalSum(root->left,A,h,w-1);
  A[h+w]+=root->data;
  buildVerticalSum(root->right,A,h,w+1);
 }
}

/* Array A will have vertical sums of the tree. This can be modified to create a list. Or in Other DS*/
void verticalSum(struct node* root){
 int h=getHeightOfTree(root);
 
 int* A=NULL;
         A=(int*)malloc(sizeof(int)*(2*h+1));
 
 buildVerticalSum(root,A,h,0);
 
 for(int i=0;i<2*h+1;i++){
  printf(“%d ”,A[i]);
 }
 printf(“\n”); 
 
}

Given a String of Length N, find all combinations of substrings of length k(Repetition Allowed)

Print all combination of given length k possible with characters available in a given string "S" with repetition in new lines.
Again an easy recursion problem.

void printAllCombinationsOfLengthK(char in[],int n,char* out,int k,int l){
	if(k==l){
		printf("%s\n",out);
		return;
	}
	for(int i=0;i<n;i++){
		out[l]=in[i];
		printAllCombinationsOfLengthK(in,n,out,k,l+1);
	}
}

int main(){
    ios_base::sync_with_stdio(false);
	
	char* a="abcdef";
	int k=3;
	char op[k]; // Output string of length K
	
	printAllCombinationsOfLengthK(a,strlen(a),op,k,0);

    system("PAUSE");
}

Define the tree, such that the parent node always contains the sum of children nodes.

Simple. I think, no explanation is required for this.

Get summation values of right sub-tree and left sub-tree, and add them to current node's data and update.

/*Define the tree, such that the parent node always contains the sum of children nodes.*/
int sumUp(struct node *root){
 if(root==NULL){
  return 0;
 }else{
  int l=sumUp(root->left);
  int r=sumUp(root->right);
  root->data=root->data + l + r;
  return root->data;
 }
}

Change the structure of a Tree node to hold a pointer for the next in-order element (sucessor).

Idea is simple, based on Threaded Trees concept.
We need to modify Morris In-Order Traversal algorithm a little to convert the tree into a linked list, where each node's right pointer will point to its in-order successor.

There is no need to change the current tree node structure.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*Tree to InOrder list conversion*/
struct node*  MorrisInOrderConversion(struct node* root){
 struct node *curr,*pre,*head=NULL;
 
 if(root==NULL){
  return NULL;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   if(head==NULL){
    head=curr;
   }
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    struct node* next=curr->right;
    struct node* temp=curr->right;
    curr->right=NULL;
    while(next->left!=NULL){
     next=next->left;
    }
    curr->right=next;
    curr=temp;
   }
  }
 }
 
 return head; //Returns head of the converted list
}

/*Traverse the Converted list*/
void traverseList(struct node* head){
 while(head!=NULL){
  printf("%d ",head->data);
  head=head->right;
 }
}

And One more approach also exists for this, which involves creating a new list without changing current tree structure.

This can be written with Morris In-Order Tree traversal algorithm or Generic In-Order traversal algorithm.

Below is the code for generic traversal algorithm.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*New Node structure defined*/
struct iNode{
 struct node* pNode;
 struct iNode* successor;
};

/*Tree to InOrder List - Start */
void insertINode(struct node* p){
 struct iNode *temp = (struct iNode*)malloc(sizeof(struct iNode));
 temp->pNode=p;
 temp->successor=NULL;
 
 if(iHead==NULL){
  iHead=temp;
 }else{
  iList->successor=temp;
 }
 iList=temp; 
};

void inOrderList(struct node* root){
 if(root!=NULL){
  inOrderList(root->left);
  insertINode(root);
  inOrderList(root->right);
 }
};

void traverseIList(){
 struct iNode *curr=iHead; 
 while(curr!=NULL){
  printf("%d ",curr->pNode->data);
  curr=curr->successor;
 }
}
/*Tree to InOrder List - End */

InOrder Traversal of Tree with out using Stack and Recursion

The idea is to create links to root from predecessor node in the left sub-tree for each node.
When traversal on the current node in done, move to the right child and make that node as current node and follow the same procedure.

1. Start from the root of the current tree, as current node.
2. If current node's left Child is NULL
        print the node data.
        make right of the current node as current.
    else
        If right child of the right most node of the left sub-tree is NULL
           make it as a link to current node.
           make left of the current node as current.
        else
           print the current node data.
           make right of the current node as current.

void MorrisInOrderTraversal(struct node* root){
 struct node *curr,*pre;
 if(root==NULL){
  return;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   printf("%d ",curr->data);
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    pre->right=NULL;
    printf("%d ",curr->data);
    curr=curr->right;
   }
  }
 }
}

Max values of Sliding Window of K, in an Array of length N(>K)

Q: An array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.

It is sliding window. Let array be “1 2 3 4 5 6” and k=2
then Sub arrays {1 2},{2 3},{3 4},{4 5},{5 6}.

For all these sub arrays, maximum of each needs to found.[Array is unordered.]

struct node{ 
 int data, index; 
 struct node next; 
 struct node *prev; 
}; 

struct DQueue{ 
 struct node *front; 
 struct node *rear; 
}; 

struct DQueue createDQ(){ 
 struct DQueue* newNode=(struct DQueue*)malloc(sizeof(struct DQueue)); 
 newNode->front=newNode->rear=NULL; 
} 

bool isDQEmpty(struct DQueue* DQ){ 
 return (DQ->front==NULL); 
} 

struct node* createNode(int data,int index){ 
 struct node* newDQNode=(struct node*)malloc(sizeof(struct node)); 
 newDQNode->data=data; 
 newDQNode->index=index; 
 return newDQNode; 
} 

void pushDQFront(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  temp->next=DQ->front; 
  DQ->front->prev=temp; 
  DQ->front=temp; 
 } 
} 

void pushDQBack(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  DQ->rear->next=temp; 
  temp->prev=DQ->rear; 
  DQ->rear=temp; 
 } 
} 

void popDQFront(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->front; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->front->next->prev=NULL; 
  DQ->front=DQ->front->next; 
  temp->next=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

void popDQBack(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->rear; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->rear->prev->next=NULL; 
  DQ->rear=DQ->rear->prev; 
  temp->prev=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

struct node* frontOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->front; 
} 

struct node* rearOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->rear; 
} 

void maxSlidingWindow(int a[],int n,int k){ 
 int i; 
 struct DQueue* DQ=createDQ(); 

 for(i=0;i<k;i++){ 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
 } 
 printf("%d",frontOfDQ(DQ)->data); 

 for(;i<n;i++){ 
  while(!isDQEmpty(DQ) && frontOfDQ(DQ)->index <= i-k){ 
   popDQFront(DQ); 
  } 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
  printf("%d",frontOfDQ(DQ)->data); 
 } 
} 

int main(){ 
 int a[]={3,5,2,8,2,3,7,9,2,2,44,66,2,23,4,54,2}; 
 int n=sizeof(a)/sizeof(a[0]); 
 int k=4; 
 maxSlidingWindow(a,n,k); 
 system("PAUSE"); 
}

Find two elements which will sum up to a given value, in a Sorted Array.

Given sorted integer array and a given value we have to find two elements which will sum up to a given value.

Since it is a sorted array our job is so easy.

For example, array a is having n element in sorted order
A[0]<A[1]<A[2]<........<A[n-1];

From this we can deduce that,
A[0]+A[1]<A[0]+A[2]<A[0]+A[3].......;
A[0]+A[n-1]<A[1]+A[n-1]<.....<A[n-2]+A[n-1];

Compare from the extreme summations with the given value and increase or decrease the indexes according to the comparison.

Int a[SIZE];
Int a[SIZE];
int n;

void findTwoElementsToN(int a[],int n){
 int i=0;
 int j=sizeof(a)/sizeof(int) -1;
 int sum=0;

 if(i<j){
  sum=a[i]+a[j];
  if(sum<n){
   i++;
  }else if(sum>n){
   j--;
  }else{
    printf(“%d and %d”,a[i],a[j]);
  }
 }
}

Least Common Ancestor of two nodes in a Given Unordered Tree.

There can be three possibilities for finding LCA is a tree.
1. Both nodes belong to left sub-tree.
2. Both nodes belong to right sub-tree.
3. One per each sub-tree.
 In fact 4th possibility is also there, i.e. nodes are not at all present in the tree.

In the first case, Current node can't be the LCA because an CA exist in the left sub-tree.
Similarly, in the second case, Current node can't be the LCA because an CA exist in the right sub-tree.
In the third case, Current node will be the LCA.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
 
 if(root==NULL){
  return NULL;  //If no root  leastCommonAncestor is NULL.
 }

 if(root==p || root==q){
  return root; // Check if the current root is equal to any of the desired node.
 }else{
  struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
  struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
  
  if(l!=NULL && r!=NULL){
   return root; 
  }else if(l!=NULL && r==NULL){
   return l;
  }else if(l==NULL && r!=NULL){
   return r;
  }else{
   return NULL;
  }
 } 
}

Binary Tree Related

Code for the following Questions can be found in below code.

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder, PreOrder, PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

/*
Written By BrOkEN@!

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder,PreOrder,PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>

#define INFINITE 1000000

using namespace std;

struct node{
 int data;
 struct node* left;
 struct node* right;
};

struct trackNode{
 struct node* pNode;
 struct trackNode* parent;
};

struct trackNode *list=NULL,*head=NULL;

void insertTrackNode(struct node* p){
 struct trackNode *temp = (struct trackNode*)malloc(sizeof(struct trackNode));
 temp->pNode=p;
 
 if(list==NULL){
  head=temp;
 }else{
  list->parent=temp;
 }
 list=temp; 
};

/*Find path from root to Specific Node*/
bool trackPath(struct node *root, struct node *p){
 
 if(root==NULL){
  return false;
 }
 
 if(root==p){
  insertTrackNode(root);
  return true;
 }else{
  if(trackPath(root->left,p)||trackPath(root->right,p)){
   insertTrackNode(root);
   return true;
  }else{
   return false;
  }
 }
};

/*Constructing a tree and returning the root*/
struct node* buildTree(){
 struct node* n01=(struct node*) malloc(sizeof(struct node));n01->data=1;
 struct node* n02=(struct node*) malloc(sizeof(struct node));n02->data=2;
 struct node* n03=(struct node*) malloc(sizeof(struct node));n03->data=3;
 struct node* n04=(struct node*) malloc(sizeof(struct node));n04->data=4;
 struct node* n05=(struct node*) malloc(sizeof(struct node));n05->data=5;
 struct node* n06=(struct node*) malloc(sizeof(struct node));n06->data=6;
 struct node* n07=(struct node*) malloc(sizeof(struct node));n07->data=7;
 struct node* n08=(struct node*) malloc(sizeof(struct node));n08->data=8;
 struct node* n09=(struct node*) malloc(sizeof(struct node));n09->data=9;
 struct node* n10=(struct node*) malloc(sizeof(struct node));n10->data=10;
 struct node* n11=(struct node*) malloc(sizeof(struct node));n11->data=11;
 struct node* n12=(struct node*) malloc(sizeof(struct node));n12->data=12;
 struct node* n13=(struct node*) malloc(sizeof(struct node));n13->data=13;
 struct node* n14=(struct node*) malloc(sizeof(struct node));n14->data=14;
 struct node* n15=(struct node*) malloc(sizeof(struct node));n15->data=15;
 
 n08->left=n04;n08->right=n12;
 
 n04->left=n02;n04->right=n06;
 n02->left=n01;n02->right=n03;
 n06->left=n05;n06->right=n07;
 
 n12->left=n10;n12->right=n14;
 n10->left=n09;n10->right=n11;
 n14->left=n13;n14->right=n15;
 
 n01->left=n01->right=NULL;
 n03->left=n03->right=NULL;
 n05->left=n05->right=NULL;
 n07->left=n07->right=NULL;
 n09->left=n09->right=NULL;
 n11->left=n11->right=NULL;
 n13->left=n13->right=NULL;
 n15->left=n15->right=NULL;

 
 return n08;
};

/*InOrder Traversal of Tree with root Node*/
void inOrder(struct node* root){
 if(root!=NULL){
  inOrder(root->left);
  printf("%d ",root->data);
  inOrder(root->right);
 }
};

/*PreOrder Traversal of Tree with root Node*/
void preOrder(struct node* root){
 if(root!=NULL){
  printf("%d ",root->data);
  preOrder(root->left);
  preOrder(root->right);
 }
};

/*PostOrder Traversal of Tree with root Node*/
void postOrder(struct node* root){
 if(root!=NULL){
  postOrder(root->left);
  postOrder(root->right);
  printf("%d ",root->data);
 }
};


/*Find Nodes at distance K from the root(possibility to skip subtree is also provided.)*/
void findNodesAtDistanceK(struct node *root,int k,bool left,bool right){
 
 
 if(root!=NULL){
  if(k==0){
   printf("%d ",root->data);
   return;
  }
  
  if(left==true && right==false){
   findNodesAtDistanceK(root->left,k-1,true,true);
  }else if(left==false && right==true){
   findNodesAtDistanceK(root->right,k-1,true,true);
  }else{
   findNodesAtDistanceK(root->left,k-1,true,true);
   findNodesAtDistanceK(root->right,k-1,true,true);
  }
 }
}

/*Get Height of the node*/
int getHeight(struct node* root,struct node* p){
 
 if(root==NULL){
  return INFINITE;
 }
 
 if(root==p){
  return 0;
 }else{
  int l=1+getHeight(root->left,p);
  int r=1+getHeight(root->right,p);
  if(l>r){
   return r;
  }else{
   return l;
  }
 }
}


int main(){
 int k=3;//Distance
 struct node *root=NULL;
 root=buildTree();
 
 struct node* p=root->right->left->right; //get a random node from Tree

 if(trackPath(root,p)){
  int i=0;
  struct trackNode* prev=NULL;
  while(head!=NULL && i<=k){

   if(prev==NULL){
    findNodesAtDistanceK(head->pNode,k-i,true,true);
   }else{
    findNodesAtDistanceK(head->pNode,k-i,head->pNode->left!=prev->pNode,head->pNode->right!=prev->pNode);
   }
   
   prev=head;
   head=head->parent;
   i++;
  }
 }

 system("PAUSE");
}