"Cool Guys" CodeChef challenge

I was trying to solve a question on CodeChef. My code works perfectly fine in my IDE (Visual Studio here) but when I submit my code at CodeChef, it says "Time Limit Exceeded".

What the code does:

• Input T number of test cases each with one input N
• Let A and B be two numbers chosen randomly from 1,2,3...N
• Output the probability that Greatest Common Divisor of A and B equals B for each test case.

int _tmain(int argc, _TCHAR* argv[])
{
int T;
cin>>T;
int tests[1000];
for(int k=0;k<T;k++) //  Take the test cases as input
cin>>tests[k];

for(int i=0;i<T;i++)   // the main loop that runs T times
{
int N=tests[i];

int result=2*N-1;   //  the numerator of the result

int square=N*N;   //  the denominator of the result

for(int j=2;j<=(N/2);j++)
{
result=result+(N/j)-1;
}

for(int w=2;w<=result;w++)  //  Loop to convert fraction into irreducible form
{
if(result%w==0 && square%w==0)
{
result=result/w;
square=square/w;
w--;
}
}

cout<<result<<"/"<<square<<endl;
}
return 0;
}


How can I optimize this code of mine so that it compiles within the specified time limit? Any optimization possible whatsoever?

• Both _tmain() and _TCHAR are Microsoft-specific and are non-portable. Just make them main() and char respectively.

• The name T is commonly used in template statements. Even with the given explanation, it may still confuse others, especially if you end up adding templates somewhere. You could just rename this to testCases or something similar.

• It's good to have more whitespace between operands for readability.

For instance, this:

for(int k=0;k<T;k++)


can look like this:

  for (int k = 0; k < T; k++)

• You have some not-so-useful comments:

//  Take the test cases as input


This is already obvious based on what it's doing.

// the main loop that runs T times


This is also already obvious, based on the loop statement.

int result=2*N-1;   //  the numerator of the result

int square=N*N;   //  the denominator of the result


Although not necessarily useless comments, they are an indication that those variables can be given more accurate names. It'll also help give more meaning to the very last cout statement that uses those variables.

Algorithm

It would be worth explaining a bit more what you have done. In any case, here are a few mathematical facts:

• For A, B positive integers, GCD(A, B) == B is equivalent to A is a multiple of B.

• For A, B in [1, N], we have N^2 couples (A, B)

• For B in [1, N], we have floor(N/B) elements A such that A is a multiple of B in [1, N]. In particular, if B is 1, we have N elements.

• To reduce fractions, you can use Euclid's algorithm.

The last fact is probably the one that can be useful to you.

Test and Code organisation

In any case, if you want to optimise your code, I suggest you write some test cases (with huge values so that you can see where the bottleneck actually is). In order to write these tests, you might find it more convenient to write small functions with a single responsability.

You might realise while doing so that you don't really need to store the inputs in an array only to go through the array afterward. You could probably write something like :

typedef frac // TODO
int get_gcd(int a, int b); // TODO
frac get_proba_as_irreducible(int N); // TODO
void print_proba(frac); // TODO

int _tmain(int argc, _TCHAR* argv[])
{
int T;
cin>>T;
for(int k=0;k<T;k++)
{
int N;
cin >> N;
print_proba(get_proba_as_irreducible(N));
}
return 0;
}