 |
lua-l archive |
|
|
||
|
Hi!-- Egor
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?