Ahmed-Nawaz's blog

64 bit > 32 bit?
By Ahmed-Nawaz, history, 5 months ago, In English

can anybody who uses #define int long long or #define int int64_t or doesnt uses int and only uses 64 bit integers please tell if through out the career due to MLE/TLE they have ever needed to switch to 32 bit and if it made a difference in verdict or not?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Ahmed-Nawaz (previous revision, new revision, compare).

→ Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

no da den

→ Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have had to switch to 32bit int only once or twice (never on codeforces). One of the times it was for some cses dp problem with very tight limits

→ Reply
»
5 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I have done problems where using long long everywhere will lead to TLE (specifically: https://usaco.org/index.php?page=viewproblem2&cpid=1207)

Just use 32bit numbers unless the problem statement shows you that values would be large or you are computing products of large numbers.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    Personally I use 32bit integers and 64bit integers specifically on what they are storing, not 64bit all the time.

    → Reply
»
5 months ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

MLE is situational, just check if (array size) * 8 bytes instead of 4 comfortably fits in the limit. Most problems do not care too much about memory.

For time, I ran some benchmarks for you. This is on GCC with -O2 on my i7-10700k.

  • 300M Adds: 0.42s vs 0.42s
  • 300M Multiplys (actually multiply-then-increment): 0.61-0.63s vs 0.61-0.62s
  • 300M Divides: 0.42-0.44s vs 0.42-0.44s (yes, divides are supposed to be slower, but the loop I have testing them is not the greatest)

Basically there's no difference in 32 vs 64 bits because they all probably execute exactly the same in the ALU.

(Bad) code: https://github.com/greatericontop/CompetitiveProgrammingStash/blob/main/random/benchmark.cpp

I tested again with a small loop written fully in assembly, 1 billion additions run in 0.20-0.21s vs 0.20-0.21s again.

Code: https://github.com/greatericontop/CompetitiveProgrammingStash/blob/main/random/benchmark_assembly.s (revised version to reduce the effect of pipelining)

→ Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have encountered a similar situation before. There was a problem where I use long long in a dp array that did not require long long, resulting in TLE. After changing it to int, it passed.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It was a question in Luogu. The evaluation machine of luogu is very slow. I don't know the situation in Codeforces.

    → Reply
    • »
      »
      »
      5 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I think the evalution machine of Luogu is not very slow.Like this.Well,I usually use long long except the problems of Ynoi.

      → Reply
    • »
      »
      »
      5 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I hit this trouble every now and then. Changing long long to int sometimes makes no difference, so I have to change the method — such as this.

      Personally, I use #define int long long most of the time. In ordinary problems, there is no need to worry too much about time and memory limits.

      → Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i solved one questions i dont really remember the rating and problem statment ,as much i remember it was 1400 rated problem where i came up with almost 1e7 time compexity solution ,it was getting TLE repeatedly and as mush as i can think it was a solution which cant be optimized further , i just thought why not switch from long long to int and surprisingly it passed the all test cases , from that day i get so scared to use long long . if i find the problem , i will update.

→ Reply
»
5 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I mostly use int64_t in my codes. TLE/MLE often occur in problems with strict constraints. Sometimes I put #define int64_t int32_t at the start of my codes.

→ Reply
»
5 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

I use #define int long long in most of my code, and it's really effective as I rarely see Wrong Answers due to overflow. However, it's not harmful; if possible, I still recommend thinking carefully before setting a variable to int64 or int32, as they have their own advantages.

→ Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Happened to me couple of times with some DP problems , got MLE using ll = long long; then changed it to int and passed peacefully.

→ Reply
»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

many times, especially in Macedonian national contests where the TL and ML limits are tight due to limitations of the judging system

→ Reply