Блог

Прежде всего, я пытаюсь решить следующую проблему с помощью Python:

Арифметическая прогрессия — это последовательность вида a, a b, a 2b, …, a nb, где n=0, 1, 2, 3, … . Для этой задачи a — неотрицательное целое число, а b — положительное целое число.

Напишите программу, которая находит все арифметические прогрессии длины n в множестве S бисквитов. Множество бисквитов определяется как множество всех целых чисел вида p2 q2 (где ^{p и q — неотрицательные целые числа).}

Ограничение по времени: 5 секунд

Формат ввода:
Строка 1: N (3 <= N <= 25), длина прогрессий, для которых выполняется поиск, Строка 2: M (1 <= M <= 250), верхняя граница, ограничивающая поиск бисквитами с 0 <= p, q <= M.

Ввод образца:

 5
7
 

Формат вывода:
Если последовательность не найдена, чтение одной строки NONE . В противном случае выведите одну или несколько строк, каждая из которых содержит два целых числа: первый элемент в найденной последовательности и разницу между последовательными элементами в той же последовательности. Сначала строки должны быть упорядочены с наименьшими разностными последовательностями и наименьшим начальным номером в этих последовательностях.

Последовательностей будет не более 10 000.

Пример вывода:

 37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
 

Написанный мной код действительно работает, но он значительно превышает заданный лимит времени. Я не могу сказать, является ли это проблемой, вызванной самим алгоритмом или просто Python. Может кто-нибудь предложить способ сделать это менее чем за 5 секунд? Вот код:

 fin = open ('ariprog.in', 'r')
fout = open ('ariprog.out', 'w')

N:int=int(fin.readline().strip())#take N
M:int=int(fin.readline().strip())#take M

s:set=set()#set s 
ans:list=[]#the list that will contain the pairs
mx:int=M**2 * 2#absolute max value in the set s 

for j in range(M 1):#produce the set s 
    for i in range(j,M 1):
        h:int=(i**2) (j**2)
        s.add(h)

for stepVal in range(1,(mx//(N-1)) 1):#iterates over the possible step values
    for initial in s:#iterates over the possible starting points in the set s
        count:int=1
        k:int=initial
        while count<N:
            if k stepVal not in s:break #if the loop breaks, 
            k =stepVal                  #we don't add the pair to the answer list
            count =1
        else:ans.append([initial,stepVal])
ans.sort(key=lambda x:x[1]) #sort the answer list
if not ans:fout.write("NONE"   "n")
for i,e in ans:
    pr=f'{str(i)} {str(e)}n'
    fout.write(pr)
fout.close()
 

При представлении тестового примера 7 я получаю следующее сообщение:

   > Run 7: Execution error: Your program (`ariprog') used more than
        the allotted runtime of 5 seconds (it ended or was stopped at
        5.242 seconds) when presented with test case 7. It used 10368 KB
        of memory. 

        ------ Data for Run 7 [length=7 bytes] ------
        21 
        200 
        ----------------------------
 

Внутренний цикл можно оптимизировать, но для этого потребуется немного больше логики.

Идея состоит в том, что после проверки initial вы в зависимости от результата будете либо знать, что initial stepVal последовательности тоже не будет, либо что вам не нужно проверять первые N-1 числа (поскольку они уже были проверены).

И вы, кажется, генерируете результат по порядку, так что нет необходимости сортировать их.

Я удалил определение переменной, чтобы сэкономить память

Я также использовал понимание списка, где это возможно.

 fin = open ('ariprog.in', 'r')
fout = open ('ariprog.out', 'w')



ans:list=[]#the list that will contain the pairs

s = set([(i**2) (j**2) for j in range(int(fin.readline().strip()) 1) for i in range(j,int(fin.readline().strip()) 1)])

for stepVal in range(1,(int(fin.readline().strip())**2 * 2//(int(fin.readline().strip())-1)) 1):#iterates over the possible step values
    for initial in s:#iterates over the possible starting points in the set s
        count:int=1
        k:int=initial
        while count<int(fin.readline().strip()):
            if k stepVal not in s:break #if the loop breaks,
            k =stepVal                  #we don't add the pair to the answer list
            count =1
        else:ans.append([initial,stepVal])
ans.sort(key=lambda x:x[1]) #sort the answer list

if not ans:fout.write("NONE"   "n")


[fout.write (f'{str(i)} {str(e)}n') for i,e in ans]
fout.close()
 

Что могло бы немного ускорить процесс, так это подход к решению как к постепенному уточнению / фильтрации всего набора квадратов для каждого размера шага. Это может сократить время выполнения примерно на 20%

Однако я обнаружил, что реальное увеличение скорости может быть вызвано гипотезой (которую я пока не смог доказать), где в последовательностях из 4 или более элементов могут существовать только шаги, кратные 4.

 def findSequences(N,M,step=4):
    S       = { p*p q*q for p in range(M 1) for q in range(p,M 1) }
    if N<4 : step = 1
    for b in range(step,2*M*M//(N-1) 1,step):
        eligible = S
        for n in range(1,N):
            eligible = eligible.intersection(e-b for e in eligible)
            if not eligible: break            
        for a in sorted(eligible):
            yield a,b
            
print(*findSequences(5,7) )

# (1, 4) (37, 4) (2, 8) (29, 8) (1, 12) (5, 12) (13, 12) (17, 12) (5, 20) (2, 24)

print(*findSequences(21,200) )

# (1217, 84) (2434, 168) (4868, 336) (6085, 420) (9736, 672) (10953, 756) (12170, 840) (12953, 924) (15821, 1092)
 

На моем ноутбуке эта гипотеза сокращает время выполнения на 75%

Возможно, кто-то с более глубокими знаниями теории чисел может пролить некоторый свет на мою гипотезу о кратных 4.

Хотя я не могу объяснить, почему это так, гипотеза работает для M <= 250, как показано:

 all(b%4==0 for a,b in findSequences(4,250,1)) # returns True
 

И поскольку более длинные последовательности являются продолжениями более коротких, это будет справедливо для N = 5,6,7, …