Kefrov's blog

Runtime error on test 6. Why?
By Kefrov, history, 13 months ago, In English

Hello friends, help me figure out why I'm getting a Runtime error on test 6 for 1883E - Look Back. I think my solution is mathematically correct however python or the log2 function may have something to do with this.

Here's my submission : 229312603

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

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

This feels like an integer overflow. Maybe the variable “last” got too big

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

It can be overflow.

from math import log2, ceil
 
for test in range(int(input())):
    n = int(input())
    a = [int(x) for x in input().split()]
 
    res = 0
    last = a[0]
    for i in range(1, n):
        c = a[i]
        p = 0
        if c < last:
            p = ceil(log2(last / c))
            res += p
        last = c * (2 ** p) //This line
 
    print(res)

In marked line you are multipling c by number that can be really big(There is some if-s to fix this).

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

Thank you very much! I got the same problem and I was getting crazy trying to find out what was wrong. I found your accepted submission and it's a brilliant solution.

→ Reply