Introduction to competitive programming

Trie can insert and search string in O(L) time where L is the length of string,this is much faster than hashtable and binary search tree implementations. Trie Node consist of a collection of Trie nodes and a boolean flag to check whether node is leaf or not.

Tutorial Links

Also Topcoder had excellent explanation about TRIE

Here is the C++ implementation of above Algorithm

/*
  TRIE implementation in C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ALPHABET_SIZE 26
using namespace std;
struct Node
{
 struct Node *child[ALPHABET_SIZE];
 bool isLeaf;
};
struct Node *createNode()
{
 Node *nw=new Node;
 for(int i=0;i<26;i++)
  nw->child[i]=NULL;
 nw->isLeaf=0;
 return nw;
}
void addWord(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
  {
   temp->child[c]=createNode();
  }
  temp=temp->child[c];
 }
 temp->isLeaf=1;
}
bool search(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
   return false;
  temp=temp->child[c];
 }
 if(temp->isLeaf)
  return true;
 else
  return false;
}
void printAllStrings(struct Node *root,string s)
{
 if(!root)
  return;
 if(root->isLeaf)
 {
  cout<<s<<"\n";
  return;
 }
 else
 {
  for(int i=0;i<26;i++)
  {
   if(root->child[i])
   {
 
    printAllStrings(root->child[i],s+(char)('a'+i));
   }
  }
 }
}
int main()
{
 struct Node *root=createNode();
 addWord(root,"abcd");
 addWord(root,"ace");
 if(search(root,"sai"))
  cout<<"Sai found\n";
 else
  cout<<"Sai not found\n";
 if(search(root,"abcd"))
  cout<<"abcd found\n";
 else
  cout<<"abcd not found\n";
 printAllStrings(root,"");
}
 

While learning Some advanced data structures I found Binary Index tree,One of the most intresting data Structure and easy to learn if we are familiar with some bit manipulation Techniques.

I found some tutorials on Internet with great Explanation.

Also Topcoder had excellent explanation about BIT

Here is the C++ implementation of above Algorithm

//C++ implementation of Binary Index Tree
//Array with N elements
//Construction of BIT
//Initialisation
//Updation
//Query Sum of elments in rangle l...r
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[100+1],BIT[100+1],n;
void init()//Initialisation of BIT
{
	for(int i=1;i<=n;i++)
	{
		int val=a[i];
		int idx=i;
		while(idx<=n)
		{
			BIT[idx]+=val;
			idx+=(idx & -idx);
		}
	}
	cout<<"After Initialisation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
void update(int pos,int val)//Update the from that Position
{
	int idx=pos;
	while(idx<=n)
	{
		BIT[idx]+=val;
		idx+=(idx & -idx);
	}
	cout<<"After Updation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
int query(int idx)
{
	int sum=0;
	while(idx>0)
	{
		sum+=BIT[idx];
		idx-=(idx & -idx);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(BIT,0,sizeof BIT);
	init();
	int q;
	cin>>q;	
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int x,val;
			cin>>x>>val;
			update(x,val);
		}
		else
		{
			int x,y;
			cin>>x>>y;
 
			cout<<query(y)-query(x-1)<<endl;
		}
 
	}
}

Problem:

The problem is about re-ordering the given trucks in an increasing order by using a temporary street.We can solve it by using stack

Here is the C++ implementation

#include<cstdio>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int main()
{
    long long n;
     cin>>n;
     while(n)
    {
        long long ans=1;
 
        long long a[n+10];
        for(long long i=1;i<=n;i++)
            cin>>a[i];
        stack<long long>st;
        long long strt=1;
        for(long long i=1;i<=n;i++)
        {
            if(a[i]==strt)
                strt++;
            else
            {
                if(st.empty())
                {
                      st.push(a[i]);
 
                }
 
                else if(!st.empty() && st.top()<a[i])
                {
 
                    ans=0;
                    break;
                }
                else
                    st.push(a[i]);
            }
 
            while(!st.empty() && st.top()==strt)
            {
                st.pop();
                strt++;
            }
        }
        if(!ans)
            printf("no\n");
        else if(strt-1==n && st.empty())
            printf("yes\n");
            cin>>n;
    }
}