URGENT HELP NEEDED:why using int instead of long long int works??

general
1

I have been facing this problem from quite some time on codechef. And recently it happened in yesterdays cookoff… I just replaced long long int by int in my cookoff’s submission and got an ac… please i require immediate help.
My AC soln:CodeChef: Practical coding for everyone
My wrong submission:CodeChef: Practical coding for everyone
Believe me there is just a change of making all long long ints as ints…The same thing happened in my JTREE submission of long challenge!!!..please help!!!

2

Here is the correct version of your code (Passed using long long int only) https://www.codechef.com/viewplaintext/11568101

The 3 common mistakes made :

  1. Declaring array on the go. The codechef server has a small stack limit, 8MB. Since you are declaring array on the go, it is getting declared on stack. See the memory used by the code. It is 15.3MB, which will lead to stack overflow, leading to undefined behaviour, can give runtime error or wrong answer. Since size of int is half of “long long int”, memeory reduces by a factor of half which barely fits in the stack limit size, giving correct results. So, the conclusion is declare arrays globally i.e. on heap. You may also declare arrays on the go, in case of strict memory requirements using malloc, as it declares array on heap but again dynamic memory allocation takes time and may be a bit slow, around 0.01 - 0.10 seconds, depending on array sizes and the number of times they are accessed.

  2. On codechef servers prefer to use %lld as modifier in scanf instead of %I64d, although both give correct answers, time taken by them differs significantly. Here the submission using %I64d ( https://www.codechef.com/viewplaintext/11568109 ) uses 0.28 seconds while the one mentioned above takes 0.08 seconds. The exact reason for this is also unknown to me, but i keep it as a fact while submitting solutions.

  3. Although this will not give wrong answers, but consider this as a good practice. While using long long int, use LLONG_MAX and while using int use INT_MAX.

I hope this answers your doubt. If anything is unclear, ask in the comments below else mark this as accepted.

6 Likes
3

I am seriously very thankful to you for such a wonderful explanation.Seriously Thanks a lot!!!