TLE in RECAMAN

[thealgorist]

I am a newbie to python programming. I tried the following problem
spoj.pl/problems/MRECAMAN/
and got a TLE

I expect bruteforcing will work in C++

but my straightforward code in Python TLEs..
I will post my code... Tell me if i am doing somethings in a stupid way, or is there some technique to make things faster...

# -*- coding: utf-8 -*-
R = 5000000	# an estimate of the maximum value
exists = range(R)	# defining the array... is there a faster way???
a = range(500001)	# defining an array
for i in range(R): exists[i] = 0
a[0] = 0
for i in range(1,500001):
  x = a[i-1]-i
  if ((x>0) and (exists[x]==0)):
    a[i] = x
  else:
    a[i] = a[i-1]  + i
  exists[a[i]] = 1
while 1:
  n = int(raw_input())
  if(n==-1): break
  print a[n]

[gorlum0_sof]

exists = range(R) # defining the array... is there a faster way???
set

And you can use psyco for overall speed up.

[numerix]

exists = range(R) # defining the array... is there a faster way???
set

That isn't a faster way to define an array, it's a hint to another approach to solve that problem.
According to your array (which is a Python-list):
Instead of filling your list first with all values from 0 to R-1 and after that setting all elements to 0, it is much more efficient to generate a list with all elements 0:

exists = [0]*R

[thealgorist]

thanx for the tips.
I also used fast I/O methods. and still TLE
so i guess i need to find a better algo

Can u suggest some simple problems which can be solved without TLE problems in Python?

[numerix]

Can u suggest some simple problems which can be solved without TLE problems in Python?

RECAMAN can be solved without TLE problems, if you implement it properly.

According to "simple problems": Take a look at the number of AC solutions (many solutions -> easy problem) and the runtime of AC Python solutions. If there are several solutions below 0.1 s, you will probably get your Python solution AC without special optimizations.

[suteerth]

thanx for the tips.
I also used fast I/O methods. and still TLE
so i guess i need to find a better algo

Can u suggest some simple problems which can be solved without TLE problems in Python?

Submit your code using the tip numerix gave you and it WILL give you ACC.

exists = [0]*5000000
a = [0]*500001
for i in range(1,500001):
  x = a[i-1]-i
  if ((x>0) and (exists[x]==0)):
    a[i] = x
  else:
    a[i] = a[i-1]  + i
  exists[a[i]] = 1
while 1:
  n = int(raw_input())
  if(n==-1): break
  print a[n]

[thealgorist]

Thank you.
I have got AC

I saw that numerix has got ACed in .11s
I am very curious

Can i see your code (only for learning purposes).

Please send it to my id: srivatsan1991@gmail.com
Or atleast put hints on the coding aspects that make it so fast!

[taijirobot_sof]

This code works well, and what's more, the exact length of exists should be 3012501, that means the first line can be this:

exists = [0]*3012501

thanx for the tips.
I also used fast I/O methods. and still TLE
so i guess i need to find a better algo

Can u suggest some simple problems which can be solved without TLE problems in Python?

Submit your code using the tip numerix gave you and it WILL give you ACC.

[code]
exists = [0]*5000000
a = [0]*500001
for i in range(1,500001):
x = a[i-1]-i
if ((x>0) and (exists[x]==0)):
a[i] = x
else:
a[i] = a[i-1] + i
exists[a[i]] = 1

while 1:
n = int(raw_input())
if(n==-1): break
print a[n]

[/code]

[shrima]

ur code is absolutely correct and it got acc with a small change in way of getting ip
evan im new to python and i jus used the input() method (instead of getting it as a string and converting it into int) and it got AC