I have made an attempt to use Lua as language for
solving problems
in a programming contest.
I came across a situation where I can solve a problem
using Pascal,
but not using Lua (4 test cases of 10 were failed due to
timeout).
This is the problem I'm talking about:
https://www.hackerrank.com/contests/infinitum17/challenges/divisor-exploration-2
The contest is over, so it is OK to discuss the
solutions.
On HackerRank one can use almost any programming
language to solve
the problem, but the timeout depends on the language of
your choice
(to make sure all participants have equal chances to
win).
The following table shows how many CPU seconds will be
given to your
program to compensate slowness of your language:
---------
2 C, Pascal
3 Brainf**k, C#, COBOL, D, PyPy
4 F#, Go, Java
5 Fortran, Haskell, Smalltalk, Tcl,
VB.NET
7 Scala
8 Clojure
9 Perl, PHP
10 _javascript_, Julia, Python, R, Ruby
12 Common Lisp, Erlang, Lua 5.2
---------
Full version is here:
https://www.hackerrank.com/environment
I guess that the complexity of test cases, created by
HackerRank,
were adjusted only for C language (good C solution
should take 2 sec),
and it was not tested that the same problem is solvable
in Lua in 12 sec.
I want you to try to solve this problem using Lua 5.2.
Your confirmation of unsolvability of
"divisor-exploration-2" in Lua
may be a reason to ask HackerRank to increase timeout
for Lua programs.
Otherwise, if someone will manage to solve it, this
would confirm
that I am not too good in optimizing Lua code :-)
Both these outcomes are welcome!
If you like to solve mathematical problems - please stop
reading here,
go register on HackerRank and try to solve this problem
by yourself.
(After the contest is over you still can submit
solutions for training)
For those who want to skip all underlying math and jump
directly to coding:
--- Attention: SPOILERS in the links below! ---
What exactly should be calculated in this task (the
formula):
https://i.imgur.com/FwpBOrO.png
Example of test case
http://pastebin.com/TBJjXpE1
My solution (which fails 40% of tests due to timeout):
http://pastebin.com/tWX8zJEL
I need to increase its speed by only about 10%.
But how?
The main problem is the following:
Calculations modulo (10^9+7) are very frequent in
programming contests.
Lua 5.2 does not have 64-bit numbers, so multiplication
(32-bit) * (32-bit) % (32-bit)
is quite slow, and, hence, raising to power
(32-bit) ^ (32-bit) % (32-bit)
is slow too.
Do you have any idea how to speed up these calculations?
