Month: August 2013

Algorithm #2: Primality Testing

One of the important algorithms that a competitive programmer must know are the primality testing algorithms. Solution to some programming problems involve checking if a number is prime or not and it is the algorithm you use to do this that determines if your solution gets accepted.

I’m sure that you all are aware that a number (say, n) is prime if there is no number (say, i ) such that i<n and n%i==0 and i!=1. We can use this fact to write a function that takes a positive number and returns 1 if the number is prime and 0 if the number is not prime.

int isprime(int n)
{
   if(n<2)
      return 0;
   int i=2;
   while(i<n)
   {
      if(n%i==0)
         return 0;
      i++;
   }
   return 1;
}

The complexity of this algorithm is O(n). This is the naive approach for primality testing. Naive approach means a simple approach that is not optimised at all and is not sufficient.

Let me draw your attention to a fact. If I want to find two numbers ( a and b ) for a number n, such that n=a*b, then one of the two numbers will be less than sqrt(n) and the other one will be greater than sqrt(n). Except when a=b=sqrt(n). So, if I don’t find any factor of n less than or equal to sqrt(n), then I can be sure that n is a prime number and there is no need to go all the way to n.

Therefore the condition in the while loop can be modified, and the code will look as follows:

int isprime(int n)
{
   if(n<2)
      return 0;
   int i=2;
   while(i*i<=n)
   {
      if(n%i==0)
         return 0;
      i++;
   }
   return 1;
}

Note that instead of finding sqrt(n), I simply used i*i<=n. This does exactly the same thing as i<=sqrt(n). The complexity of this algorithm is O(sqrt(n)).

But for some problems even this optimised method is not enough. There is another, very efficient way to find prime numbers. This algorithm is known as Sieve of Eratosthenes.

I will explain how the Sieve of Eratosthenes works for a number less than or equal to 100.

We start by writing numbers from 1 to 100 on paper. Cross the number 1 on the paper. Circle the number 2 and cross every multiple of 2. Circle 3 and cross every multiple of 3. We skip 4 as it is crossed (it is a multiple of 2). Circle 5 and cross every multiple of 5. At each step, we find the next smallest number that is not crossed. We circle that number and cross every multiple of that number. We continue this process until all numbers are either circled or crossed. All the numbers that are circled are prime numbers. Now, if I want to check the primality of any number less than or equal to 100, I can simply see if that number is circled or crossed. If it is circled, it is a prime number otherwise it is composite.

So, once we have completed the circling-and-crossing process, we can check the primality of a number in constant time i.e. O(1) time. In a way we ‘precalculate’ the primality of numbers and use this information later on.

In all programming problems the upper limit of numbers is given. Suppose that it is given that all numbers are <=10^7. In this case, I’ll simply run the Sieve of Eratosthenes till 10^7 in the start of the program and later in the program I’ll be able to check the primality of any number <=10^7 in O(1) time.

Following is an implementation in C/C++. I have declared an array ‘isprime’ of size (10^7 + 1) to find prime numbers upto 10^7. If isprime[i]==1, it simply means that the ith number is crossed.

int isprime[10000001]={0},i=2,j;
isprime[0]=1;
isprime[1]=1;
for(i=2;i*i<=10000000;i++)
{
   if(isprime[i]==1)//if the number is crossed, it is skipped
      continue;
   for(j=i*2;j<=10000000;j+=i)// NOTE that j is incremented by i everytime
   {
      isprime[j]=1; // crossing every multiple of i
   }
}

Now whenever I want to check if a number p is a prime number, I’ll observe the value of isprime[p]. If it is 0, then it is prime otherwise it is not.

Lets examine the execution time of this code. The outer loop iterates i from 2 till n(n=10000000 here). The inner loop will iterate only if ‘i’ is not crossed (i.e. If ‘i’ is prime).

For i=2, the inner loop will iterate n/2 times.

For i=3, the inner loop will iterate n/3 times.

For i=5, the inner loop will iterate n/5 times.

For i=7, the inner loop will iterate n/7 times… and so on.

For i= some composite number, the inner loop will iterate 0 times.

Therefore the total times the inner loop iterates is :

( n/2) + ( n/3 ) + ( n/5 ) +( n/7 ) + ( n/11 ) + ( n/13 ) + …

We can take n out from all the terms and we get,

n * summation (1/i), where i is a prime number less than or equal to n. Summation(n/i) is called the harmonic series of primes. Its summation till n approximately reaches log(log(n)). Therefore, the inner loop iterates approximately n*log(log(n)) times

The complexity of Sieve of Eratosthenes is as follows:

For Precalculation : O(n* log(log(n)))

For each query : O(1)

If you don’t understand how we arrived at this complexity, don’t fret. You’ll understand it eventually when you observe some more algorithms and develop a better understanding of complexity of algorithms.

All questions are welcome.

 

Sources to read from :

About the Sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://www.youtube.com/watch?v=9m2cdWorIq8

Complexity of this algorithm :

http://stackoverflow.com/questions/2582732/time-complexity-of-sieve-of-eratosthenes-algorithm

Online question:

Implement this algorithm first and see if it is generating prime numbers. And when you get familiar with the concept try to solve this question:

‘Count k primes’ on Codechef: 

http://www.codechef.com/problems/KPRIME

This question requires some modification to the actual Sieve algorithm. I’ll leave it to you to figure it out. If you face any problem, you may leave a  comment here.

Algorithm Complexity

In this post I am going to discuss what ‘complexity’ of an algorithm is and a method by which it is determined. I am not going to bore you guys by posting too much about theoretical concepts instead of actual algorithms. From the next post onward I am going to talk only about new algorithms. But it is important that you understand this concept.

Algorithm complexity tells us about how fast or slow an algorithm performs. We use the Big O notation to classify algorithms on the basis of how they respond to input of different sizes. I am going to describe it briefly. The Big O notation basically tells us “what is the execution time of the algorithm directly proportional to”.  If I say that the complexity of an algorithm is O(n^2), it means that the execution time of that algorithm is proportional to the square of the input size. Consider the following code snippet:

for(i=0;i<n;i++)
{
  for(j=0;j<n;j++)
  {
    //some code here
  }
}

The code inside the two loops will execute n^2 times. Therefore, The complexity of the above code snippet is O(n^2), because the execution time is directly proportional to the square of ‘n’.

Another example, complexity of the following code is O(n^3):

for(i=0;i<n;i++)
{
  for(j=0;j<n;j++)
  {
     for(k=0;k<n;k++)
     {
       //some code here
     }
  }
}

Similarly, the following algorithm for printing all elements of an array of size ‘n’ is an O(n) algorithm. In other words, it has linear complexity.

for(i=0;i<n;i++)
{
   printf("%d ",array[i]);
}

If I have to write a program for adding two numbers, I’ll write it as follows:

scanf("%d %d",&number1,&number2);
int sum=number1+number2;
printf("%d",sum);

The execution time of this algorithm is not dependent on the input ( number1 and number2). In this case, we say that the complexity of this code is O(1) i.e. constant complexity.

One more example,

scanf("%d",&n);
for(i=1;i<n;i*=2)
{
  //some code here
}

The complexity of the above algorithm is O(logn) as the code inside the loop executes ([log(n)]  + 1) times. ( [num] means that num is rounded up to the closest integer). The base for log is 2.

E.g.,

for n=8, the values of i for different iterations are i =  1, 2, 4, 8. Therefore, 4 iterations.

For n=31, i = 1, 2, 4, 8, 16, 32. Therefore, 6 iterations.

For n=33, i = 1, 2, 4, 8, 16, 32, 64. Therefore, 7 iterations.

So, the number of times the for loop iterates is directly proportional to log(n).

If I insert a code with O(logn) complexity inside a code with O(n) complexity, I’ll get code with complexity O(n*logn). For example,

scanf("%d",&n);
for(j=0;j<n;j++)
{
  for(i=1;i<n;i*=2)
  {
    //some code here
  }
}

The execution time of the above code is proportional to n*log(n), therefore O(n*logn)

O(1) algorithms are the best (obviously) but a constant time solution is not possible for most problems. Algorithms of higher order (n^3, n^4,…) are not preferred. They are the main culprits for TLE (Time Limit Exceeded) verdict.

Common algorithm complexities, from better to worse are

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O((n^2)*logn) < O(n^3) < …

Counting sort, that we previously discussed, has a complexity O(n). In counting sort, an array of size ‘n’ is traversed 3 times. Therefore, the execution time is directly proportional to n.

Other basic sorting algorithms like Selection sort, Bubble sort , Quick sort, etc have complexity O(n^2). Efficient sorting algorithms like Merge sort and Heap sort, have complexity O(nlogn), and therefore are preferred over the O(n^2) sorting algorithms.

The Big O notation is  widely used to compare algorithms. While introducing new algorithms I too will  mention their complexity in this manner.

I came across a page that contains some interesting information.

http://bigocheatsheet.com/

“Why am I getting Time Limit Exceeded?”

“I have implemented everything perfectly. Then why am I getting TLE?” is the question that comes to most programmers who are new to competitive programming. Let me tell you guys once and for all that declaring variables inside loops or writing a lengthy code has nothing to do with it. Variable declaration takes negligible time and the number of lines in the code does not affect the execution time of a program. If you are getting TLE, it is because the logic that you have devised to solve the problem is taking up a lot of time when run on large inputs. Lets take a simple example.

Suppose that we have to write a program to find the sum of all natural numbers from a till b. ( a and b are natural numbers too )

One possible approach (in C/C++) to this simple problem is

int i,sum=0;
for(i=a;i<=b;i++)
   sum+=i;

Now, if examined in terms of correctness, this code has nothing wrong with it. It finds the correct answer. But the code is not efficient with respect to time. If the difference between ‘a’ and ‘b’ is very large (say, a=1 and b=10^15), this code would take forever to run because the for loop will have to iterate from 1 till 10^15.

There’s another way to find the solution. We know that the sum of the first n natural numbers is ( n * (n+1) ) /2. By using this formula we may write the following code:

int high= (b * ( b + 1 )) /2;
int low= ((a-1) * a) /2;
int sum=high-low;

The variable ‘high’ contains the sum of first b natural numbers. And the variable ‘low’ contains the sum of first (a-1) natural numbers. So, obviously the sum of natural numbers from a to b will be (high – low).

The second approach will always take constant time to run. The execution time will be the same no matter how far apart a and b are. And it gives the same answer as the first method.

Now you see, this is the reason the first solution was not correct even though it was giving the correct output. Remember that if you are getting TLE, it may be because of the following reasons:

1. The logic of your program is not fast enough (as demonstrated above).

2. Your program is going into an infinite loop somewhere.

3. Rarely, VERY rarely because you are not using an efficient way to take input.

The problem setters usually set the time limit such that a participant never gets a TLE due to the 3rd reason. A note for C++ users: if a problem is such that large amount of numbers have to taken as input, it is better to use scanf() instead of the cin stream. The cin stream is slower than scanf().

(See the documentation for your language to find the best way to take input.)

When comparing two algorithms, we use a method known as the ‘Big O Notation’. In a nutshell, the Big O notation tells us what the execution time of a program  is directly proportional to.

This notation is used very frequently to comment on the efficiency of the algorithms and its very important that you get familiar to it. I’ll write about it in my next post (which will be very soon!).

Algorithm #1!

The first class of algorithms that I am going to discuss are sorting and searching algorithms. They are the most basic type of algorithms. Many times in a programming problem ( real world or in competitions), we need to sort a list of numbers or strings in ascending or descending order. The most basic sorting algorithms are Bubble Sort, Selection Sort, Insertion Sort and Quick Sort. But, none of these are good enough. As the length of the array to sort increases, these algorithms start taking too much time to sort. Merge Sort and Heap sort, on the other hand, respond well even on large inputs.

Implementation of good sorting algorithms is already available in the libraries of C++, Java and Python, so one doesn’t need to write a sort function from scratch in a programming competition.

But still I’ll discuss about one sorting technique that demonstrates a little trick that will help you in understanding other algorithms.
The algorithm is the ‘Counting Sort‘. It is a very simple way to sort numbers. The reason I am discussing it is that it demonstrates how the array indices can be cleverly used to simplify many tasks.

Sources to read from…

Counting sort: 
http://www.cs.miami.edu/~burt/learning/Csc517.091/workbook/countingsort.html

http://www.geeksforgeeks.org/counting-sort/

Related problems:

Codechef problem named ‘Turbo Sort’: http://www.codechef.com/problems/TSORT

NOTE:
Even though inbuilt sorting functions are available in C++, Java and Python, still I would suggest you to understand how the different sorting algorithms work as it will help you to develop your understanding. Also,NEVER use code templates from websites blindly. Always understand how they work first.
How to use sorting function in C++, Java and Python:

For C++ users, 
add the following line in the beginning of the program.
‪#‎include‬<algorithm> // ‘algorithm’ is a header file that contains implementation of some commonly used algorithms

and then you can use the following statement to sort an array (named ‘arr’ )

sort(arr,arr+n); // where n is the number of elements in the array

For Python users:
Just a make a list,

arr=[6,53,2,7,3]

and use

arr.sort()

For Java users:
Make an array and use
Arrays.sort(arr);
and the array arr will be sorted

If you have any problem in understanding the algorithm then you may leave a comment  the comments section below and I’ll try to answer it as soon as I can.

What’s this blog all about?

Greetings all!

My name is Abhinav Sharma. I live in Surat, India.

I remember the days when I started solving programming questions on online judges. There wasn’t so much solving  as there was getting frustrated  over Time Limit Exceeded, Run Time error and Wrong Answer verdicts. Over time I gradually understood how my solution should look like before I submitted it; It should strictly adhere to the input and output format specified by the problem statement, it shouldn’t include non standard header files, it should contains a ‘ return 0; ‘ statement at the end,… .( The last one really got me worked up!).

This blog is dedicated to the programmers who are in this beginning phase and for anyone who wants to learn new algorithms that are useful in programming competitions.

Solving some programming problems requires the use of some efficient algorithm or special data structure. If you try to solve them without using these special techniques, you might get the dreaded ‘Time Limit Exceeded’ (TLE) verdict. Or you might not be able to solve them at all.

There are some algorithms that are very frequently used in programming competitions. Approximately every week  I will introduce one such algorithm on this blog, along with an online source where you can read about it. I’ll also post a problem statement related to that algorithm so that you guys can implement it on an actual problem ( or I may give a link to a related problem on an online judge).
If you face any problem in understanding the concept or in getting your solution accepted on an online judge, you may post your questions here. Your questions will be answered!

Cheers!