I_am_Mahi's blog

Getting TLE for latest G++23 and 20 but solution is accepted in G++17.
By I_am_Mahi, history, 12 hours ago, In English

I was solving a question Weird Sum, I wrote a solution and according to me it was within the constraints. It passed sample test cases on VS code but when I submitted it on the codeforces it gave TLE on the sample test case only. I tried changing the version of G++ and it worked. It got accepted on G++17. However, I cannot understand what my mistake was and what the improvements could be.

(Here's my submission: https://codeforces.me/contest/1648/submission/300963112)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. your solution is in the constraints but there is a bug in your implementation. you use .size() - i in your code but if im not wrong,.size() returns an unsigned short int that blows up when used in arithmic operation that is .size() - i in your code. instead i used an integer x = .size() and used x - i in your code and it got accepted and time was almost exactly as G++17.+

→ Reply
  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So when the condition for executing while loop was getting checked, the unsigned integer blew and it resulted in a very large positive number resulting in tle. Am I understanding it correctly? and Why did it get accepted in G++17, do things work differently in it?

    → Reply
    • »
      »
      »
      11 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i guess so and im not a technical freak in c++ so i don't know why it worked diffrently in G++17. let me know if you find out why the diffrence

      → Reply
    • »
      »
      »
      44 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When you do arithmetic operation each operand must be converted to the same type.

      What is size_t in G++17 7.3.2? It is uint32_t.
      What is size_t in G++23 14.2 64-bit? It is uint64_t.

      In both compilers long long is int64_t.

      And which type would be operands converted to?

      7.4 of this document gives an answer (this is C++20; both C++17 and C++23 has almost same wording):

      • Integer promotion is skipped in both cases
      • In C++17 32-bit applies if the type of the operand with signed integer type can represent all of the values of the type of the operand with unsigned integer type, the operand with unsigned integer type shall be converted to the type of the operand with signed integer type.
      • In C++23 64-bit applies if the operand that has unsigned integer type has rank greater than or equal to the rank of the type of the other operand, the operand with signed integer type shall be converted to the type of the operand with unsigned integer type

      So in C++17 32-bit both operands converted to signed int64_t, in C++23 64-bit operands converted to unsigned uint64_t.

      So in C++17 you got success because there wasn't any overflow, in C++23 there was.

      P.S. Main reason not between standards but between 32-bit/64-bit compilers.

      → Reply