我的FB HackerCup代码对大输入来说太慢了

Question

我正在Find the min使用python 解决facebook hackercup上的问题,我的代码适用于样本输入但是对于大输入(10 ^ 9),它需要数小时才能完成.

那么,有可能使用python在6分钟内无法计算出该问题的解决方案吗？或者可能是我的方法太糟糕了？

问题陈述:

发送表情后,John决定玩数组.你知道黑客喜欢玩阵列吗？John有一个从零开始的索引数组m,它包含n非负整数.但是,只有k阵列的第一个值是他知道的,他想要弄清楚剩下的.

John知道以下内容:对于每个索引i,其中k <= i < n,m[i]是最小的非负整数,它不包含在先前的*k*值中m.

例如,如果k = 3,n = 4以及已知值m是[2, 3, 0],他能弄清楚,m[3] = 1.

约翰非常忙于让世界变得更加开放和联系,因此,他没有时间去弄清楚阵列的其余部分.帮助他是你的任务.

给定第一个k值m,计算该数组的第n个值.(即m[n - 1]).

由于价值观n和k可能非常大,我们用一个伪随机数生成器来计算第一k的价值观m.给定的正整数a,b,c和r,的已知值m可如下计算:

m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k

输入

• 第一行包含整数T(T <= 20),测试用例的数量.

• 接下来是T测试用例,每个测试用例包含2行.

• 每个测试用例的第一行包含2个空格分隔的整数 n,k(1 <= k <= 10^5,k < n <= 10^9).

• 每个测试用例的第二行包含4个空格隔开的整数 a,b,c,r(0 <= A,B,C <= 10 ^ 9,1 <= R <= 10 ^ 9).

我尝试了两种方法但都未能在6分钟内返回结果,这是我的两种方法:

第一:

import sys
cases=sys.stdin.readlines()
def func(line1,line2):
    n,k=map(int,line1.split())
    a,b,c,r =map(int,line2.split())
    m=[None]*n                     #initialize the list
    m[0]=a
    for i in xrange(1,k):          #set the first k values using the formula
        m[i]= (b * m[i - 1] + c) % r
    #print m    
    for j in range(0,n-k):         #now set the value of m[k], m[k+1],.. upto m[n-1]

        temp=set(m[j:k+j])     # create a set from the K values relative to current index
        i=-1                   #start at 0, lowest +ve integer
        while True:           
            i+=1
            if i not in temp:  #if that +ve integer is not present in temp
                m[k+j]=i       
                break

    return m[-1]

for ind,case in enumerate(xrange(1,len(cases),2)):
    ans=func(cases[case],cases[case+1])
    print "Case #{0}: {1}".format(ind+1,ans)  

第二:

import sys
cases=sys.stdin.readlines()
def func(line1,line2):
    n,k=map(int,line1.split())
    a,b,c,r =map(int,line2.split())
    m=[None]*n                       #initialize
    m[0]=a                  
    for i in xrange(1,k):            #same as above          
        m[i]= (b * m[i - 1] + c) % r

    #instead of generating a set in each iteration , I used a 
    # dictionary this time.
    #Now, if the count of an item is 0 then it
    #means the item is not present in the previous K items
    #and can be added as the min value


    temp={}
    for x in m[0:k]:                   
        temp[x]=temp.get(x,0)+1       

    i=-1
    while True:
            i+=1
            if i not in temp:
                m[k]=i          #set the value of m[k]
                break
    for j in range(1,n-k):      #now set the values of m[k+1] to m[n-1]
        i=-1
        temp[m[j-1]] -= 1       #decrement it's value, as it is now out of K items
        temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1   # new item added to the current K-1 items

        while True:
            i+=1
            if i not in temp or temp[i]==0:  #if i not found in dict or it's val is 0
                m[k+j]=i                     
                break

    return m[-1]

for ind,case in enumerate(xrange(1,len(cases),2)):
    ans=func(cases[case],cases[case+1])
    print "Case #{0}: {1}".format(ind+1,ans)  

第二种方法中的最后一个for循环也可以写成:

for j in range(1,n-k):
    i=-1
    temp[m[j-1]] -= 1
    if temp[m[j-1]]==0:
        temp.pop(m[j-1])      #same as above but pop the key this time
    temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1

    while True:
        i+=1
        if i not in temp:
            m[k+j]=i
            break

样本输入:

5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46

输出:

Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12

我已经尝试过codereview,但还没有人回复.

Answer 1

在大多数k+1步骤之后,k+1数组中的最后一个数字将是0...k(按某种顺序).随后,序列是可预测的:m[i] = m[i-k-1].所以解决这个问题的方法就是为你的k+1步骤运行你的天真实现.然后你有一个包含2k+1元素的数组(第一个k是从随机序列生成的,另一个k+1是迭代生成的).

现在,最后的k + 1个元素将无限重复.所以你可以m[n]立即返回结果:它是m[k + (n-k-1) % (k+1)].

这是一些实现它的代码.

import collections

def initial_seq(k, a, b, c, r):
    v = a
    for _ in xrange(k):
        yield v
        v = (b * v + c) % r

def find_min(n, k, a, b, c, r):
    m = [0] * (2 * k + 1)
    for i, v in enumerate(initial_seq(k, a, b, c, r)):
        m[i] = v
    ks = range(k+1)
    s = collections.Counter(m[:k])
    for i in xrange(k, len(m)):
        m[i] = next(j for j in ks if not s[j])
        ks.remove(m[i])
        s[m[i-k]] -= 1
    return m[k + (n - k - 1) % (k + 1)]


print find_min(97, 39, 34, 37, 656, 97)
print find_min(186, 75, 68, 16, 539, 186)
print find_min(137, 49, 48, 17, 461, 137)
print find_min(1000000000, 100000, 48, 17, 461, 137)

这四种情况在我的机器上运行4秒钟,最后一种情况可能最大n.

Answer 2

这是我的O(k)解决方案,它基于与上面相同的想法,但运行速度更快.

import os, sys

f = open(sys.argv[1], 'r')

T = int(f.readline())

def next(ary, start):
    j = start
    l = len(ary)
    ret = start - 1
    while j < l and ary[j]:
        ret = j
        j += 1
    return ret

for t in range(T):
    n, k = map(int, f.readline().strip().split(' '))
    a, b, c, r = map(int, f.readline().strip().split(' '))

    m = [0] * (4 * k)
    s = [0] * (k+1)
    m[0] = a
    if m[0] <= k:
        s[m[0]] = 1
    for i in xrange(1, k):
        m[i] = (b * m[i-1] + c) % r
        if m[i] < k+1:
            s[m[i]] += 1

    p = next(s, 0)
    m[k] = p + 1
    p = next(s, p+2)

    for i in xrange(k+1, n):
        if m[i-k-1] > p or s[m[i-k-1]] > 1:
            m[i] = p + 1
            if m[i-k-1] <= k:
                s[m[i-k-1]] -= 1
            s[m[i]] += 1
            p = next(s, p+2)
        else:
            m[i] = m[i-k-1]
        if p == k:
            break

    if p != k:
        print 'Case #%d: %d' % (t+1, m[n-1])
    else:
        print 'Case #%d: %d' % (t+1, m[i-k + (n-i+k+k) % (k+1)])

这里的关键点是,m [i]永远不会超过k,如果我们记住连续数字,我们可以在从0到p的先前k个数字中找到,那么p将永远不会减少.

如果数m [ik-1]大于p,那么显然我们应该将m [i]设置为p + 1,并且p将增加至少1.

如果数m [ik-1]小于或等于p,那么我们应该考虑m [ik:i]中是否存在相同的数,如果不存在,m [i]应该等于m [ik-1],如果是,我们应该将m [i]设置为p + 1,就像"m [ik-1] -larger-than-p"情况一样.

每当p等于k,循环开始,循环大小为(k + 1),所以我们可以跳出计算并立即打印出答案.