SPOJ Methods to solve for beginners – part 1

From last 20-25 days I am solving problems on Sphere Online Judge . This site contains the best problemset I’ve seen (even better than acm) It contains a variety of problems and I thought to write my algorithms here so that some beginners like me can get help and improve their programming skills. So here is the first part containing some easy problems –

Disclaimer : I do not claim that my solutions are best in any means, as far as methods are concerned I always prefer simplicity rather then speed, and my methods are just a starting point for beginners. If you have better solutions please be generous to put them as comments along with the problem name.

so here we go –

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 .. ) . here we consider primes only till the square root of bigger number beacause of the fact that if any number is divisible by a number .. then either the diviser of x/y( x is the number and y is the diviser ) will b in the range of square root of x .. so it speeds up the simulation a lot .. 🙂

2. Transform the expression – This problem is very easy except you got check all the minor errors .. you can do it easily by a use of stack .. ( that is the method i was taught in my data structure course .. :p .. ) what you do is make a stack of operations .. ( char ) and a stack of operators ( char again .. ) .. now whenever an operator is pushed on to the stack if the the operator at the top of the stack has a priority higher than the operator to be pushed ( for example ‘+’ is to be pushed and ‘*’ is at the top of the stack .. ) we first pop out the higher

priority operator .. apply the operation on the char operands .. print the result and then push the current operator .. I am just telling the basic thought .. now you have to put a lot of conditions to get it working .. and ofcourse the special case for brackets .. because they are not the operators but have got the highest priority .. ) .. this algorithm is pretty much O(n) so will work fine ..

3. The next palindrome .. :- this method I used to solve the problem is pretty much a non standard method .. I mean just specific to the problem .. there is no specific theorum to proove that the method is correct or not .. anyways .. what we do is .. we have a boolean variable isincreased ( which at any time specifies that after all the manipulations we have done till then is the resultant number greater than the input number or not .. ) now make it initially as false then first we travel starting from the starting digit and the ending digit .. ( make one pointer as low and other one as high .. based on your choice .. ) now we keep moving both the pointers towards the center of the number untill high<low comes .. once it comes we make high equal to low and make the isincreased flag to true .. if it does not than we will stop our traversal once we reach the center .. now we will move outside i mean towards the corners of the number .. we again have a high .. ( pointer on the right side .. ) .. and low so we can have 3 conditions at a time ..

1.high < low .. => we make high equal to low and forget about it ..

2. high=low => we do nothing and keep moving

3. low<=high => we increase digit low by 1 and and then make high equal to low ( that means if we have low = 1 and high = 8 we make low as 2 and high as 2 ( ofcourse we have to make them equal at any stage because the resultant number is a palindrome .. ) . and then make all of the digits between low and high as 0 ( becauze since low is increased so even we make all of them as 0 the isincreased flag will still be fine .. )

now the special case is if we have the digits as 9 and their is no chance of increasing the digits .. frm the beginning ( the number is all 9 ) the isincreased flag continues to be false and finally if that is the case when we finish it up .. we simply print 1 than some 0’s then again 1 .. ) ..

otherwise after we reach the ends we are done and we simply print the string .. 🙂

4. Simple Arithmatics .. – this is question is as simple as it looks except the output formatting .. you will get it right but the only statement to be given attention is that horizontal line of hyphens is only as long so as to cover the line exactly above and below it .. and not all the output .. so if u take care about this you may get it right .. that was the mistake i did when i solved .. :p ..

5. Small Factorial .. – This is one of the easiest problems at spoj .. 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 .. at least that is what i did .. ( thr may b better methods ofcourse .. )

6. 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 .. ( I used a trick to get around the solution .. which makes it almost 16 character programme .. !! .. ) ..so easy points once you go through this page ..