Programming Problem - Block Game

Question

You may have an idea to solve the following problem.

John decided to buy some math toys for his son Johnny. One of his favorite toys are blocks of different colors. John decided to buy C blocks in different colors. For each color he will buy googol (10 ^ 100) blocks. All blocks of the same color have the same length. But blocks of different colors can vary in length. Jhonny decided to use these blocks to create a large 1 xn block. He wonders how much he can do. Two ways are considered different if there is a position in which the color is different. The example shows a red block of size 5, a blue block of size 3, and a green block of size 3. It shows that there are 12 ways to make a large block of length 11.

Each test case starts with an integer 1 ≤ C ≤ 100. The next line consists of integers. with an integer 1 ≤ leni ≤ 750 denotes the length of the i-th color. The next line is a positive integer N ≤ 10 ^ 15.

This problem should be solved in 20 seconds for T <= 25 test cases. The answer must be calculated MOD 100000007(prime).

This can be deduced into the matrix exponentiation problem, which can be solved relatively efficiently in O (N ^ 2,376 * log (max (leni))) using Coppersmith-Winograd and rapid exponentiation. But it seems that a more efficient algorithm is required, since Coppersmith-Winograd implies a large constant coefficient. Do you have any other ideas? This may be a problem with numerical theory or separation and subjugation.

Answer 1

For a solution, see the TopCoder stream . No one was close enough to find an answer in this thread.

Answer 2

Firstly, note that the number of blocks of each color you have is a complete red herring, since 10 ^ 100> N always. Thus, the number of blocks of each color is almost infinite.

Now note that in each position p(if there is a valid configuration that does not contain spaces, etc.). There should be a color block c. There is a len[c]way that the block must lie, so he is still on this position p.

- (N/2, ), b a . , ways(i), i ( ways(0)=1). ways(b)*ways(a). ways(i).

N/2, , ceil(log(N)). , N/2, N/2-750 N/2-750, 750 - , . 750*ceil(log(N)) ( - ) .

, , , memoisation, .

Python ( ):

T = int(raw_input())

for case in xrange(T):
    #read in the data
    C = int(raw_input())
    lengths = map(int, raw_input().split())
    minlength = min(lengths)
    n = int(raw_input())

    #setup memoisation, note all lengths less than the minimum length are
    #set to 0 as the algorithm needs this
    memoise = {}
    memoise[0] = 1
    for length in xrange(1, minlength):
       memoise[length] = 0

    def solve(n):
        global memoise
        if n in memoise:
            return memoise[n]

        ans = 0
        for i in xrange(C):
            if lengths[i] > n:
                continue
            if lengths[i] == n:
                ans += 1
                ans %= 100000007
                continue 
            for j in xrange(0, lengths[i]):
                b = n/2-lengths[i]+j
                a = n-(n/2+j)
                if b < 0 or a < 0:
                    continue
                ans += solve(b)*solve(a)
                ans %= 100000007
        memoise[n] = ans
        return memoise[n]
    solve(n)
    print "Case %d: %d" % (case+1, memoise[n])

. , , 20- , ++ somesuch.

EDIT: N = 10^15 750 , memoise 60000 , , solve(n) .

Answer 3

: c = 2, len1 = 1, len2 = 2, N- , () , phi ~ 1.61803399. N = 10 ^ 15, phi ^ (10 ^ 15), . (ln (phi ^ (10 ^ 15))/ln (2))/(8 * 2 ^ 40) ~ 79 . 79 20 , , .

, C , leni i. N, .

M, (i + 1,..., + k) , (i,..., + k-1). ( k + 1 ). k "", M ^ (10 ^ 15) (0... k-1).

() , , . , , p, p. p, p, bigints. , , " " mod-p.

Answer 4

@JPvdMerwe . @JPvdMerwe Dynamic Programming/memoisation, , , . .

, :

• , , , 2. , , .

• , , . , . , . @JPvdMerwe , .

• Modulo , . C = 100 . () .

A good way to test the effectiveness of a solution is a pathological case. The most difficult may be the following: length 10 ^ 15, C = 100, dimensions of the main unit.

Hope this helps.

Answer 5

In the answer above

    ans += 1
    ans %= 100000007

can be much faster without a modulo common:

    ans += 1
    if ans == 100000007 then ans = 0