Enormous Input Test

March 12, 2009 at 11:59 am 3 comments

This is quite strange – http://www.codechef.com/problems/INTEST/

Basically it is a division problem, but I do not understand what all optimizations can be applied to speed it up. I could think of only 1 simple optimization which is to check if num1 < num2 and in that case num2 cannot completely divide num1 (note that we are considering only positive numbers, so 0 is not involved). The best solution takes 0.86 seconds, while my solution is taking 5.54 seconds and both are implemented in C++.

Need to think more into it!

Advertisements

Entry filed under: Uncategorized.

Sums in a triangle Prime Generator

3 Comments Add your own

  • 1. narinderberi  |  March 12, 2009 at 12:01 pm

    Here is my code:

    #include
    #include

    void enormousInputTest()
    {
    int n, k;
    scanf(“%d %d”, &n, &k);

    register int num;
    register int count = 0;
    for(register int iNum = 0; iNum = k)//note that we are considering only positive numbers, so 0 is not involved.
    if(!(num % k))
    count++;
    }

    printf(“%d”, count);
    }

    int main()
    {
    enormousInputTest();
    return 0;
    }

  • 2. Lalit  |  March 16, 2009 at 6:07 am

    if the number is odd, we can reject even numbers

  • 3. Lalit  |  March 16, 2009 at 6:11 am

    Sorry for the above comment, I meant other way round, if the divisor is an even number, we can reject the odd numbers from the provided list.

    I think to further improve the logic, we should think of the list as a whole and not consider indivudally, for example sort the list, keep taking out the differences, until the difference is greater then the divisor, now there can be only one dividend which the temp list so formed. This is just a thought will post a proper one, if it forms correctly

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

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: