just wnt to knw the ways through which we cn reduce time taken by a programme to run
how cn v control tht
First thing is your algorithm, whatever language you use, make sure you use an efficient algorithm to solve the problem. Here is the link to know what better about algorithmic efficiency and complexities http://en.wikipedia.org/wiki/Algorithmic_efficiency
Once you ensure that you use an efficient algorithm, (this should suffice most of the times) if you want to further decrease the time taken by a program. Use FASTIO, the order of the time taken by the functions            scanf() > getchar() > getchar_unlocked()
But beware of using getchar_unlocked(), it might be faster but dangerous as it is a thread unsafe version. Itâs even deprecated in windows. If you refer some top submissions on a problem, you may end up looking at solutions using FASTIO methods.Even you may come across some problems where you couldnât solve unless you use FASTIO.
2 Likes
First of all make it clear that time taken by program depends upon the language you choose and the algorithm you apply.You can not change the time taken by the language compiler but you can certainly reduce the time complexity of your program.First of all, try to find out if that program could be solved through any other algorithm which has lesser time complexity than the algorithm you are applying.This completely depends upon your knowledge.Second thing you can do is to try to optimize your program in the best possible way.By optimization I mean ,check that the your program is not doing same thing again and again or not processing those values which are not needed to be processed at all to reach the answer.
Finally , I would like to say the more you practice the more you efficiently solve a problem.
1 Like
Good answer. I would like to quote an example here. See http://www.codechef.com/OCT14/problems/FATCHEF/ and my submissions http://www.codechef.com/OCT14/status/FATCHEF,chefkaushik94. I finally figured out that the TLE is because of my slow IO and it took me 35 fail submissions for that.
1 Like
Accessing the memory appropriately will give you a faster execution time. Basically, you are optimizing the compiler.
For example, check the code below :
/* Before /
for (j = 0; j < 100; j = j++)
for (i = 0; i < 5000; i = i++)
x[i][j] = 2 * x[i][j];
/ After */
for (i = 0; i < 5000; i = i++)
for (j = 0; j < 100; j = j++)
x[i][j] = 2 * x[i][j];
After modifying the code, we have sequential accesses instead of striding through memory every 100 words improves spatial locality.
Another way , would be reducing the loops. Example :
1 Like
With strict reference to online IDEs, we know that for a particular language such as C, it will perform some (say X) operations a second. This number cannot be changed by us.
But what does this number mean? It means that when the time given for a problem is 2 seconds, we can perform atmost 2*X operations in our program. This X is very high, so 1-2 operations more or less does not affect it. What affects is the following-
-
Loops- Most common reason for TLE errors or program taking too much time are loops, ESPECIALLY NESTED LOOPS. For example, lets saw we need to find a set of triple (x,y,z) which satisfy three equations given in Q (ax +by +cz= d, qx2 +wy2 +rz2 = y⌠and so on.)
What many new programmers do, is that they set up 3 nested loops to substitute vale of triples until a correct one is found. Eg-pre <
for(x=0;x<1000000 (given constraints in Q) ; x++) for(y=0;y<1000000;y++) for(z=0;z<1000000;z++) {if ( value of all 3 eq 0 on this value of x,y,z) `Assign the values and break out`}>
Now, the above loop takes ALOT of time as its complexity is O(n^3) , meaning for n=1000, it will need to perform at least 10^9 operations. By making appropriate substitutions and correlating the three variables together by given eq, this can be reduced to even O(n) complexity (depends on given equations)(in case of n=1000, 10^6 times faster!!!). This is the most important factor in considering time. One loop can be a difference between TLE and a successful submission.
-
The next is Input Output. Why I am telling this, is because, I was on a recent contest on hackerrank.com, and found my program giving TLE in many test cases. So I just removed all the code after input, put a print statement just after accepting all the input, and re submitted. To my surprise, I STILL GOT TLE in 75% test cases. It meant that the program gave TLE at the input step itself, because of how large the input was! So faster Input Output methods are given second priority.
-
The third is operations inside the loop and conditions. Once I was doing a problem on hackerearth.com, the time for problem was 1 sec and it involved in removing all repetitions in the string. Eg, aaabb to reduced to ab. All we needed t return was number of deletions. The length of string was from 1 to 10^5. Now, it was in EASY section. I simply ran a loop from start to end of string, storing number of each character in another array (arr[s[I]-âaâ]++ ). When I submitted my O(n) solution, I found that 25% of test cases gave TLE. Why? Because it was a veryâŚâcloseâ Q [test cases used almost complete of those X operations]. Those testcases were specifically designed as such to pass only on VERY FINE AND OPTIMAL solutions. After I added conditions like âif all numbers found then break the loop and find sum by length of string-26 &etcâ it passed 20% more. The remaining 5% required VERY fine optimisation of operations in loop. It was the most tricky easy problem. The question was easy, but the test cases made it clear that only a very fine solution would pass with full marks. Hence this is the third.
I would advise you to first correct these three things Once you do so, we can focus on even advance topics, but as of now, these three thigns should be your priority to make your program faster!
Hope it helped!!
(PS: If you find my answer decent, or if it helped you in any significant way, donât forget to upvote! I will appreciate that 
)
(Edit- Wait a minâŚI just realized this was a 2014 QâŚwhy was sit showing up on front page? I thought its a recent Q which needs to be answeredâŚ)
1 Like
Nice approach! But one thing you have to remember that whenever you write Any code in any language then always use pre<> tag! Ok
Oh you mean that âEnter code hereâ stuff! MAN ITS HAS BEEN BOTHERING ME SINCE FEW DAYS!! It was working fine but idk suddenly it JUST wouldnât let me post code properly. Trust me, I tried editing thrice!!!
You say putting code in " < >" ? I will give it a shot!! THANKS!!
Yes! Always put code in pre<> tag⌠you can do this by selecting the code that you want in a pre tag and just click the pre button on top of comment sectionâŚ
Thanks! It worked!
For solving any problem, you must design an efficient algorithm. Whether the problem is of daily life or any computer program, you have find out the easiest approach so that the computer processor can solve it faster.
After designing the algorithm, assume that i-th statement of your code costs âCiâ, excluding the comment statements. Now calculate how many times each line executes.
Let i-th line executes Ni times => Cost of i-th line = Ci*Ni
Now sum up all the costs of lines to get an estimation of how much time your algorithm would take.
From these calculations, one can observe that if there are several nested loops executing for high range, then the algorithm would take very long to complete its executions.
Therefore, practise more and more to design better algorithms for greater efficiency.
how to find the number of solutions to the equation ax+by+cz=N ?