Hello, I was recently coding a problem and my approach was correct. But I was using all variables in the form of long long int. I had used #define int long long.
In this problem, it was not necessary to use long long.
I submitted code and result was TLE. And I observed that the time taken was above 3200 ms in cp editor. Then after scratching my head for 1 hour, I atlast went for other users' solutions. The only difference was they used int and approach was the same. I did the same. I deleted this line #define int long long. The time taken was now slightly above 2500 ms. I submitted the code and it was accepted.
Bonus questions : My second successful code was taking time above of 2500ms in my local machine(in cp editor). But the time constraint of that problem was 2 seconds. Why was the code accepted? The problem was from cses problem set. Are there any relatively similar incidents that occurred to you? I would be happy to know some, especially in codeforces platform?
1)Yes. On a 32 bit compiler, integer operations(or more specifically, 32 bit operations) are made in 1 instruction. On the other hand, 64 bit data structures like long long are made in 2 instructions inside processor. So that is roughly double the amount but in fact, it will usually be less than double the time. The reason for that can be many. First, not all operations are long long in your code. Second, compiler optimizations might've optimized it and processor optimizations too. If there is a 64 bit compiler on CSES(in codeforces, there is), use it. This will perform long long operations in only 1 instruction which is pretty neat.
2) Your compiler settings might be different than the plateform's. Add this line in your code before includes:
Your program should run faster. Try other more optimizations too:
The above might or might not work. If you own a modern processor, it should work.
Yeah using long long makes program slow a little bit. But it won't affect much. In most of the problems you will not see any significant change if you use int instead of long long. But very few questions have strict time constraint and there you have to use int for AC. I faced this problem in a contest on codechef where using long long was giving TLE. But I was sure that time complexity is fine for this problem. So after checking for some edge cases, I checked the submission time of other users during the contest and found that it was quite close to the maximum time allowed for the question. So I immediately changed long long to int and code got accepted.
It affects the runtime on 32-bit compilers. However, if you use C++17 64-bit, then there won't be any runtime penalty.
https://codeforces.me/contest/1538/submission/119209438
In c++17 also it is giving TLE
That could be because of cache effects. int takes up less space than long long and so you can fit more ints than long longs in cache.
The runtime of int vs long long (32 bits vs 64 bits) depends on the architecture of the machine. Most machines, including yours, are probably 64 bits. But codeforces has 32 bits archtecture, so int is faster than long long in codeforces, but long long should be faster on your machine. (actually this should be faster thing is not really that hard of a rule, it may vary on the operation being performed and may not behave as I described, but overall should be something like what I said)
Happened with me as well in Problem D of last contest. The only difference in these solutions is that a,b,k are int in first, and long long in second. AC TLE