Re: Using Lua in programming contests

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

Hi Egor,

you may possibly stay within the tmieout with this algorithm:
(this isonly a test snippet, it uses fixed a and m)

local p={ 2,3,5,7,11,13,17,19 }
local m=2
local a=4

-- vektor of exponents
local i={}
local sum=0

-- k is the exponent to count through
-- u is the available occurrences
--
local function find( k, u )
    if k==0 then
        -- made a full counting step
        -- compute the divisor from the  prime factors
        local f=1
        for j,e in ipairs( i ) do
            f = f * p[j] ^ e
        end
        -- multiply by frequency and add
        sum = sum + f*u
        while sum > 1000000007 do sum = sum - 1000000007 end
    else
        i[k-1] = 0
        for x=0,a+k do
            i[k] = x
            find( k-1, u * (a+k+1-x) )
        end
    end
end

find(m, 1)
print(sum)


Am 04.01.2017 um 13:10 schrieb Egor Skriptunoff:
> 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.