Алгоритмы с нуля
Инструментарий: капстоун-вызов решения задач
Реальная задача не объявляет, какую технику она хочет, а сложные требуют не одной. Этот капстоун — единая многоэтапная система, где каждый этап указывает на свой инструмент из трека, и целое работает, только если выбрать каждый инструмент из ограничений и связать их вместе. Решить её — доказательство, что инструментарий твой.
Преврати трек в рабочий процесс решений: прочти задачу, выведи бюджет сложности, разложи на этапы, выбери верную технику и структуру данных для каждого этапа, скомбинируй их и обоснуй каждый выбор — включая то, почему отверг соблазнительную альтернативу.
Построй консольный 'планировщик сборки пакетов'. Имея набор пакетов с зависимостями, размерами и целочисленной 'ценностью', он должен: (a) находить циклы зависимостей и отклонять их, (b) вычислять корректный порядок сборки, (c) при бюджете диска B выбирать максимально ценное собираемое подмножество, уважающее и бюджет, и замыкание зависимостей, и (d) быстро отвечать на повторные запросы 'выбран ли пакет X?'. Каждый этап вынуждает осознанный выбор техники; ты должен назвать и обосновать каждый.
- Циклы обнаружены и сообщены с виновными пакетами; ацикличные входы дают корректный топологический порядок сборки, проверенный по рёбрам зависимостей.
- Выбранное подмножество замкнуто по зависимостям, в пределах бюджета диска B и доказуемо максимально по ценности на тестовых случаях — включая случай, построенный, чтобы побить жадность-по-отношению.
- Запросы принадлежности работают за O(1) в среднем, и код демонстрирует разницу против базовой линии линейного скана на большом выбранном множестве.
- Журнал выбора техники называет отдельную корректную технику на этап с её сложностью, а общая сложность конвейера указана и совпадает с выведенным бюджетом.
- Абзац-рефлексия: какая одна подсказка (размер ограничения, глагол задачи или структура) была решающей для выбора каждого этапа.
- Замени выбор битмасками при n ≤ 30 на настоящий knapsack-DP с учётом зависимостей и сравни оба по корректности и времени, задокументировав, где каждый становится лучшим выбором с ростом n.
- Добавь планирование кратчайшего времени сборки: при заданных временах сборки пакетов и неограниченных параллельных воркерах вычисли минимальный makespan через длиннейший путь по DAG (критический путь) — ещё одна техника на топосортировке.
- Добавь второй тип запроса — 'какие пакеты транзитивно зависят от X?' — и выбери верный обход (BFS или DFS по обратному графу), обосновав его ограничениями.
- Профилируй конвейер на синтетическом графе из 10^5 узлов и подтверди, что измеренное масштабирование каждого этапа совпадает с заявленной сложностью; отметь этап, который доминирует, и почему.
Это инструментарий в одной сборке: ты прочёл ограничения в бюджет, разложил систему на этапы и выбрал свою технику на этап — топосортировку для порядка и поиска циклов, обоснованный ограничением перебор подмножеств или DP для выбора с учётом замыкания, hash set для O(1) принадлежности — затем скомбинировал их и защитил каждый выбор от соблазнительной альтернативы. Самый важный артефакт — журнал выбора: в реальной инженерии назвать, почему эта техника, а не та, подкрепив ограничением, которое решило, — и есть навык, к которому вёл весь трек.