Some medium level problems on SPOJ

Here are some of the medium level problems on SPOJ:

1. Prime Generater – This question can be solved by applying sieve’s algorithm. What we do is make an array of prime numbers in the range of 1 to 32000 ( square root of 1000000000 ) .. now we have our initial setup ready .. for generating primes i used sieve’s algorithm which states that you make an boolean array of 32000 values and initialize it as true that means declare all of them as prime .. now start from 2 and if the current number is prime .. make all itz multiple in the apropriate range as composite ( i.e. set their index in the array as false .. ) .. this is the fastest method for generating prime numbers .. now we start taking the input from the user .. lets say he gives the numbers m and n as input ( m> n) now we apply sieve again .. first make an array of booleans of size m-n ….. now for all the prime numbers from 2 to the prime number next to the square root of m we make their multiples in the range n to m as composite ( i.e. set their array as false ) .. now after this procedure is over .. just a linear traversal in the second array .. and print whatever is prime .. ( i.e. flag is true .. ) .


2. Small Factorial .. – This is fairly simple problem .. you just have to make a programme to multiply arbitrary large numbers . ( stored as strings .. ) and then run a loop from 1 to n to calculate the answer .. thats it ..


3. Bytlandian cryptographer .. act 2nd .. – This is again a very easy problem .. add 1 to a number isnt it easy !!!! .. but the problem is you have to write the code in Brainf*** yeah that language does not have even a multiplication and addition operators .. just 8 instructions and the language is over .. !!!  .. but you can try the official documention of brainf*** language .. go through may be first page and thats it for this problem ....so easy points once you go through this page ..


4.Bytelandian gold coins -This problem can be solved by recursion using the relation:
                                  f(n)=max(n,f(n/2)+f(n/3)+f(n/4))
but it times out.The solution to that is memoization.It is a technique in which we store the already calculated results in a sort of cache and use it whenever needed instead of calculating it again.
here's a sample  for the same in C++:


map reference;


long long f(n)
{
   if(n==0)return 0;
   if(reference[n]==0)
   {
         reference[n]=max(n,f(n/2)+f(n/3)+f(n/4));
   }
   return reference[n];
}


5.POKER:Though its a very easy problem if you know the rules of POKER but i put it in medium because i think its very easy to miss any condition in this and  get it wrong.


Best Of Luck