PALIN timeout.... but why?

[mclaren24]

Hi guys.

Having a problem with PALIN, and after 5 hours of trying to figure it out, I'm no better off.

Here's my code - I get a timeout.

t=int(raw_input())
while t > 0:
  K = long(raw_input())
  u = K
  x = 0
  while x != 1:
    s = str(u)
    s = s[::-1]
    if (str(u) == s) & (long(s) != K):
      x = 1
      t -= 1
      print int(s)
    else:
      u += 1

[TripleM_sof]

The input can be up to 100000 digits long. If the input was only around 20 digits long, eg all ones, then you would have to add one about 10^10 times, which won't even come close to fitting in the time limit, let alone inputs of length 100000. You'll need a much cleverer algorithm.

[mclaren24]

Ahh... digits....

Ahh....

[MAK_sof]

I've been trying PALIN in Python, but I keep getting TLE. I think my technique is fast enough to be accepted in a faster language. The basic idea is to increment the middle digit, propagating carries to the left and the right if any.

I've tried coding this in two slightly different ways (the 'smallest' and 'smallest1' functions in my code) but both get TLE.

There are a number of solves for this one in Python, so can anyone help by sharing hints on making the code faster?

# Code removed after getting AC

[numerix]

Type conversions (int -> str and str -> int) are too expensive!

[MAK_sof]

Thanks for the help. I have removed operations converting large str->int and int->str. But still getting TLE (with both smallest and smallest1). Any other ways of making this faster?

# Code removed after getting AC

[numerix]

Still too many type conversions ...

[MAK_sof]

Thank you very much numerix. I got AC after removing all str->int and int->str conversions. I had not idea they were this slow in Python.