Разбор задач Школы программистов 202327.10.2023 10:30

Школа программистов hh.ru 2023 успешно стартовала, а значит пришло время традиционно показать вам задачки со вступительных испытаний. В этой статье мы разберемся, как устроен отборочный тур изнутри и разберем решения задач этого года. Мы так уже делали: последние материалы с разборами можно посмотреть здесь и здесь. Поехали!

Этот набор уже 14-й! Каждый год Школа программистов немного отличается от предыдущей. Нам регулярно приходится меняться под потребности компании и совершенствовать процесс обучения, чтобы сделать его максимально полезным и эффективным для студентов. Одно остается неизменным: год обучения в Школе состоит из двух частей — теоретической и практической. С первой всё понятно: лекторы в лице опытных разработчиков вгружают тонну полезной информации в алчущие тайного знания светлые головы студентов. А вот практическая уже интереснее: ученики объединяются в команды, чтобы поработать над реальным проектом, который потом частенько уходит в прод. Обучение бесплатное, но и отбор достаточно требовательный — мы не обучаем азам разработки, поэтому наш курс не подойдет для начинающих энтузиастов кода.

Как рождаются задачи

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

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

Из чего состоят вступительные

У вступительных три этапа — регистрация, решение задач и интервью. Все начинается с регистрации участников на сайте Школы. Любой желающий может подать заявку на участие. В этом году мы получили почти три тысячи откликов — 2483 человека захотели пройти наш курс.

Регистрация засыпает, просыпаются задачи: мы предлагаем решить две задачи всем, кто оставил заявку на участие. И в этом году с обеими задачками успешно справились 590 человек, но часть из них — успешно списали.

Затем конкурсантам предстоит очное собеседование: чтобы мы могли познакомиться и дополнительно проверить знания. На интервью пришли 122 человека. А по его результатам новыми участниками Школы программистов стали 43 студента: 30 на бэкенд и 13 на фронтенд.

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

Наконец, задачи!

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

Задача 1. Офисные печеньки

Разработчик Фёдор очень любит печеньки в офисе, и точно знает все N мест, где их можно найти, а также точное количество печенек Сn в каждом месте. Сегодня Фёдор особенно голоден: он закончил большую задачу, и решает выделить себе M часов на то, чтобы съесть все печеньки в офисе.

Фёдор рассчитал минимальное количество печенек K, которое ему нужно съедать в течение часа так, чтобы в итоге успеть съесть все печеньки в офисе за выделенное время.

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

Коллеги, из уважения к Фёдору, никогда не трогают его любимые печеньки.

Пример:

Вывод: 3

Особенность заключается в том, что Фёдор должен провести весь час в одном месте, поэтому нельзя просто взять и поделить количество печенек на количество мест с округлением в большую сторону. Еще стоит помнить о граничной ситуации, которую придется обработать отдельно — если количество мест с печеньками больше количества часов, Фёдор точно не успеет. И, как обычно бывает в наших задачах, существует проблема оптимизации: в большом тесте для этой задачи N = 100 000, поэтому простой перебор не укладывается в 1 секунду.

Исходя из условий, наиболее простым и подходящим алгоритмом для решения будет бинарный поиск. Вот решение на python:

import math

# Проверяем, можно ли успеть съесть все печеньки с выбранным количеством
def can_be_eaten(cookies_amounts, per_hour, hours):
    time_to_eat = 0
    for amount in cookies_amounts:
        time_to_eat += math.ceil(amount / per_hour)

    return time_to_eat <= hours


def get_minimal_amount_to_eat(cookies_amounts, hours):
    # Если количество мест с печеньками больше количества часов - Фёдор точно не успеет
    if len(list(filter(lambda amount: amount > 0, cookies_amounts))) > hours:
        return 0

    start = 1
    end = max(cookies_amounts)

    while start < end:
        # Приближаемся к точному значению через бинарный поиск
        middle = start + math.floor((end - start) / 2)

        if can_be_eaten(cookies_amounts, middle, hours):
            end = middle
        else:
            start = middle + 1

    return end


if __name__ == '__main__':
    N, M = [int(x) for x in input().split()]  # Читаем N и M в первой строке
    C = [int(input()) for _ in range(N)]  # Читаем Cn в последующих строках

    print(get_minimal_amount_to_eat(C, M))

В общем, несложно, поехали дальше.

Задача 2. Лабиринт

Вы очнулись в определённой ячейке (x1, y1) лабиринта, с его картой в руке. Карта показывает, что лабиринт представляет собой окружённый сплошной стеной прямоугольник размерами N на M, состоящий из ячеек, каждая ячейка самого лабиринта — это проход 0 или стена 1. Перемещаться по лабиринту можно по горизонтали (меняя координату x) либо по вертикали (меняя координату y) на одну ячейку. Перемещаться по диагонали (меняя за один шаг обе координаты) нельзя.

На карте отмечен выход, и он находится в ячейке с координатами (x2, y2).

Задача — найти длину кратчайшего пути из ячейки пробуждения в ячейку выхода. В случае, если такого пути нет — нужно вывести 0

Пример:

Вывод: 6

Тоже довольно просто — по сути, нужно пройти по лабиринту из одной точки в другую, но IDCLIP использовать нельзя (нельзя ходить сквозь стены, я старый, да). Из типичных ошибок в этой задаче — участники либо пытались перебрать ячейки лабиринта, используя пару вложенных циклов, что выдает неправильный результат в случае разных поворотов пути, либо, в случае BFS/DFS забывали про учет посещенных ячеек и уходили в бесконечное путешествие, или забывали, что первый найденный DFS путь — не всегда самый короткий. Также, было много превышений лимитов на большом лабиринте 500 на 500, который построен таким образом, чтобы путь был существенно длиннее, чем диагональ.

Из простого, подойдёт либо DFS алгоритм с последующей проверкой длины пути, либо BFS — там первый найденный уже будет самым коротким. Например, вот такой:

from collections import deque


# Функция для проверки, является ли ячейка внутри лабиринта и доступной
def is_valid(x, y, N, M, maze):
    if 0 <= x < M and 0 <= y < N:
        return maze[y][x] == 0
    else:
        return False


def shortest_path_length(N, M, x1, y1, x2, y2, maze):
    queue = deque([(x1, y1, 0)])  # Каждый элемент очереди - кортеж (x, y, расстояние)

    visited = [[False] * N for _ in range(M)]
    visited[x1][y1] = True

    # Возможные направления движения (вверх, вниз, влево, вправо)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        x, y, distance = queue.popleft()

        if x == x2 and y == y2:
            return distance

        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if is_valid(new_x, new_y, N, M, maze) and not visited[new_x][new_y]:
                queue.append((new_x, new_y, distance + 1))
                visited[new_x][new_y] = True

    return 0


if __name__ == '__main__':
    N, M = map(int, input().split())
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    
    maze = []
    for _ in range(N):
        row = list(map(int, input().split()))
        maze.append(row)
    
    print(shortest_path_length(N, M, x1, y1, x2, y2, maze))

Ну вот и всё

Большое спасибо всем, кто подает заявки в нашу Школу и решает задачки. Надеемся, они вам понравились! Нам будет полезно, если вы оставите обратную связь по задачам и процессам набора — можно прямо здесь, в комментариях под статьей.

Отдельно обращаемся к тем, кого с каждым годом становится всё больше — к списавшим решения. Не надо так. Мы уже много раз рассказывали о том, что после решения всегда будет устное собеседование с life-coding, который крайне сложно списать. Попробуйте в следующем году сделать всё сами, так ведь в разы интереснее.

Увидимся в следующем году! А пока мы будем рады, если вы поучаствуете в нашем ежегодном исследовании узнаваемости брендов IT-компаний. Для этого нужно пройти маленький, но очень полезный опрос. Результатами исследования мы поделимся с вами в одном из следующих материалов, например, как здесь и здесь.

Где ты хочешь работать?

Мы снова запускаем ежегодное исследование узнаваемости брендов IT-компаний на российском рынке. Каждый год изучаем, какие айтишки у нас знают лучше, и в каких хочется работать большинству специалистов.

Пройди опрос и расскажи о своих впечатлениях от сегодняшнего IT в РФ.

Твои ответы помогут нам составить наиболее объективную картину, которой мы по традиции поделимся со всеми здесь.