Page 1 of 2 12 LastLast
Results 1 to 10 of 20

Thread: Bombing Problem

  1. #1
    Join Date
    Aug 2010
    Location
    INDIA
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Bombing Problem

    i found this problem in codechef NOV10 competition.
    http://www.codechef.com/NOV10/problems/BOMBING/


    here is my program:

    PHP Code:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>

    // these two variables will store the initial and final house of the particular protection
    intinitial;
    intfin;
    static 
    int count=0;  // will count the total number of protections

     // in case protection will applied this function will update initial and final variables
    void pro(int u,int v
    {
      
    int i;  // loop variable
      
    *(initial+count)=u;
      *(
    fin+count)=v;
      
    count++;
    }

    // this function will move the protection.
    void mov(int u,int v)
    {
      
    u--;
      *(
    initial+u)+=v;
      *(
    fin+u)+=v;
    }


    // this function will return the number of protections protecting the house x
    int bomb(int x)
    {
      
    int p=0,i;
      for(
    i=0;i<count;i++)
        {
          if(*(
    initial+i)<=&& *(fin+i)>=x)
        
    p++;
        }
      return 
    p;
    }


    int main(void)
    {
      
    long n;    // number of houses
      
    long m;   // number of lines to be entered, may be protection, move or bombing
      
    charstr=NULL;  // take the input
      
    chartemp;  // processing on input
      
    size_t sz=25;  // used in getline
      
    int u,v;  // variables used to extract info from text and pass into various functions
      
    int i;  // loop variable

      
    getline(&str,&sz,stdin);

    // extracting first two integer i.e. number of houses and input lines
      
    temp=strtok(str," ");
      
    n=atoi(temp);
      
    temp=strtok(NULL,"\n");
      
    m=atoi(temp);

    // allocating memory for number of input lines
      
    initial=(int*)malloc((m)*sizeof(int));
      
    fin=(int*)malloc((m)*sizeof(int));

    // processing
      
    while(m--)
        {
          
    getline(&str,&sz,stdin);
          
    temp=strtok(str," ");

    // if protection is applied in input line
          
    if(temp[0]=='P')
        {
          
    u=atoi(strtok(NULL," "));
          
    v=atoi(strtok(NULL,"\n"));
          
    pro(u,v);
        }
          else if(
    temp[0]=='B')  // if bombing is done in input line
        
    {
          
    u=atoi(strtok(NULL,"\n"));
          
    printf("%d\n",bomb(u));
        }
          else if(
    temp[0]=='M')  // if move is done in input line
        
    {
          
    u=atoi(strtok(NULL," "));
          
    temp=strtok(NULL,"\n");
          if(
    temp[0]=='-')
            {
              
    i=1;
              
    v=0;
              while(
    temp[i])
            
    v=v*10 + ((int)temp[i++] - 48);
              
    v*=-1;
            }

          else
            
    v=atoi(temp);
          
    mov(u,v);
        }
        }
      return 
    0;

    i posted all the comments that may be helpful in understanding of the program.
    my problem is i need to speed up this program without using too much memory.
    can anyone please suggest me a way. please.
    Last edited by c2tarun; November 6th, 2010 at 04:30 AM.

  2. #2
    Join Date
    Jun 2007
    Location
    Maryland, US
    Beans
    6,273
    Distro
    Kubuntu

    Re: Bombing Problem

    Quote Originally Posted by c2tarun View Post
    my problem is i need to speed up this program without using too much memory.
    can anyone please suggest me a way. please.
    Remove the getline() calls, and instead receive command line arguments.


    P.S. I would not be too concerned with "speed" if your program is going to be dependent on getting input from a user.

  3. #3
    Join Date
    Aug 2010
    Location
    INDIA
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Bombing Problem

    Quote Originally Posted by dwhitney67 View Post
    Remove the getline() calls, and instead receive command line arguments.


    P.S. I would not be too concerned with "speed" if your program is going to be dependent on getting input from a user.

    actually in a way i m getting input from outside but in a very speedy manner.
    there are huge test cases saved in text files.
    at execution time i use

    $ ./bombing < testcase1


    this reduces the time for input. the problem is with program execution. the program is taking too long to print the output. i tried replacing all else if with switch case, but nothing happened.

  4. #4
    Join Date
    May 2008
    Location
    UK
    Beans
    1,450
    Distro
    Ubuntu 8.04 Hardy Heron

    Re: Bombing Problem

    Quote Originally Posted by c2tarun View Post
    actually in a way i m getting input from outside but in a very speedy manner.
    there are huge test cases saved in text files.
    at execution time i use

    $ ./bombing < testcase1


    this reduces the time for input. the problem is with program execution. the program is taking too long to print the output. i tried replacing all else if with switch case, but nothing happened.
    Why do you think the switch will be any quicker - it is likely (with a good compiler like gcc) to result in exactly the same machine code to be executed - comparisons and branches.
    Tony - Happy to try to help.
    Unless otherwise stated - all code posted by me is untested. Remember to Mark the Thread as Solved.
    Ubuntu user number # 24044 Projects : TimeWarp - on the fly Backups

  5. #5
    Join Date
    Aug 2010
    Location
    INDIA
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Bombing Problem

    Quote Originally Posted by Tony Flury View Post
    Why do you think the switch will be any quicker - it is likely (with a good compiler like gcc) to result in exactly the same machine code to be executed - comparisons and branches.

    sorry i just shot an arrow in the dark.
    i was not knowing that switch will do no good.
    but good thing is now i know that switch is as good as else if.
    but my problem still persists.

  6. #6
    Join Date
    Jun 2007
    Location
    Maryland, US
    Beans
    6,273
    Distro
    Kubuntu

    Re: Bombing Problem

    It would be helpful to see what input you are providing the application. It also would be nice to see a version of your application where you actually free each of the strings that is allocated and returned by getline().

    From the man-page:
    Code:
    DESCRIPTION
           getline()  reads  an entire line from stream, storing the address of the buffer containing
           the text into *lineptr.  The buffer is null-terminated and includes the newline character,
           if one was found.
    
           If  *lineptr  is  NULL,  then getline() will allocate a buffer for storing the line, which
           should be freed by the user program.  (The value in *n is ignored.)

  7. #7
    Join Date
    Aug 2010
    Location
    INDIA
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Bombing Problem

    Quote Originally Posted by dwhitney67 View Post
    It would be helpful to see what input you are providing the application. It also would be nice to see a version of your application where you actually free each of the strings that is allocated and returned by getline().

    From the man-page:
    Code:
    DESCRIPTION
           getline()  reads  an entire line from stream, storing the address of the buffer containing
           the text into *lineptr.  The buffer is null-terminated and includes the newline character,
           if one was found.
    
           If  *lineptr  is  NULL,  then getline() will allocate a buffer for storing the line, which
           should be freed by the user program.  (The value in *n is ignored.)

    actually the bigger test cases are with the website owners.
    i have a pretty small one.
    Input:
    7 5
    P 1 4
    P 3 5
    B 3
    M 2 1
    B 3

    Output:
    2


    when i m posting the program there they check it with their own test case, they are giving error time limit exceeded...
    1

  8. #8
    Join Date
    May 2006
    Beans
    1,787

    Re: Bombing Problem

    Quote Originally Posted by c2tarun View Post
    actually the bigger test cases are with the website owners.
    i have a pretty small one.
    Input:
    7 5
    P 1 4
    P 3 5
    B 3
    M 2 1
    B 3

    Output:
    2


    when i m posting the program there they check it with their own test case, they are giving error time limit exceeded...
    1
    What time limit is that? Can you get them to give you their test cases and check how long it takes on your computer?

    I would also ask for the output generated before the time limit was exceeded.

  9. #9
    Join Date
    Aug 2010
    Location
    INDIA
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Bombing Problem

    Quote Originally Posted by Arndt View Post
    What time limit is that? Can you get them to give you their test cases and check how long it takes on your computer?

    I would also ask for the output generated before the time limit was exceeded.

    friends, the website dont tell us anything, they just give us the question, the sample output and on submitting if program gives the desired output on there test case in the given time, they give that program is correct. but in my case they r just saying that time limit exceeded.

  10. #10
    Join Date
    May 2006
    Beans
    1,787

    Re: Bombing Problem

    Quote Originally Posted by c2tarun View Post
    friends, the website dont tell us anything, they just give us the question, the sample output and on submitting if program gives the desired output on there test case in the given time, they give that program is correct. but in my case they r just saying that time limit exceeded.
    Do you know for sure that "time limit exceeded" doesn't also include the case where the test case fails?

    Send in something trivial but wrong, that can't possibly cause time limit exceeded, and see what they report.

    I haven't looked much at your code, but may there be cases where it enters an infinite loop?

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •