Разбор отбора Яндекс Кружка по ИИ. Часть 1

Вступление

Недавно завершился отборочный контест Яндекс Кружка по ИИ. В нём было 16 очень крутых задач, которые, конечно, большей частью участников были завайбкожены, но я вам попробую их разобрать так, как сам их решал. Как вы уже увидели в названии, будет несколько частей, потому что я ленивый что задач довольно много и писать разбор всех разом, ровно как и читать такой большой разбор тяжело.

A. Прогулка без повторов

Первая задача отбора является самой базовой задачей в олпроге. Это задача на два указателя, с помощью которых нам надо найти длину самого большого участка, где все буквы разные. Я думаю, немало людей решали подобную задачу.

def max_unique_run_length(s: str) -> int:
    ind1 = 0 # Начинаем с начала строки 
    ind2 = 0
    ls = list(s) # Лишнее действие, так как строка и так работает как список

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

    max_len = 0 # Максимальная длина

    for ind2 in range(len(ls)): # Перебираем ind2 до конца строки
        while ls[ind2] in in_use: # Пока в множестве букв уже есть эта буква
            in_use.remove(ls[ind1]) # Мы двигаем вправо левый указатель и убираем его буквы из множества
            ind1 += 1

        in_use.add(ls[ind2]) # Добавляем букву в множество

        lenn = ind2 - ind1 + 1 # Пересчитываем длину и, если рекорд, запысываем
        max_len = max(max_len, lenn)

    
    return max_len

Это очень простая разминочная задача. Сложность этого алгоритма равна $O(n)$: в худшем случае правый указатель совершает $n$ шагов, а левый - не более чем $n$. Итого, не более чем $2n$ шагов (операции с множеством имеют сложность $O(1)$), но мы упускаем константы, поэтому $O(n)$.

На этом всё. В следующий раз постораюсь разобрать больше, чем одну задачу, но сейчас я приболел, поэтому только 1.