Приветствие:

В феврале 2026 года писал в своих каналах [1], что делал задачку по программированию для отборочного соревнования студкэмпа «Алиса и Умные устройства Яндекса» при поддержке НИУ ВШЭ и МФТИ [2]. Дошли руки сделать обзор.

Краткий фидбэк по задаче:

Задача

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

Условие в студию:

На планете сигма-терра обитают сигма-люди, которые живут миллионы лет и с детства занимаются спортивными мероприятиями. Каждый день они идут на тренировку и записывают сколько ультраграммов подняли сегодня в целых числах. В спортзале задумались какие веса используются клиентами чаще всего, чтобы оптимизировать запасы тренажеров. Для этого решили собрать статистику со всеми весами, которые отмечали клиенты. Вот только данные сейчас хранятся отдельно для каждого сигма-человека. Тогда руководство решило обратиться к программистам, чтобы те создали одну общую базу со всеми весами. Программисты с другой планеты заняты тем, что тоже поднимают веса, поэтому, когда им надо решить задачу, они обращаются к Землянам. В исходных данных есть два файла. Каждый файл описывает историю поднятых весов сигма-человека в спортзале. Т.к. сигма-люди только прогрессируют, веса идут от меньшего к большему. И т.к. они живут по миллиону лет, числа и файлы могут быть большие. Файлы историй одинакового размера. Вам на вход программы по техническим причинам даётся один общий файл, который представляет собой конкатенацию двух файлов с историями, без разделителей. Вы должны посчитать и вывести в стандартный вывод CRC32-хэш общей истории, в которой есть все веса из двух исходных файлов, так же в неубывающем порядке от меньшего к большему. Все файлы хранят веса в бинарном формате, все веса занимают одинаковый размер, разделителей нет.

Максимальный вес, который когда либо поднимал сигма-атлет - 9223372036854775807 ультраграммов.

Максимальное количество наблюдений на одного атлета - 134217728 дней.

Ограничение на время исполнения программы - 15 секунд.

Ограничение на RAM - 128Mb.

На вход нам даются два потока отсортированных 64-битных чисел (9223372036854775807 - это Long.MAX_VALUE), мы должны создать единый поток отсортированных данных. В качестве входящих потоков у нас максимум гигабайт (134217728 по 8 байт - получаем 1Gb), а на решение задачи допустимо использовать 128Mb RAM и 15 секунд времени CPU.

По техническим причинам...

Яндекс Контест позволяет на вход дать только один файл. Поэтому два файла понадобилось объединить в один. Так как размеры одинаковы, чтобы вычислить начало второго файла, достаточно поделить длину на два. На выходе сложно сделать файл, поэтому в результате вместо результирующего потока, в ответ пишется только одно число - CRC32 хэш потока.

Показывать код по задаче не буду, но идею обсудим.

Первое, что может прийти в голову, прочитать данные целиком и слить два массива. Такое решение на первой же строчке с большими файлами упрётся в лимит по памяти. Но я начал с него, чтобы у меня был baseline (базовая граница) для бенчмарков. А так же, чтобы нагенерировать файлы-ответы. Для генерации ответов локально можно дать памяти сколько угодно, а чем проще алгоритм, тем больше уверенности, что твои файлы решения - действительно рабочие и эталонные. Сравнивать их потом с помощью diff мне доводилось ещё не раз, убеждаясь в правильности работы подходов.

Так как целиком не получится, надо читать потоки кусочками. Считаем размеры буферов (можно отталкиваться от page cache), чтобы это было эффективно, и в итоге программа вкладывалась в 128 Mb. Тестируем размеры опытным путём. В итоге у меня использовались размеры буферов по 8Mb.

Поняв, что вам нужны буферы, можно пойти посмотреть в сторону BufferedInputStream, BufferedOutputStream. Такое решение будет работать, хотя вероятно долго.

Почему долго? Если данные в текстовом виде (изначально по задумке так и было), то парсинг будет есть большую часть CPU. Помимо этого куда вытаскивать данные из буфера? Кто-то их пытался вытащить в массив. В моих тестах тоже были решения, где буфер переходит в массив. Если на каждый буфер создавать новый массив - это значит, что вам надо будет дополнительно сгенерировать минимум те же 1024 Mb данных (массивов и т.п.), которые потом придётся чистить сборщику мусора, на это уйдёт ещё CPU. Поэтому для промежуточных массивов должны аллоцироваться объекты заранее и переиспользоваться.

В итоге основная идея проста: зная возможности Java, написать код, который с буферизацией будет сливать потоки, при этом генерируя минимум мусора.

Помимо своих бенчмарков, просил DeepSeek и Perplexity тоже написать код. Оба сработали плохо, так что ИИ слёту не помогал: решение DeepSeek работало 40 секунд с хвостом, а Perplexity зависал в вечном цикле. Если смотреть на долю комментариев в решениях студентов:

Можно предположить, что участники тоже пробовали воспользоваться ИИшкой, с первой попытки не получалось, но это не точно:

Потому что среди всех кто сдал задачу, порядка 30% сдали с первого раза. А всего сдавших больше половины участников:

Ошибки

На чём спотыкались участники?

Есть странные попытки сдачи с кодом на C++, Python-комментариями (#) посередине кода и другое, всё это и то, что не работало в JDK21, попало в CompilationError.

MemoryLimitExceeded и TimeLimitExceeded увидеть было ожидаемо, всё-таки для этого задача и придумывалась. Что таится под RuntimeError? MemoryLimitExceeded - отбивка платформы контеста, а RuntimeError - когда Java свалилась сама. Здесь признаюсь, не стал копать и анализировать все исключения под капотом.

Решения

В итоге имеем, что успешные попытки - это там, где участники догадались связать FileChannel и ByteBuffer с буферизацией всех данных на первом этапе. А на втором - смогли это ещё и аккуратно реализовать, потому что сортировка слиянием на буферизованных байтах не тривиальная вещь в обработке крайних случаев...

Спасибо за возможность участия:

• Анна Фисенко

• Команде Яндекс Образование.

Отдельное спасибо Натальи Баданиной за "ночные" тестирования задачи в Яндекс Контесте.

Ссылки:

1. Каналы: Dzen, Tg, Vk.

2. Сайт студкэмпа.

3. Код с анализом.

4. На связи: https://egorlitvinenko.ru

p.s. Статья - ручная работа, всё написано мной лично. LLM использовалась для генерации обработки результатов тестов в приложении marimo.