A warrior never surrenders, A warrior never quits..


Sunday, September 14, 2008

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

Friday, September 12, 2008

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....