Как можно оптимизировать код в данной задаче? Не проходит по времени, использую два указателя

Question

Как можно оптимизировать код в данной задаче? Не проходит по времени, использую два указателя

Рейтинг: -2Ответов: 2Опубликовано: 23.02.2023

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.

Формат ввода В первой строке входного файла находятся два числа N и K (1 ≤ N, K ≤ 250000). Во второй строке входного файла следуют N чисел (разделенных пробелами), i-ое число второй строки задает цвет i-ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета

Формат вывода В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.

n,k=str(input()).split()
n=int(n)
k=int(k)
mass=str(input()).split()
mass=list(map(lambda x:int(x),mass))
l=0
r=n



while len(set(mass[l+1:r]))==k or len(set(mass[l:r-1]))==k :
    if len(set(mass[l+1:r]))==k:
        l=l+1
    elif len(set(mass[l:r-1]))==k:
        r=r-1            
print(l+1,r)

python

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

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

Создаём словарь (Counter) и переменную NumKinds для числа видов деревьев в движущемся окне (от левого указателя до правого).

Ставим оба указателя на начало.

Начинаем двигать правый указатель. На каждом шаге увеличиваем счётчик в словаре для текущего вида дерева. Если этот счётчик меняется с 0 на 1, инкрементируем NumKinds.

Когда NumKinds становится равным K, останавливаем продвижение правого индекса.

Начинаем двигать левый указатель. На каждом шаге уменьшаем счётчик в словаре для уходящего из окна вида дерева. Если этот счётчик меняется с 1 на 0, декрементируем NumKinds.

Когда NumKinds становится меньшим K, останавливаем продвижение левого индекса. Смотрим разницу индексов - если она меньше прежнего минимума длины- запоминаем.

Повторяем с правым указателем и т.д.

Сложность алгоритма линейная, время будет очень невелико

На informatics: Статус OK Пройдено тестов 21

import collections

#k = 3  #test
mass=[1, 2, 1, 1, 1, 1, 3, 1]
#mass=[1, 2, 1, 1, 1, 3, 1, 1, 2, 3]
#mass=[1, 2, 1, 3, 1, 3, 1, 1, 3]
#n = len(mass)

n, k = map(int, input().split())
mass = list(map(int, input().split()))
zmin, l, r  = 9999999, 0, 0
NumInWindow = 0
slovar = collections.Counter()

while r<n:
    slovar[mass[r]] += 1
    if slovar[mass[r]] == 1:
        NumInWindow  += 1
    r += 1

    while NumInWindow == k:
        slovar[mass[l]] -= 1
        if slovar[mass[l]] == 0:
            NumInWindow  -= 1
        l += 1

        if NumInWindow < k:
            if r - l < zmin:
                zmin, ll, rr = r - l, l, r

print(ll,rr)

Answer 2

▲ 0

Все таки получилось реализовать через словарь на свежую голову

 s=str(input()).split()
    n=int(s[0])
    k=int(s[1])
    mass=str(input()).split()
    mass=list(map(lambda x: int(x),mass))
    left=0
    right=0
    zmin=10000000000
    slovar={}
    slovar[mass[0]]=1
    for left in range(n):
        while right<n-1 and len(slovar)<k:
            right=right+1
            if mass[right] not in slovar:
                slovar[mass[right]]=1
            else:
                slovar[mass[right]]+=1
        if right-left<zmin and len(slovar)==k:
            zmin=right-left
            r=right
            l=left
        slovar[mass[left]]-=1
        if slovar[mass[left]]==0:
            del slovar[mass[left]]
    print(l+1,r+1)

Как можно оптимизировать код в данной задаче? Не проходит по времени, использую два указателя

Ответы