В 2024 году я принял участие в этом конкурсе и стал победителем (🎉), поэтому хочу из первых рук поделиться информацией о том, как это было.
В первой статье с общей информацией о конкурсе я рассказал о том, какие этапы необходимо было пройти.
Во второй части речь шла о первых трех заданиях предметного этапа.
Теперь представлю те задания, которые стопроцентно решить не удалось.
Задача D. Максимальный четный отрезок
В этом задании я увидел вариацию задания номер 27 из ЕГЭ по информатике. И решение строил на этой основе. Решал методом префиксных сумм. Задача чуть усложняется тем, что необходимо запомнить границы отрезка. Само решение сложнее не становится, просто необходимо запоминать еще и границы. Так же стоит обратить внимание, что числа могут быть отрицательными.
Сначала попробовал сделать переборное решение, которое ожидаемо получило time limit на последних тестах, набрав 58 баллов из 100
Потом перешел к эффективному по времени решению. Для него необходимо посчитать префиксные суммы. быстрый ответ Яндекса на тему что это
Таким образом, для нахождения суммы элементов отрезка мы будем складывать два значения префиксных сумм. Заметим, что получить четную сумму двух слагаемых можно если оба четные или оба нечетные.
Алгоритм перебирает каждую префиксную сумму и подбирает ей такую префиксную сумму из чисел слева, чтобы в итоге получилась максимальная четная сумма. А для этого мы должны знать две величины: минимальную четную и нечетную префиксную сумму от начала последовательности. Но в задаче есть еще условие, что длина отрезка тоже должна быть четной. Поэтому храним уже четыре величины: минимальные четные и нечетные суммы, стоящие на четных и нечетных позициях. А учитывая, что нам нужны еще и границы отрезков, то надо еще хранить индексы этих сумм.
Далее реализуем описанный выше алгоритм: перебираем суммы и подбираем им парные, дающие четную длину и четную сумму
Данное решение сработало не на всех тестах
Время выполнения заданий было весьма ограничено, поэтому я решил что лучше будет перейти к другим задачам, чем пытаться отладить это решение.
Разбор от авторов лаконичен и содержит слова "тривиально" и "прорелаксируем"
Задача E. Броски шариков
В этой задаче мне так и не удалось понять до конца условие. Задача очень простая, если у нас неограниченное количество шариков. Тогда выигрышная стратегия бросания - это бинарный поиск. В этом случае нам требуется подобрать степень двойки, не меньшую количества этажей. Но в задаче у нас ограниченное количество шариков. В процессе решения я рисовал эти несчастные этажи на бумаге, строил в электронных таблицах дома, закрашивал ячейки этажей. В общем, потратил много времени, но построить математическую модель решения не смог. Решение без учета ограничений на шары набрало 60 баллов. Для разнообразия в решении использовал динамическое программирование. В карусели - авторское решение
Задача F. Разработка тестов для задачи «Мастерство фотографии»
Необычная задача, как и написано в условии. Нужно составить тесты так, чтобы неверные решения их не прошли. Тут навскидку накидал несколько тестов, взял граничные значения переменных, некоторые частные случаи, но в итоге набрал только 21 балл, что означает, что 13 решений из 20 я поймал на ошибках. Авторского разбора у этой задачи нет. Для успешного решения нужна аналитика условия, поиск особых ситуаций. Возможно, стоит придумать несколько решений и попытаться понять, где можно допустить ошибку. В условиях ограниченного времени это не так просто.
Итог
Предметное тестирование конкурса "Вклад в поколение" - это решение олимпиадных заданий на программирование. Если планируете подготовку к этому конкурсу, необходимо потратить время на олимпиадные задания.
Несмотря на то, что я не решил все задания на полный балл, это оказалось достаточно для прохождения в следующий этап. В списке победителей конкурса я увидел некоторых коллег, которые связаны с олимпиадным программированием. Этап предметного тестирования важен в данном конкурсе, поэтому не надо им пренебрегать.
Какое впечатление у Вас от заданий? С учетом трех предыдущих заданий (всего их 6), как Вам кажется, достаточно 2 часа 30 минут на их решение?