Inversion Count – SPOJ

In the Question Inversion Count – INVCNT on spoj, you need to print the no. of inversion pairs. The question defines it as – “Let A[0…n – 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A.” So basically an inversion pair is the one in which if indices and the values have invert relation. ( if one is > the other is < ).

The first basic approach which comes to mind is simple Brute Force algo. That is selecting one element(let it be i th) in the array and then checking all the elements ( j index for that matter) after the selected element for the condition Arr[i]>Arr[j], if such pair occurs then count++. But time complexity of this approach is O(n2).

But submitting this solution will lead to TLE (time limit exceeded).

So we need to use some other algo, and the solution uses Merge Function in Merge Sort Algorithm.

Actually when we merge the two sorted array, while comparing elements we can perform the counting of inversion pairs. This can be done as : (for ascending order sorting) When the current element under consideration in right sub-array is smaller than current element under consideration in left sub-array the no of inversion pairs equals to the no. of all the elements after the current element in left sub-array (including itself), in each level of merge sort. Sum of all these pairs will be equal to inversion pairs.

This can be understood using following :

IMG_20150411_231458239_HDR

Here is the following pseudo-code :

#include <iostream>
typedef long long int typex;
using namespace std;
long long int count,arr[200001];
void merge(typex p,typex q,typex r)
{

	//first array has indices from p to q
	//second array has indices from q to p
    typex i,li,ri,n1,n2;
    n1=q-p+1;
    n2=r-q;
    typex *lt= new typex [n1];
    typex *rt= new typex [n2];//[q-(r+1)+1]
    // HERE copy both the arrays in the newly dynamically allocated array.
    //left and right array is ready which is all ready sorted
    //now we will merge
    //indices fr left copy and right copy respectively
    li=ri=0;
    i=p;//index for array being sorted
    while(li<n1 && ri<n2)
    {
        if(lt[li]>rt[ri])
        {
            arr[i++]=rt[ri++];
            count=count+n1-li;// MAIN STEP
        }
         else //right hand side elemnt is greater that is inversion pair
        {
            arr[i++]=lt[li++];
        }
    }
//inversion pairs have been counted till this stage, do not count again;
    while(li<n1)
        arr[i++]=lt[li++];
    while(ri<n2)
        arr[i++]=rt[ri++];
}
void mergesort(typex p,typex r)
{
    if(p<r)
    {
        typex q=(p+r)/2;
        mergesort(p,q);
        mergesort(q+1,r);
        merge(p,q,r);
    }
}
int main()
{
   ////Write code accordingly
        count=0;
        mergesort(0,n-1);
        cout&lt;&lt;"\n"&lt;&lt;count;
	////

}

Complete Solution : https://ideone.com/UBCpT9

Shell Sort

There are many implementations of this sort available,  but in this article I have taken O(n2) implementation.

It is a modified insertion sort such that we are maintaining of the “sorted part” of the insert sort algo, at discrete gaps rather than being contiguous as in normal insertion sort.

Other modified versions : WIKI

#include <stdio.h>
#include <stdlib.h>
void shell_sort(int arr[], int n)
{
    int gap,i,j;
    //we change the gap/ shell size from n/2,n/4......1
    for(gap=n/2;gap>0;gap/=2) //ranges gap = n/2 --->1
    {
        //we perform something similar to insertion sort but rather than taking elements which are adjacent
        //in memory locations we take them at certain "gap" (also the variable name used in code is as same)
        for(i=gap;i<n;i++) //for all elements using the shell length { int temp=arr[i]; for(j=i;j>=gap && arr[j-gap]>temp;j=j-gap) //the insertion step, we jump at elements before i, but by a leap = gap
            {
                arr[j]=arr[j-gap];
            }
            arr[j]=temp;
        }
    }
}

int main()
{
    printf("Enter the array : \n");
    int n, a[]={5,6,8,9,8,7,6,8,4,6,2,1,6};
    n=sizeof(a)/sizeof(int);
    shell_sort(a,n);
    for(int i=0;i<n;i++)
    {
        printf(" %d ", a[i]);
    }

    return 0;
}


Dijkstra’s Algorithm – Shortest Path

Concept of Set can be understood by following code :


#include <iostream>
#include<set>
using namespace std;
int main() {
// your code goes here
set <pair<int,int>> S;
set <pair<int,int>> :: iterator it;
S.insert({2,100});
S.insert({1,200});
S.insert({1,50});
for(it = S.begin();it!=S.end();it++)
{
cout<<(*it).first<<" "<<(*it).second<<endl;

}
return 0;
}

Output:
1 50
1 200
2 100

This property of set can be easily utilized, that set keeps all its elements in kind of sorted order. (using Red-Black Trees)

Check out the code for SPOJ – SHPATH at : http://ideone.com/Ip8Kzf

Psuedocode  from CLRS :

function Dijkstra(Graph, source):
     create vertex set Q
     for each vertex v in Graph:             // Initialization
         dist[v] ← INFINITY                  // Unknown distance from source to v
         prev[v] ← UNDEFINED                 // Previous node in optimal path from source
         add v to Q                          // All nodes initially in Q (unvisited nodes)
     dist ← 0                        // Distance from source to source
     
     while Q is not empty:
         u ← vertex in Q with min dist[u]    // Source node will be selected first
         remove u from Q 
         
         for each neighbor v of u:           // where v is still in Q.
             alt ← dist[u] + length(u, v)
             if alt < dist[v]:               // A shorter path to v has been found
                 dist[v] ← alt 
                 prev[v] ← u 
     return dist[], prev[]

Comparing Input Functions for SPOJ input intensive problem : INTEST

I tried the problem using 4 methods, results of which I have tabulated as following :

Method Time Comparision
Cin  2.72s SLOWEST 
scanf  0.66s  SAFE
cin with sync_with_stdio(false) 0.54s  NICE
getchar_unlocked() 0.11s  FASTEST

If you require fast IO, always use getchar_unlocked(), but remember, with great power comes great responsibility. getchar_unlocked() is not thread safe, getchar_unlocked is a thread unsafe version of getchar( ), and as it does not check for any locks for threads accessing stdin. In short, you can use for normal integer inputs and when having large Input requirements.

Code Example using getchar_unlocked()

#include <iostream>
#include <cstdio>
using namespace std;
#define gc getchar_unlocked
void scan(int &input) //for int only
{
 input = 0;
 register int c = gc();
 for(;(c<48 || c>57);c = gc()); //for omitting spaces or any other character (other than number)
 for(;c>47 && c<58;c = gc()) {input = (input<<1) + (input<<3) + c - 48;} //reading of the number
}
int main()
{

 int n,k,i,ctr=0,x;
 scan(n);
 scan(k);
 for(i=0;i<n;i++)
 {
 scan(x);
 if(x%k==0)
 ctr++;
 }
 cout<<ctr;
 return 0;
}

File IO Operations in C++

Source : http://www.cplusplus.com/doc/tutorial/files/


I am just trying to keep the reading material organised for people and myself, I state that I do not own the following article).


C++ provides the following classes to perform output and input of characters to/from files:

  • ofstream: Stream class to write on files
  • ifstream: Stream class to read from files
  • fstream: Stream class to both read and write from/to files.

For  writing into a file we declare an object of class ofstream and for reading a file object of class ifstream. Steps are as follows :

  1. Creating stream object.
  2. Opening the file
  3. Performing tasks (Reading/Writing)
  4. Closing the file

1. Creating Object

ofstream myfile; //to write
//or
ifstream myfile; //to read

2. Opening File

ofstream myfile;
myfile.open ("example.bin", ios::out | ios::app | ios::binary); 
/*
open (filename, mode);
Where filename is a string representing the name of the file to be opened, and mode is an optional parameter with a combination of the following flags
*/

Combining step 1 and step 2,

ofstream myfile ("example.bin", ios::out | ios::app | ios::binary);
//Using the benefit of the contructor for the class ofstream

 

Member constant Opening mode
app (append) Set the stream’s position indicator to the end of the stream before each output operation.
ate (at end) Set the stream’s position indicator to the end of the stream on opening.
binary (binary) Consider stream as binary rather than text.
in (input) Allow input operations on the stream.
out (output) Allow output operations on the stream.
trunc (truncate) Any current content is discarded, assuming a length of zero on opening.

 

For ifstream and ofstream classes, ios::in and ios::out are automatically and respectively assumed, even if a mode that does not include them is passed as second argument to the open member function (the flags are combined).

For fstream, the default value is only applied if the function is called without specifying any value for the mode parameter. If the function is called with any value in that parameter the default mode (which is both input and output) is overridden, not combined.

To check if a file stream was successful opening a file, you can do it by calling to member is_open. This member function returns abool value of true in the case that indeed the stream object is associated with an open file, or false otherwise:

if (myfile.is_open()) { /* ok, proceed with output */ }

3. Performing Operations

Text Files

// writing on a text file
#include <iostream>
#include <fstream>
using namespace std;

int main () {
  ofstream myfile ("example.txt");
  if (myfile.is_open())
  {
    myfile << "This is a line.\n";
    myfile << "This is another line.\n";
    myfile.close();
  }
  else cout << "Unable to open file";
  return 0;
}
// reading a text file
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main () {
  string line;
  ifstream myfile ("example.txt");
  if (myfile.is_open())
  {
    while ( getline (myfile,line) )
    {
      cout << line << '\n';
    }
    myfile.close();
  }

  else cout << "Unable to open file"; 

  return 0;
}

 

get and put stream objects:

ifstream, like istream, keeps an internal get position with the location of the element to be read in the next input operation.

ofstream, like ostream, keeps an internal put position with the location where the next element has to be written.

Finally, fstream, keeps both, the get and the put position, like iostream.

These internal stream positions point to the locations within the stream where the next reading or writing operation is performed.

tellg() and tellp()

no parameters return a value of the member type streampos,  the current get position (in the case of tellg) or the put position (in the case of tellp).

seekg() and seekp()

allow to change the location of the get and put positions. Both functions are overloaded with two different prototypes. The first form is:

seekg ( position );
seekp ( position );

Using this prototype, the stream pointer is changed to the absolute position position (counting from the beginning of the file). The type for this parameter is streampos, which is the same type as returned by functions tellg and tellp.

The other form for these functions is:

seekg ( offset, direction );
seekp ( offset, direction );

Using this prototype, the get or put position is set to an offset value relative to some specific point determined by the parameter direction. offset is of type streamoff. And direction is of type seekdir, which is an enumerated type that determines the point from where offset is counted from, and that can take any of the following values:

ios::beg offset counted from the beginning of the stream
ios::cur offset counted from the current position
ios::end offset counted from the end of the stream

 


 

Binary Files

For binary files, reading and writing data with the extraction and insertion operators (<< and >>) and functions like getline is not efficient, since we do not need to format any data and data is likely not formatted in lines.

File streams include two member functions specifically designed to read and write binary data sequentially: write and read. The first one (write) is a member function of ostream (inherited by ofstream). And read is a member function of istream (inherited byifstream). Objects of class fstream have both. Their prototypes are:

write ( memory_block, size );
read ( memory_block, size );

 

// obtaining file size
#include <iostream>
#include <fstream>
using namespace std;

int main () {
  streampos begin,end;
  ifstream myfile ("example.bin", ios::binary);
  begin = myfile.tellg();
  myfile.seekg (0, ios::end);
  end = myfile.tellg();
  myfile.close();
  cout << "size is: " << (end-begin) << " bytes.\n";
  return 0;
}
// reading an entire binary file
#include <iostream>
#include <fstream>
using namespace std;

int main () {
  streampos size;
  char * memblock;

  ifstream file ("example.bin", ios::in|ios::binary|ios::ate);
  if (file.is_open())
  {
    size = file.tellg();
    memblock = new char [size];//we request the allocation of a memory block large enough to hold the entire file
    file.seekg (0, ios::beg);
    file.read (memblock, size);
    file.close();

    cout << "the entire file content is in memory";

    delete[] memblock;
  }
  else cout << "Unable to open file";
  return 0;
}

 

 


4. Closing a file

Once this member function is called, the stream object can be re-used to open another file, and the file is available again to be opened by other processes.

myfile.close();

In case that an object is destroyed while still associated with an open file, the destructor automatically calls the member function close.


Concept of Buffer and Syncronization

When we operate with file streams, these are associated to an internal buffer object of type streambuf. This buffer object may represent a memory block that acts as an intermediary between the stream and the physical file. For example, with an ofstream, each time the member function put (which writes a single character) is called, the character may be inserted in this intermediate buffer instead of being written directly to the physical file with which the stream is associated.The operating system may also define other layers of buffering for reading and writing to files.

When the buffer is flushed, all the data contained in it is written to the physical medium (if it is an output stream). This process is called synchronization and takes place under any of the following circumstances:

  • When the file is closed: before closing a file, all buffers that have not yet been flushed are synchronized and all pending data is written or read to the physical medium.
  • When the buffer is full: Buffers have a certain size. When the buffer is full it is automatically synchronized.
  • Explicitly, with manipulators: When certain manipulators are used on streams, an explicit synchronization takes place. These manipulators are: flush and endl.
  • Explicitly, with member function sync(): Calling the stream’s member function sync() causes an immediate synchronization. This function returns an int value equal to -1 if the stream has no associated buffer or in case of failure. Otherwise (if the stream buffer was successfully synchronized) it returns 0.

Boyer-Moore’s Voting Algorithm

Moore’s Voting algorithm has 2 parts –

1. First part of running Moore’s Voting algorithm only gives you A candidate which occurs “most” of the time in the given array.
2. In the second part, we need to iterate over the array once again to determine if this candidate occurs maximum number of times (i.e. greater than size/2 times).

First iteration is to find the candidate & second iteration is to check if this element occurs majority of times in the given array.

So time complexity is: O(n) + O(n) ≈ O(n)

———————————————————

1.Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If count == 0
maj_index = i;
count = 1

(b)If a[maj_index] == a[i]
count++
(c)Else
count–;

3. Return a[maj_index]


2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print “NONE”

Knuth–Morris–Pratt (KMP) algorithm

KMP is a pattern matching algorithm which has very good running time.

Firstly, what is the naive approach solution for pattern matching ? Answer to this question will lead to the key idea behind the KMP algo.

How you go about matching a pattern with a text ? You might search  the first character of the pattern in the text, and after finding that you will try to match the other sequentially appearing characters in  the pattern till you match all or find a mismatch. Bravo, if you find a match but what if you didn’t. You will go back to the point where your first character matched. And start the same procedure from the character next to the first match. This can be seen in the following example : Patterrn Matching Naive

There is an annoying step which we perform if we find a mismatch, that is going BACK to the first character of match. The KMP algo improves the worst time complexity significantly just by eliminating this step of going backwards. Obviously, no one likes to step backwards 😛

Key Concept of KMP algo :

The KMP matching algorithm uses degenerating property – pattern having same subpatterns appearing more than once in the pattern. The algorithm first creates an integer array of size same as that of the pattern and stores some useful information after computing on the text, which it then uses while matching the pattern with the text.

KMP algorithm does some preprocessing over the pattern pat[] and constructs an auxiliary array lps[] of size same as size of pattern (=m). lps = longest proper prefix which is also suffix. For each sub-pattern pat[0…i] where i = 0 to m-1, lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].

For Example :

Let Pattern be FFZFFZFFF :

for i=0 : “F” – Proper prefix = “” and

Proper Suffix = “”                                        lps[0]=0

for i=1 : “FF” – Proper prefix = “F” and

Proper Suffix = “F”

Longest common prefix which is also a suffix = “F” ie length  1, thus lps[1]=1

for i=2: “FFZ” – Proper prefix = “F”,”FF” and

Proper Suffix = “Z”,”FZ”                                      thus lps[2]=0

for i=3: “FFZF” – Proper prefix = “F”,”FF”,”FFZ” and

Proper Suffix = “F”,”ZF”, “FZF”                                      thus lps[3]=1

for i=4: “FFZFF” – Proper prefix = “F”,”FF”,”FFZ”,”FFZF” and

Proper Suffix = “F”,”FF”ZFF”, “FZFF”                                      thus lps[3]=2 (as longest common is “FF”)

for i=5: “FFZFFZ” – Proper prefix = “F”,”FF”,”FFZ”,”FFZF”,”FFZFF” and

Proper Suffix = “Z”,”FZ”FFZ”, “ZFFZ”,”FZFFZ”                                      thus lps[4]=3 (as longest common is “FFZ”)

Similarly lps[i] can be carried out for  whole pattern.

Now this lps[] array is used while matching patterns.

**********

Pseudocode Code for Function to create lps array
Function    create_lps( pat,  size) :
    lps[0]=0
    INITIALIZE i=1 and j=0
    WHILE i < PATTERN.LENGTH:

        if PATTERN at i == PATTERN at j :
            lps[i]=j+1
            i++ and j++ //MOVE i and j ahead

        else //MISMATCH
            if j > 0:
                j=lps[j-1];
            else //when j stands at 0
                //NO PART OF PATTERN till i, HAS LPS
                lps[i]=0
                i++

Pseudocode Code for Function to check pattern
Function KMP_chk():
	WHILE i < TEXT.LENGTH :
		if TEXT at i == PATTERN at j :
			i++ and j++
		else
			if mismatch occurs at j>0
				j=lps[j-1];		//THIS IS THE STEP WHICH AVOIDS GOING BACK TO
			else
                                i++;

		if j== PATTERN.LENGTH	//THAT MEANS TEXT at i == PATTERN at j executed j times only because it matches the pattern
			//PATTERN MATCH FOUND, STORE AND FIND MORE OCCURANCES.

Here is the C++ implementation code

#include <iostream>
using namespace std;
int lens(char *s)
{
    int i;
    for(i=0;s[i]!=0;i++);
    return i;
}
void createlps(char *pat, int *lps, int size)
{
    int i,j;
    lps[0]=0;
    i=1;j=0;
    while(i<size)
    {
        if(pat[i]==pat[j])
        {
            lps[i]=j+1;
            i++;j++;
        }
        else
        {
            if(j>0)
            	j=lps[j-1];
            else
            {
	        lps[i]=0;
                i++;
            }
        }
    }
}

void checkoccurances(char *text, char *pat, int *lps, int sizep, int *occurances)
{
    int i,j,k;
    i=0;k=0;j=0;
    while(text[i]!=0)
    {
        if(pat[j]==text[i])
        {
            i++;
            j++;
        }
        else
        {
                if(j>0)
                    j=lps[i-1];
                else
                    i++;
        }
        if(j==sizep)
        {
            occurances[k++]=i-sizep;
            j=0;
        }
    }
    occurances[k]=-1;
}

int main() {
    char text[5000],pat[50];
    int i,occurances[50];

    cout<<"Enter the text : ";
    cin>>text;
    cout<<"Enter the pattern : ";
    cin>>pat;

    int patlen=lens(pat);
    int *lps= new int [patlen];
    createlps(pat,lps,patlen);
    checkoccurances(text,pat,lps,patlen,occurances);

	cout<<"\n \nOccurances are at indices :";
    for(i=0;occurances[i]!=-1;i++)
    	cout<<occurances[i]<<"   ";
cin.ignore();
    cin.get();
    return 0;
}

Note the similarity in the code of createlps() and checkoccurances()

Reading integer input from a text file in C

Many times you need to read from a text file in order to take input.

So here is one of the way :

I have used the function fscanf().

 

#include <stdio.h>
#include <stdlib.h>
int main()
{
	FILE *textfile=fopen("IntegerArray.txt","r");
	int arr[100050],i,lim,num;
	if (textfile == NULL)
    {
        printf("Error Reading File\n");
        exit (0);
    }
    i=0;
	while(fscanf(textfile, "%d", &num) >0 )
	{
		arr[i++]=num;
	}
    lim=i;
    printf("\n Lim : %d \n",lim);

    for (i = 0; i < lim; i++)
    {
           printf("%d : %d\n",i, arr[i]);
    }
    fclose(textfile);
    return 0;

}

QUICK SORT

The basic outline of the Quick Sort function is to :

1) Find a pivot, place it on correct position(let index be p) in the array(index : s to l ). This will be achieved by a partition function.

2) Quick Sort the sub array (s to p-1).

3) Quick Sort the sub array (p+1 to l).

I have implemented the following code with 2 partition functions :

1st based on Wikipedia’s Algo

2nd based on ###

#include <iostream>
#include <time.h>
using namespace std;
clock_t total_elapsed_time = 0;

int partition(int *arr,int s,int l);

void qsort(int *arr,int s,int l)
{
    int x=partition(arr,s,l);
    if(s<x-1)
    qsort(arr, s, x-1);
    if(x+1<l)
    qsort(arr,x+1,l);
}
int partition(int *arr,int s,int l)
{
    clock_t call_begin = clock();
    int pivot;
    int pval;
    int i,j,temp;

    // ALGO 1 for partition function
    i=s;j=s;
    //i traverses over the array
    //j resides over the element > arr[pivot]
        pval=arr[l];
        pivot=l;
    while(i<l)
    {
        if(arr[i]<pval)
        {
            temp=arr[i];
            arr[i]=arr[j];
            arr[j++]=temp;
        }
        i++;
    }
    temp=arr[l];
    arr[l]=arr[j];
    arr[j]=temp;
    total_elapsed_time+=(clock()-call_begin);
    return j;

    //ALGO 2 for partition function.
    /*
    i=s;j=l;
    pivot=s;
    pval=arr[pivot];
    while(i<j)
    {
        if(pivot==i)
        {
            //make comparision with value at j
            if(!(pval<arr[j]))
            {
                //swap
                temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                //pivot value has been shifted to arr[j]
                pivot=j;
                //now at ith position we have an element we just swapped with pivot, so move ahead at i
                i++;
            }
            else
                j--;
        }
        else
        {
            //this is for pivot==j
            if(!(pval>arr[i]))
            {
                //swap
                temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
                //pivot value has been shifted to arr[i]
                pivot=i;
                //now at jth position we have an element we just swapped with pivot, so move ahead(left) at j
                j--;

            }
            else
                i++;
        }

    }

    total_elapsed_time+=(clock()-call_begin);
    return i;
    */
}
int main()
{
    int i,arr[100],n,t;
    cin>>t;
    while(t--)
    {
        total_elapsed_time=0;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        qsort(arr,0,n-1);
        for(i=0;i<n;i++)
            cout<<arr[i]<<"\t";
        cout<<"\n\nTOTAL TIME ELAPSED in PARTITION FUNCTION : "<<float(total_elapsed_time)/CLOCKS_PER_SEC;
    }

    return 0;
}


Hello world!

Finally, Today I got myself free from all assignments, projects and sheets. (Those Engineering Drawing ones 😛 ) I was planning to write blogs but kept delaying due to busy schedule.

So this is my first blog and on this site I will be posting Algorithms, Solutions to Problems on SPOJ and Some Tips and Tricks in C and C++.