fastest i/o methods

Almost all the problems involve some kind of input and output processing. Unless your code is of O(n^2) or above, more than 70% of the running time goes for IO processing. So it is important to perfrom these operation efficiently in order to make the entire program efficient. here are some tips regarding input and output...
1. More overloaded a function the more time it takes
It means if you use overloaded function or stream opreator then it will take more time than an ordinary function, in short cin is slower than scanf() which in turn is slower than gets()
2. Input and output usually involves peripheral hardwares which make them slow.
If you are taking input from file then its ok otherwise you have to use keyboard which can slow down the speed not because you cant type fast(even thats also true) but because it has to check the buffer of keyboard and same in case output.
3. String and character arrays are easy to handle in case of input and output because the compiler just has to use them exactly as they are. Int, Long and Floats have to be transformed before printing or before storing.

Here is a hierarchy of the methods to take the input:
> fread() or read() system call
> gets() or getchar()
> scanf()
> cin>>
these are the methods in the increasing order of processing time with fread() is the fastest and cin being the slowest.

similarly you can figure out for the output:
> fwrite() or write()
> puts()
> printf()
> cout<<

now choose any one option according to the situation. Choose from the bottom if you want good looking but relatively slower code and choose from the top if you want complex but faster code... as always choice is yours :)
happy coding

get the input from a file

there are lots of problems on SPOJ that require input must be taken from an input file. Those types of problems require that you get input till the end of input file and you cant use simple while or for loop to get input say 'n' no of times or until a particular number is entered. i tried so many things like finding EOF or checking for (!scanf()) but none of them worked and finally i had to keep my working codes for those problems aside since if i cant take inputs as described i will either get Time limit exceeded or runtime error.
after a long searching of such code i finally got perhaps the easiest way to get around that problem of getting input. it is damn simple. all you need to do is to make an object(e.g. string s;) of string type in CPP of course and then simply initialize a loop as
string s;
while(getline(cin,s))
{
use s as you wish
print result
}
that was a normal code but if you dont know this in prior then you cant do anything since it is not very common code. few examples of those problems which require this type of implementation are encondin, javac, bishops

it was sensational :)

when on sep 03 i got my code for generation of prime number accepted on SPOJ i felt like i have achieved something very special. its not that very few people have solved it or it was a great problem but its in that sense that i made more than 20 unsuccessful attempts before finally cracked it. i was simply jumped from my chair when i saw the time taken by my code it was showing 0.21 secs when the time limit is 6 secs. indeed it was great feeling because i could not able to do it even for 6 secs few days before now fucked it up for 0.21 secs :)
there was nothing special in that code i just implemented Sieve's algorithm for generation of prime number but improved it a little bit.
what i done is not at all significant but still i explain it here. here we go...
i created an array of 32000 and applied sieve on it to get a list of all the primes from 1 to 32000 now processed the input. if the larger number is less than 32000 then simply printout what we already have in our pocket.
else created another array of size that is the difference between the larger(h) and smaller(l) input. now besides small manipulations, i found the square root of larger number then from 2 to that square root took each number(lets say 'd') and for each such number i took another number(lets say 'n') in the given range(l to h) but instead of dividing it for modulus(as per Sieves algorithm) i used a trick here.
i found a number that is nearest to the first number of the input(smallest int greater than l) which is a multiple of 'd' and then simply added d till it was less than h to find all its multiple and then simply applied remaining sieves algorithm.

// AC
#include<iostream>

#include<math.h>
#include<stdio.h>
using namespace std;
int main()
{
    bool a[32010]={0},*p;
    int i,j,s,k,t=0,rem,rem1;
    cin>>t;    
    long long n1[t],n2[t],m;
    long d;
    //int z=0;

    double x;
    for(i=2;i<32002;i++)
    {
          if(a[i]==0)
          {
               for(j=i+i;j<32002;j+=i)
               a[j]=1;
          }
    }
    for(i=0;i<t;i++)
    {
        cin>>n1[i]>>n2[i];
        if(n2[i]<=32000)
        {
            for(j=n1[i];j<=n2[i];j++)
            if(a[j]==0 && j>1)
            cout<<j<</*"   "<<++z<<*/endl;
            goto done;
        }
        if(n1[i]==1)
        n1[i]=2;
        n2[i]+=2;
        d=sqrt(double(n2[i]))+1;
        p=new bool[n2[i]-n1[i]+1];
        for(j=0;j<n2[i]-n1[i]+1;j++)
        p[j]=0;
        for(j=2;j<d;j++)
        {
         if(a[j]==0)
            {
                rem=n1[i]%j;
                if(rem==0)
                rem=j;
                k=n1[i]+j-rem;
                while(k<=n2[i])
                {
                    p[k-n1[i]]=1;
                    k+=j;
                }
                if(j==n1[i]+j-rem)
                p[j-n1[i]]=0;
            }
        }
        s=n2[i]-n1[i];//getchar();

        for(j=0;j<s;j++)
        {
            if(p[j]==0 && j+n1[i]<n2[i]-1)
            cout<<j+n1[i]/*<<"   "<<++z*/<<endl;
        }
      done: cout<<"\n";
    }
    return 0;
}                 

besides this i have come across few other cool programming problems and concepts but thats not for now....

tips 4 neophytes like me

programming is the only thing that i do in my college with (extreme) regularity. i think i need not mention that i m a registered user at SPOJ. i've solved a handful of problems there. here is my profile at spoj. it was not so long when i was happy with my Turbo-C compiler... i was asked by my senior to switch to GCC and i m very grateful to him [:)].
things you need to keep in mind while solving problems.

1. they check your efficiency not your language knowlegde.
2. they run your programs at extreme cases.
   
3. finally you need a gud algorithm and proper implimentation.

thats it and you will make it Ac ( @ spoj, Ac means your solution to a particular problem has got accepted by online judges).
mostly problems are based on number theory, string matching, sorting, graph and others but the input range and time limit makes it harder to solve.
if you want to start with some easier ones then go to my profile. i usually solve easier first [:)].
thats enuf for today next time i will tell you explanation to few problems so you can solve them quite easily.

Introduction

hi all. this is me out here with a brand new blog. before i come to my business, let me introduce myself. This is Shubham Dave pursuing my btech with CS stream n currently studying in final year. my subjects of interest are data structures and algorithms and i just love writing programs in c/c++, java and python...
ps: as midsem tests are scheduled from tomoro onwards i cant continue right now [;)]