A- CodeChef: Practical coding for everyone
i guess this is the problem code,
while(h != n)
{
l=(h+1);
while(l != n)
{
if(goals[l] > goals[h] && (goals[l]-goals[h]) > diff)
{
diff=goals[l]-goals[h];
}
l++;
}
h++;
}
i tried using both for and while loop, but as obvious, it doesn’t change anything. Please suggest me how to shorten this code snippet or get rid of TLE anyhow.
Hi,
You are doing a brute force. Your code takes at least N(N-1)/2 steps. When N is as big as 100000 (105), this is at least 4999950000 operations to be done in 2 seconds.
Of course, using an O(N2) algorithm will time-out.
You need to have an algorithm, whose complexity is something like O(N).
Please read the editorial, for a quick explanation on this.
@tijoforyou : though i’ve been programming from school days, but i’m relatively new to making programs with time limit hence need no ask even small things.
i’ve used nested for/while loops making it of O(N2) complexity. Would it be better if instead i introduce 2 new arrays and store the max and min goal scored with their index, and accordingly compare and print the answer ? will this thing be cool ?
[you’ve answered many of my doubts, so thanks :)]
Yup. Calculating the values of one of the arrays (say, the min-array) will need only a single loop. Similarly, that for the other array (say, the max-array) will also need only a single loop. Since there are no nested loops, it takes only O(N) steps. Now the solution is maximum among difference between the corresponding entries of the two arrays. This will also be O(N). Hence, total complexity stays at O(N).
PS: All the above words taken from the editorial, just to re-assure you 
You can even find the links to the problem setter’s and the problem tester’s solutions in the editorial. YOu may go through them, if you wish to have some reference! 
There need not be any “thanks” in here. Discuss is here, so than we can learn and help. I learned a lot. Now, I try and help others, as much as I can, with what limited knowledge I have!