03.12.2024 10:27
tapo4ki 0 1700 Источник

Всем привет, завершился набор в юбилейную 15-ю школу программистов HeadHunter. Поздравляем всех поступивших и желаем удачи остальным в следующий раз! Каждый год после старта школы мы разбираем решение задач, и этот год не исключение. Поехали!

В этом году в отборе участвовало 2349 человек, из них успешно решили оба задания 477, 116 дошли до собеседований и 58 поступили в школу.

Основная проблема этого года — LLM (большие языковые модели, обычно в лице ChatGPT). К сожалению, они умеют решать задачи лучше многих программистов. Некоторые ребята сдавали готовые решения через 3 минуты с сомнительными комментариями в коде в духе:

# create list of users and initialize it
users = […]

или другими очевидными намеками на то, что код писал не человек. Некоторые маскировали решение от LLM и доходили до собеседований, но на очном собеседовании вскрывалась правда. 

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

Задачи, как обычно, принимались на трех языках: Java, Python, JavaScript. Разберем примеры на Python-е, как на языке, наиболее похожем на псевдокод. Погнали к разборам:

Задача 1. Поле программиста Петра

После очередного завершенного проекта программист Петр решил переехать в деревню и заняться сельским хозяйством. Мелочиться он не стал, поэтому, помимо домика в деревне, сразу приобрел несколько идущих подряд параллельных участков поля, расположенных вдоль прямой дороги. Участки были разделены заборами, при этом все заборы начинались от той самой дороги, но заканчивались на разном удалении от нее, не доходя до противоположной границы участка.
Петру нужно объединить эти участки. Но так как Петр перфекционист, он непременно хочет, чтобы получившийся объединенный участок:

  1. Был прямоугольным;

  2. Был ограничен дорогой и двумя уже имеющимися заборами (забор необязательно использовать целиком, а вот удлинять забор нельзя);

  3. Имел наибольшую возможную площадь.

Как и положено разработчику, Петр получает 300к/наносек, поэтому его совсем не беспокоит тот факт, что часть территории окажется неиспользованной.

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

Входные данные (поступают в стандартный поток ввода)

На вход вашей программе подается одна строка, содержащая массив целых чисел length, где length[i] — длина i-го забора. Иными словами, i-й элемент массива задает забор в виде отрезка от (i, 0) до (i, length[i]), где 0 — это дорога.
Причем 0 ≤ length[i] ≤ 10 000, а количество заборов n удовлетворяет условию 2 ≤ n ≤ 100 000. Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются.

Выходные данные (ожидаются в стандартном потоке вывода)

Одно целое число, максимальная площадь образованного участка.

Пример 1

Ввод: 2 4 3 2 1 4 1
Вывод: 16
В первом примере участок наибольшей площади образуется между двумя заборами длины 4.

Пример 2

Ввод: 1 2
Вывод: 1
В данном примере второй забор используется не на всю длину, так как нас интересуют только прямоугольные участки.

Описание решения

В этом году в качестве первой задачи мы взяли классическую задачу на два указателя. В начале указатели будут находиться на максимальном удалении друг от друга. Они будут показывать на первый и последний заборы, что даст нам на первом шаге максимальное расстояние между заборами, а следовательно максимально возможное значение для одной из сторон прямоугольника. Затем с каждым шагом указатели будут приближаться друг к другу, сокращая это расстояние на 1 и пытаясь увеличить площадь за счёт длин заборов. Главная сложность в решении — понять, что, чтобы при уменьшении расстояния между заборами площадь могла увеличиваться, длина участка (то есть длина меньшего из двух рассматриваемых заборов) должна расти. Таким образом, никогда не имеет смысла перемещать указатель с более длинного из них. Например, пусть указатель l показывает на забор длины 5, а r — на длины 7. Текущая площадь будет равна 5 * d, где d — расстояние между этими заборами. Мы хотим попробовать посмотреть на заборы, находящиеся на расстоянии d-1 друг от друга. Если мы сместим указатель r, то независимо от длины следующего за ним забора, мы получим площадь не более 5 * (d - 1), даже если второй забор будет гораздо выше. Это строго меньше площади, полученной на предыдущем шаге. Таким образом, как и говорилось ранее, для увеличения площади всегда целесообразно сохранять более высокий забор.

Решение

length = list(map(int, input().split()))
l, r = 0, len(length) - 1
area = 0
while l < r:
    area = max(area, (r - l) * min(length[l], length[r]))
    if length[l] < length[r]:
        l += 1
    else:
        r -= 1
print(area)

Задача 2. Космическое путешествие

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

  1. Магические паромы, перемещающиеся между соседними островами (естественно, паром может двигаться в обе стороны), таким образом с острова, который стоит на i-ом месте в космическом ряду, можно попасть на i-1 и i+1 острова;

  2. Порталы, через которые можно телепортироваться между островами независимо от расстояния, но только если до катаклизма эти острова составляли один материк (любопытно, что материки в этом мире имели не названия, а номера).

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

Выходные данные (ожидаются в стандартном потоке вывода)

На вход вашей программе подается одна строка, содержащая массив целых чисел islands, где islands[i] — это числовое обозначение материка, к которому когда-то относился i-ый остров. Элементы в массиве расположены в том же порядке, что и острова в космическом пространстве. Причем -100 000 000 ≤ islands[i] ≤ 100 000 000, а количество островов n удовлетворяет условию 1 ≤ n ≤ 50 000. Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются.

Выходные данные (ожидаются в стандартном потоке вывода)

Одно целое число, минимальное число шагов от первого острова до последнего.

Пример 1

Ввод: 3 5 2 2 5
Вывод: 2
Простой пример для ознакомления с входными и выходными данными. На вход подаются 5 островов. С первого острова можно попасть только на второй с помощью парома. Порталы использовать не получится, так как нет других островов, носящих тот же номер материка. Со второго можно добраться на пароме обратно на первый или вперед на третий. А также можно переместиться через портал на пятый (ведь они имеют один и тот же номер). Таким образом мы можем переместиться от первой ячейки до последней за два шага.

Пример 2

Ввод: 11 -86 -86 201 11 86 86 86 3 201
Вывод: 3
Во втором примере потребуется уже 3 шага: перемещение через портал до 5-го острова, шаг назад до 4-го (с помощью парома) и, наконец, скачок через портал до последнего.

Пример 3

Ввод: 3 2 5 2 5 2 5 3
Вывод: 1
Тривиальный пример: требуется всего одно перемещение через портал от первого острова до последнего

Описание решения

На первый взгляд, эта задача решается обычным БФС, но если мы посмотрим на ограничения, то увидим, что мы даже не успеем заполнить список смежности за отведённое время. Поэтому обратим внимание на то, что наш граф имеет весьма специфичный вид с группами вершин, образующими полный подграф (по номеру материка). Сохраним граф в словаре: ключом будет выступать номер материка, к которому относился остров до катаклизма, а значением — список всех островов, относящихся к этому материку. Но и это ещё не всё. Даже в этом случае классический обход графа будет занимать O(n^2) времени, если большинство островов будут относиться к одному материку. Заметим, что как только мы посетим один из островов материка, мы уже будем иметь информацию о расстоянии до всех остальных островов, к нему относящихся. То есть повторный проход по вершинам данной части графа не имеет смысла, так как всегда будет упираться в классическое условие d[to] > d[v] + 1. Таким образом мы получаем до n бесполезных проходов. Чтобы избежать этой ситуации, будем удалять из словаря информацию о посещённых материках.
Ещё с одной сложностью столкнулись поступающие, решавшие задачу на JavaScript. Так как в этом языке нет структуры данных "очередь", многие использовали в качестве её замены обычный массив, применяя метод shift для удаления первого элемента и, конечно, получали асимптотику O(n^2). Эту проблему можно было решить, заменив удаление первого элемента на хранение всех попавших в неё элементов и поддержание индекса реального начала очереди.

Решение

from collections import deque

# Поиск в ширину с некоторыми доработками
def bfs(islands: list) -> int:
    continents = dict()
    for i in range(len(islands)):
        if islands[i] not in continents:
            continents[islands[i]] = []
        continents[islands[i]].append(i)
    queue = deque()
    queue.append(0)
    distance = [int(1e9)] * len(islands)  # Создаем и заполняем лист условно бесконечными значениями
    distance[0] = 0
    while queue:
        current_island = queue.popleft()
        # Соседние вершины обработаем отдельно
        if current_island > 0:
            destination_island = current_island - 1
            if distance[destination_island] > distance[current_island] + 1:
                distance[destination_island] = distance[current_island] + 1
                queue.append(destination_island)
        if current_island < len(islands) - 1:
            destination_island = current_island + 1
            if distance[destination_island] > distance[current_island] + 1:
                distance[destination_island] = distance[current_island] + 1
                queue.append(destination_island)
        # Пройдёмся по островам того же материка
        # Но только один раз для каждого материка (обратите внимание на pop)
        for destination_island in continents.pop(islands[current_island], []):
            if distance[destination_island] > distance[current_island] + 1:
                distance[destination_island] = distance[current_island] + 1
                queue.append(destination_island)
    return distance[-1]


print(bfs(list(map(int, input().split()))))

На этом все, спасибо за внимание.

Поздравляем всех поступивших — вы сделали первый шаг к успешной карьере в программировании! Для тех, кто не прошел в этом году: не останавливайтесь на достигнутом — приходите снова! Мы всегда рады видеть стремящихся к знаниям.Можно уже сейчас записаться на следующий набор — https://school.hh.ru/ Школа программистов ждет вас!

Комментарии (0)