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-2The 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.NET7 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/environmentI 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.pngExample of test case
http://pastebin.com/TBJjXpE1My solution (which fails 40% of tests due to timeout):
http://pastebin.com/tWX8zJELI 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?
