I have a few doubts related to execution time …(though they are not much related to eachother.)
1.I submitted these two solutions for kingcon problem (in APRIL13) first and second The only difference being that in the first an extra command is there ("cout<<“dfs”;)which is executed at most once for a given test case.
For first one time: 0.37 mem: 2.9M (Wrong Answer).
For second one time: (TLE) mem:28.2M (TLE). Why it is so??
2.If we use say unsigned long long int in place where just int would suffice why the time taken increases?
3.Suppose the time limit given for a given problem is 2 sec. and we are considering an algorithm of O(n) and say n is of order 10^8. Let us assume that a processor that we use processes about 10^8 instructions per sec.Now,the total no of instructions in our code may be 2x10^8 to 5x10^8.So, how do we come to know that the code will execute in 2 sec or 5 sec ,when we don’t now the actual speed of processor.
Edit: It is related to 1 point
I would like to add third soln
time: 3.32 mem:3M (AC)
The only difference between this and second soln is that cin>>u>>v; is replaced by scanf("%d%d",&u,&v); It is fine that time has reduced but why has memory reduced so much…??
@prakharsharma >>
First of all, generally, cout is slower than printf, so you can see a majority of C++ programmers still using printf in situations where time really matters.
Secondly, you can check the running time of your code by first generating a(or few) test files yourself based on the constraints and then running your code over those tests.
You can read my answer to a similar question regarding execution time for implementation of the same.
@bugkiller There is no question about cout being slower than printf().
For running time ,I wanted to know that before implementing an algo how can we assure ourselves that ,if it is implemented , it will execute in the given time .I agree that after implementing it ,execution time can be found(and that too would be machine dependent) but I guess this is not what we would always like to do…
For submissions,I too think the same but I guess first the output files are obtained and then they are checked. Or may be as there are many test files ,checking is done after obtaining each output file.
@prakharsharma…it is all depended on how much practise you have done…and how many algorithm based problems you have solved…and also by seeing the constraints you can get an idea if a naive n^2 or n^3 algo will pass or maybe we would require a NlogN solution…also during the contest by seeing the time that the best AC soln took and the worst time that has been AC you can judge what type of algo may pass and which type may give a TLE verdict…in short practise and observation is the key…
i also would like to add that…whenever you solve a practise ques…suppose u get a AC time of 0.35 secs…and u see there are solutions which have been AC in or arnd time 0.00 then dont hesitate even a bit to see the solns after you have done solving…take a look go through their algo…if there is something else they have done(except for fast IO) then voila you get something new to learn…
@prakharsharma I think the answer to your 1st qn is that the program execution is terminated when the judge encounters an incorrect answer and does not check the code for subsequent input files. it displays only memory and time consumed till incorrect answer was encountered.
Well, this is a bit off-topic, but, everyone knows that scanf()/printf() is a lot faster than cin/cout… And that can greatly influence the performance of a program over the judge.
The main reason why this happens is due to the fact that cin and cout are, in a sense, higher level versions of scanf()/printf().
As you all might be aware of, we are required to read input from stdin and write to stdout.
The functions from C, as they require the include of the header <stdio.h>, directly and naturally write to this stdout and read from stdin, which makes them “low-level” in the sense we are discussing.
On the other hand, cin and cout, require the use of the header .
The standard input stream is a source of characters determined by the environment. It is generally assumed to be input from an external source, such as the keyboard or a file.
As an object of class istream, characters can be retrieved either as formatted data using the extraction operator (operator>>) or as unformatted data, using member functions such as read.
The object is declared in header with external linkage and static duration: it lasts the entire duration of the program.
cin is tied to the standard output stream cout (see ios::tie), which indicates that cout’s buffer is flushed (see ostream::flush) before each i/o operation performed on cin.
