TLE with int, and AC with long long - CPP

help
1

problem : CodeChef: Practical coding for everyone

TLE with int : CodeChef: Practical coding for everyone

AC with long long : CodeChef: Practical coding for everyone

2

Hello @anon94212090,
As you can see in the problem statement the value of A[i] is <= 10^18. The range of int is a Just a bit more than 10^9, whereas the range of long long int is a bit more than 10^18. Thats why your code gives TLE.

3

yes but in that case it sould have been WA, how TLE?

4

As integer can’t store values greater than 10^9, the program will overflow and result in giving TLE :slight_smile:

5

That’s not really an answer, as there are plenty of situations where an overflow occurs but causes a WA instead of a TLE :slight_smile:

(Also, technically, no overflow actually occurs - the act of reading a too-large value into a variable is perfectly well-defined).

@anon94212090 - try with the following test input:

2
3
173943434324324324 2 7
2
1 2

The fact that it causes TLE in this case relies on some Undefined Behaviour, so might not occur on all platforms.

Explanation:

  1. T is read successfully
  2. For T = 1, we goes through the loop and read N successfully.
  3. We do not read the first value of A successfully, as we read it in via the int variable x, and the value 173943434324324324 is too large to fit into an int.
    The behaviour, then, is (in C++17) to change the value of x to std::numeric_limits<int>::max() and to set the failbit of cin to true. [1]
    Since cins failbit is true, any subsequent attempt to read values into a variable via cin will fail, leaving that variable unchanged. [2]
  4. We fail to read in the next two values of A; note that the value of N is now -1.
  5. We decrement T, and go through the loop the final time.
  6. Here’s where the Undefined Behaviour comes in - N is not initialised, so we don’t know its value. However, most compilers will not change the stack address of N, so it still maintains its previous value - -1.
  7. We attempt to read the new value of N via cin, but cins failbit is still true - hence, the read fails, and N maintains its value - that is, -1.

The loop

while (N--)

for N = -1 will almost certainly timeout before it completes (in fact, whether it completes at all is Undefined).

[1] - see here. In particular:

[2] - see here. In particular:

9 Likes
6

thankyou that was wholesum information.

2 Likes