Rec tle

[budabudimir]

Hi,
I am solving this problem : spoj.pl/problems/REC/
I am wondering, what is expected complexiti for this problem. I have O ( log ( n % m ) ) per test. All in all O( T * log ( n % m ) ). But it TLEs.
I would be grateful for any suggestion you might have.
Thx in advance.

[leppyr64]

I thought the beauty of doing this is python was that you wouldn't need all those %'s.

I doubt that the nod operator is any faster in python than it is in c.

[numerix]

I don't know if it's the number of "mods" (I have 7 mods in my AC submission), but - sure - avoiding mod is not a bad thing.
On the other hand: If numbers get too large, it also slows down the algorithm.

What could be done:
- Generate a large number of random generated testcases
- Do some profiling and look for the bottleneck
- Do e.g. some varations with calculations: Remove some mods or add some mods: What effect has it on the runtime?
- Try other possibilities of I/O. Though it has not to be really optimized, it must be considered here because of large I/O. raw_input() may be too slow in this case. Also try some output variations.

By the way: You know psyco?

[budabudimir]

Ok thx for advices. What do you recommend to be input method.

[numerix]

Ok thx for advices. What do you recommend to be input method.

If you want fast input with Python, do some experimenting on your own.
If you e.g. search in the forum, you'll find different approaches to read from stdin. Compare the runtime with random data.