Re: Using Lua in programming contests

[Oliver Kroth <oliver.kroth@...>]

Hi,

you may possibly get along without modular exponentiation The product n does not have to be computed. You just need to memorise how many of which prime factors you have,
and then compute the sum of all different subsets of them plus the number of subsets. Subtract 1000000007 whenever your results get larger.

And use Erastosthenes to find teh first 10000 prime numbers. YOu may do this in advance and use a fixed array to speed things up. Or just pick them form a web page.

--
Oliver

Am 04.01.2017 um 16:28 schrieb Ką Mykolas:

Quick brainstorm:

For modulo exponentiation You could try something like modular exponentiation [1].


Also, are You sure You need those fancy metatables? I guess You could shave some time ditching those....

What about memorizing p^(a+k+2) as well?

Maybe You could employ Wilson's Theorem [2] as well? I do recall something similar in Project Euler.

[1] https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
[2] https://en.wikipedia.org/wiki/Wilson's_theorem

On Wed, Jan 4, 2017 at 2:10 PM, Egor Skriptunoff <egor.skriptunoff@gmail.com> wrote:

Hi!

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?

-- Egor