## Enormous Input Test

*March 12, 2009 at 11:59 am* *narinderberi* *
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.

1.narinderberi | March 12, 2009 at 12:01 pmHere 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 amif the number is odd, we can reject even numbers

3.Lalit | March 16, 2009 at 6:11 amSorry 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