Just another tech blog.

A blog abt GNU/Linux, programming, hacking, and my life.

SPOJ Methods to solve for beginners – part 1

Posted by ajay on June 4, 2006

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

About these ads

26 Responses to “SPOJ Methods to solve for beginners – part 1”

  1. Sharat said

    gud work yaar…btw hav u uploaded next palindrome prob..

  2. ajay said

    yeah i did ..

  3. nilesh said

    the next palindrome:
    can you explain a bit more..
    as far as I understand your algo will give the answer “2002″ for input “1008″.. but the answer should be “1111″.. correct me if I am wrong..

  4. ajay said

    @Nilesh ..

    my algorithm will still give the correct output 1111 ..
    when you give 1008 … initially it will get to the center because high less then low will not occur .. and after then as
    I have written that ’0′ and ’0′ are equal .. so we do increase them by 1 because isincreased flag is still false and noww I make it true .. now after this step .. the low pointer will be at 1 and high pointer will be at 8 .. since isincreased is true .. so we make 8 equal to 1 and do nothing about it .. so after this step the number will become 1111 .. and hence the answer will come .. if the algorithm is still not completely clear to you .. I may as well mail you the source code so that you can see it for yourself .

  5. sunandan madan said

    HI I AM sunandan from karnal haryana.ihave got admission in lnmiit and daiict(gandhinagar).which is better in terms of placement,facilities…. and everything else.please do reply.

  6. anu said

    How to handle Big Numbers in SPOJ????

    • I code in C : you can – use a linked list.. or a char[],

      multiplication of big numbers is given in “balaguruswaami” i think.. have a look if you have trouble..

  7. vijay03 said

    Write your own big number class :) Or use Java :)

  8. AMBREEN said

    I HAVE A PROGRAM WHERE I HAVE TO SOLVE THE PROBLEM IN AN ARRAY METHOD. CAN SOMEBODY HELP ME
    PROGRAM TO SOLVE IN ARRAY METHOD:

    Bobo visits the local high school on a Saturday and finds that all of the school’s 1,000 lockers are neatly closed. So, he starts at one end of the school and opens them all.

    Then he goes back to the start and closes EVERY OTHER locker (lockers 2, 4, 6, and so on). Then he goes back to the start and visits EVERY THIRD locker: if it is open, he closes it; if it is closed, he opens it.

    He again returns to the start and this time visits EVERY FOURTH locker. If it is open, he closes it; if it is closed, he opens it. He continues to return to start, and then visits EVERY FIFTH, then EVERY SIXTH, and so on until he has done this process 1,000 times.

    Then he gets bored and goes home.

    TO SOLVE: At the end, how many of the school’s 1,000 lockers are left open, and which ones are they? (As an aside, do you notice a special characteristic of the numbers of the lockers that were left open? Also, do you notice a characteristic between the number of lockers left open and one of the values in the set of lockers left open?).
    PLEASEEEE HELP ME TO SOLVE.

  9. Ajay Anandan said

    hey… the answer is all the numbers which are perfect squares…

  10. bittu said

    prime generator
    what’s the purpose of creating the array of primes in the range 1-32000..??

  11. Kshitij said

    Hi Ajay.

    I’ve been stuck on PRIME1 for some time now. I’ve tested my solution against many test cases, but it still gets a “Wrong Answer” from the judge. Could you mail me your code?

    
    #include 
    #include 
    #include 
    
    #define SIZE 31700
    
    char firsts[SIZE+1];
    char oths[100001];
    
    int main()
    {
        int i, j, ntests;
        long high, low, first, srt;
    
        memset(firsts, 0, SIZE);
    
        firsts[0] = firsts[1] = 1;
    
        for(i = 2; i <= SIZE; i++)
        {
            if(firsts[i] == 0)
                for(j = i + i; j <= SIZE; j += i)
                    firsts[j] = 1;
        }
    
        scanf("%d", &ntests);
    
        while(ntests--)
        {
            scanf("%ld %ld", &low, &high);
    
            if(high < SIZE-1)
            {
                for(i = low; i < high+1; i++)
                    if(firsts[i] == 0)
                        printf("%d\n", i);
                printf("\n");
                continue;
            }
    
            memset(oths, 0, high-low);
    
            srt = sqrt(high) + 1;
    
            for(i = 2; i <= srt; i++)
            {
                if(firsts[i] == 1)
                    continue;
                first = ((low/i) * i) - low;
                if(first < 0)
                    first += i;
                for(j = first; j < high-low+1; j+=i)
                    oths[j] = 1;
            }
    
            for(i = 0; i < high-low+1; i++)
                if(oths[i] == 0)
                    printf("%ld\n", i+low);
    
            printf("\n");
        }
    
        return 0;
    }
    

    Thanks :)

  12. das said

    bye

  13. Hi Ajay,

    Nice to know about the best method to find out prime. Could you please send me the Code. I would like to check it out what the best can be.

    Thanks and I really appericiate your interesting post.

    Bye

  14. Magesh said

    Hi,
    this code works in my system but spoj says its wrong..pls mail the corrected answer for me..
    problem code:LASTDIG
    #include
    #include
    int answ(unsigned long long int,int);
    int main()
    {
    int no,i,ans[30],a,c,a1;
    unsigned long long int b;
    scanf(“%d”,&no);
    for(i=0;i<no;i++)
    {
    scanf(“%d %llu”,&a,&b);
    if(a==0||a==10||a==20||a==5||a==15||a==1||a==11||a==6||a==16)
    {
    ans[i]=a%10;
    }
    else
    {
    a1=a%10;
    ans[i]=answ(b,a1);
    }
    }
    for(i=0;i<no;i++)
    printf(“\n%d”,ans[i]);
    return 0;
    }
    answ(unsigned long long int q,int no)
    {
    int d,e,c,an;
    if(no!=4||no!=9)
    {
    c=q%4;
    if(c==0)
    c=c+4;
    }
    else
    {
    c=q%2;
    if(c==0)
    return no;
    else
    return ((no*no)%10);
    }
    d=pow(no,c);
    e=pow(10,c);
    an= d%e;
    return (an%10);
    }

  15. mido22 said

    i solved prime or not but it tells me wrong answer and i solved it with variables long long int so what is wrong here

    #include
    #include
    #include
    #include
    using namespace std;
    int main()
    {
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
    //vector y;
    long long x;
    cin>>x;
    // y.push_back(x);
    if(x==2||x==3||x==5)
    {
    cout<<"YES"<<endl;
    continue;
    }
    else
    if(x<=1)
    {
    cout<<"NO"<<endl;
    }
    else
    if((x%2)==0||(x%3)==0||(x%5)==0)
    {
    cout<<"NO"<<endl;
    }
    else
    {
    cout<<"YES"<<endl;
    }
    }
    return 0;
    }

  16. ankit said

    i am stuck on the prime 1.
    i used the algo and got the correct answer but only till n-m is about 65000.anything more than that..
    i can’t even store it in a char array…
    what’s the solution to this please?
    i have the similar problem in a lot of problems

  17. Paradise said

    really helpful info …

  18. soundar said

    tell me how to manage the carry in
    Bytlandian cryptographer .. act 2nd problem….it’ll be really helpfull

  19. Was searching on a variety of instructions on this matter and i should admit your tactic could be the 1 that makes extra sense to me. thanks for sharing

  20. It is the digital spotlight forum…

    [...]SPOJ Methods to solve for beginners – part 1 « Just another tech blog.[...]…

  21. … [Trackback]…

    [...] Read More Infos here: ajayfromiiit.wordpress.com/2006/06/04/spoj-method-to-solve-for-beginners-part-1/ [...]…

  22. Ayone said

    7335. Spheres
    I get TLE on the second test. Does anyone know what is the solution of this problem? Please!

  23. yaswanth said

    hi, I am on a problem MINMOVE spoj.I hv checked all most all the test cases.bt still it gives a wrong answer.can any1 help me out?here is the link to my code.
    http://ideone.com/kMITa

  24. yaswanth said

    and the link to the problem
    http://www.spoj.pl/problems/MINMOVE/

  25. Pranjal Jain said

    This is a code to find the next palndrome..it is giving wrong answer on spoj.Please help me to find the bug in the code..Thanx

    #include
    #include
    #include

    int main()
    {
    char a[1000002];
    long int len,i,j,temp,temp1,allnine,carry,t,k,l;
    scanf(“%d”,&t);
    for(k=0;k1)&&a[0]==’0′)
    {
    i=0;
    l=0;
    while(i<len-1)
    {
    if(a[i]=='0')
    {
    l++;
    i++;
    }
    else
    break;
    }

    for(i=l;i<len;i++)
    {
    a[i-l]=a[i];
    }
    len=len-l;
    a[len]='';

    }

    if(len==allnine)
    {
    allnine=1;
    a[0]='1';
    for(i=1;i<=len;i++)
    a[i]='0';
    a[i]='';
    len++;
    }

    switch(len%2) //if a nuber is a palindrome add 1 to it
    {
    case 0:
    temp=0;
    for(j=0;j=0;j–)
    {
    if(a[j]==’9′)
    a[j]=’0′;
    else
    {
    a[j]++;
    carry=1;
    }
    if(carry==1)
    break;
    }

    }
    break;

    case 1:
    temp=0;
    for(j=1;j=0;j–)
    {
    if(a[j]==’9′)
    a[j]=’0′;
    else
    {
    a[j]++;
    carry=1;
    }
    if(carry==1)
    break;
    }

    }
    break;
    }

    switch(len%2) // creates the next palindrome of a given number
    {
    case 0:
    if(!(a[len/2-1]>a[len/2]))
    {
    temp=0;
    for(j=0;ja[len/2-j-1])
    temp=1;

    if(temp==1)
    break;

    }
    }
    if(temp==1)
    a[len/2-1]++;
    for(j=0;ja[len/2+1]))
    {
    temp=0;
    for(j=1;ja[len/2-j])
    temp=1;

    if(temp==1)
    break;
    }
    if(temp==1)
    {
    if(a[len/2]!=’9′)
    a[len/2]++;
    else
    {
    a[len/2-1]++;
    a[len/2]=’0′;
    }
    }

    }
    for(j=1;j<=len/2;j++)
    a[len/2+j]=a[len/2-j];
    break;

    }

    printf("%s\n",a);
    }
    getch();
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: