In September lunchtime problem, Chef and easy problem A, The answer for subtask 2 is accepted only if long long int is used for taking input of range 10^9. On the other hand the october lunchtime problem - Physics Class, the range of input is 10^9, but the answer with data type ‘int’ is giving correct answer. Both solutions employ sorting. Can somebody explain why this discrepancy?
Short answer is, that it depends also on output range not only the input range…
I don’t exactly remember the questions but saw my solutions, and the point of difference is in the first one we are adding numbers of the range 10^9. Now lets say you have 100 numbers each having value of 10^9, then the sum is 100*10^9 i.e. 10^11. i.e. my output variable can exceed the range of type of my input variables if number of terms i need to add is large. Hence, long long int. In the second one, we need to count the number of pairs and the maximum possible ans is nC2 cuz n maximum is 10^4, that will then fit in the range.
for this problem http://www.codechef.com/LTIME16/problems/CHEFA
the range of output is 10^5*10^9/2 , how can this fit into an integer .
links would be nice
I think the range of output of both is within 10^5.
@mansigupta Its true for the PHYSICS question but not for the CHEFA. Maximum range for it is 10^9*(N)
thanks all of you!