Мой код FB HackerCup слишком медленный для больших входов

Я решал проблему Find the min в hackercup на facebook с помощью python, мой код отлично работает для ввода образцов, но для больших входов (10 ^ 9) для завершения требуется несколько часов.

Итак, возможно ли, что решение этой проблемы невозможно вычислить в течение 6 минут с помощью python? Или могут быть мои подходы слишком плохи?

Описание проблемы:

После отправки смайлов Джон решил играть с массивами. Знаете ли вы, что хакеры любят играть с массивами? Джон имеет индексный массив на основе нуля, m, который содержит n неотрицательные целые числа. Однако ему известны только первые k значения массива, и он хочет выяснить остальное.

Джон знает следующее: для каждого индекса 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 тестовые примеры, состоящие из двух строк.

  • Первая строка каждого тестового примера содержит целые числа, разделенные пробелом, 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).

    /li>

Я попробовал два подхода, но оба не смогли вернуть результаты за 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 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 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, но пока никто не ответил.

3 ответа

Вот мое решение 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, и если мы помним последовательные числа, которые мы можем найти в предыдущих k числах от 0 до p, то p никогда не уменьшит.

Если число m [i-k-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] -больше, чем-p".

Всякий раз, когда p равно k, начинается цикл, а размер цикла (k + 1), поэтому мы можем выпрыгнуть из расчета и распечатать ответ.


После не более k+1 шагов последние k+1 числа в массиве будут 0...k (в некотором порядке). Впоследствии последовательность предсказуема: m[i] = m[i-k-1]. Таким образом, способ решить эту проблему - выполнить наивную реализацию для шагов k+1. Затем у вас есть массив с элементами 2k+1 (первый k был сгенерирован из случайной последовательности, а другой k+1 из итерации).

Теперь последние k + 1 элементы будут повторяться бесконечно. Поэтому вы можете сразу вернуть результат для m[n]: it 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.


Я повысил производительность за счет добавления карты.

import sys, os
import collections
def min(str1, str2):
 para1 = str1.split()
 para2 = str2.split()
 n = int(para1[0])
 k = int(para1[1])
 a = int(para2[0])
 b = int(para2[1])
 c = int(para2[2])
 r = int(para2[3])
 m = [0] * (2*k+1)
 m[0] = a
 s = collections.Counter()
 s[a] += 1
 rs = {}
 for i in range(k+1):
 rs[i] = 1
 for i in xrange(1,k):
 v = (b * m[i - 1] + c) % r
 m[i] = v
 s[v] += 1
 if v < k:
 if v in rs:
 rs[v] -= 1
 if rs[v] == 0:
 del rs[v]
 for j in xrange(0,k+1):
 for t in rs:
 if not s[t]:
 m[k+j] = t
 if m[j] < k:
 if m[j] in rs:
 rs[m[j]] += 1
 else:
 rs[m[j]] = 0
 rs[t] -= 1
 if rs[t] == 0:
 del rs[t]
 s[t] = 1
 break
 s[m[j]] -= 1
 return m[k + ((n-k-1)%(k+1))]
if __name__=='__main__':
 lines = []
 user_input = raw_input()
 num = int(user_input)
 for i in xrange(num):
 input1 = raw_input()
 input2 = raw_input()
 print "Case #%s: %s"%(i+1, min(input1, input2))

licensed under cc by-sa 3.0 with attribution.