lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Thu, Jan 5, 2017 at 9:14 AM, Dirk Laurie <> wrote:
2017-01-05 3:30 GMT+02:00 Egor Skriptunoff <>:
> On Wed, Jan 4, 2017 at 6:28 PM, Ką Mykolas <> wrote:
>> What about memorizing p^(a+k+2) as well?
> Powers are not reusable.
> You need to calculate 50 random powers of the same prime (exponents are
> randomly chosen from 100000 possible variants).

Even so. Memoize p^2, p^4, p^8, p^16. and compute p^(16*a+b) as (p^16)^a*p^b.

I've rewritten the code to cache all p^(2^k) and that gave me 0.3 seconds!
Now I'm under 12 seconds!

THANKS TO ALL for your advices!

But anyway, coding in Pascal is obviously easier:
one can successfully solve the same problem using less efficient algorithms.
Using Lua in HackerRank is harder.

Paradox: Lua was designed to reduce program development time,
but when one have only limited time in programming contest
to devise an algorithm and write a program,
it would be better to use Pascal :-)

Maybe Lua should have 13 seconds timeout to make the competition honest?