После возвращения с зимней школы, у меня была пара свободных недель до начала следующего семестра в университете, и я уделил время созданию задач для своего второго матча на топкодере. На этот раз я написал 6 разных задач, но концепт обеих Easy и обеих Medium был общий, и в случае Medium-ов мне это очень нравилось.
Ответа я ждал примерно месяц. За это время сменился координатор задач на топкодере - Олексия сменил Иван Метельский. Ответил мне уже последний. Посмотрев задачи, он довольно скоро предложил мне выбрать матч - и я взял первый же неночной SRM после финала ACM.
Тестера на матч назначили в тот день, когда мы с финала вернулись, и им, к моей большой радости, оказался не кто иной, как Вася. За дело он принялся довольно скоро, а расправился с задачами ещё быстрее. Более того, он написал быстрое и красивое решение для div1 Hard, на которое я в итоге и заменил своё страшное и неповоротливое детище.
Опишу вкратце подходы к задачам:
Div2 Easy - IncredibleMachineEasy. Действительно, есть такая старая игра от компании Sierra, и когда-то я в неё играл. Было весело. Так вот, написав уравнение зависимости времени, ускорения и высот падений шариков, мы получим что-то этакое: T=sqrt(2*h1/a)+sqrt(2*h2/a)+...+sqrt(2*hN/a). Умножив обе части уравнения на sqrt(a)/T и возведя получившееся в квадрат, мы придём к формуле для ускорения: a=2*(sqrt(h1)+sqrt(h2)+...+sqrt(hN))/T]^2. Альтернативой этому подходу был перебор ускорения двоичным поиском: проверить, годно ли то или иное значение, можно подставив его в первоначальную формулу.
Div1 Easy - IncredibleMachine. Тут мы видим уже усложнённый вариант: в дело вступают наклонные плоскости. Решать задачу можно опять чисто аналитически, но в данном случае, на мой взгляд, намного легче применить двоичный поиск. Несмотря на то, что в условии даны были все формулы, кто-то всё равно посчитал его не достаточно ясным. Мне трудно судить, хотя учитывая, что большинство всё же решило задачу довольно быстро, наверное, условие всё же было понятным. Так или иначе, приносить задачи физического характера на топкодер довольно тяжело, потому что сложно описать все допущения и условия, принятые в задаче относительно классических законов физики.
Div2 Medium - MazeWanderingEasy. Задача эта возникла как дополнение к её более сложному собрату из первого дивизиона. Я на самом деле видел по Discovery программу, где подобным экспериментом показывали, как изменялись умственные способности мышей при прослушивании различной музыки. Несмотря на то, что я слушаю большей частью металл, подобная задача показалась мне весёлой (хотя кто-то воспринял условие MazeWandering как личное оскорбление :D). Что касается решения, надо было всего лишь найти путь в дереве между двумя вершинами и посчитать на нём количество вершин с decision-ами, то есть именно то, что сказано в условии.
Div1 Medium - MazeWandering. Я люблю задачи на вероятность, поэтому появление такой задачи на моём матче было лишь вопросом времени. Как только вспомню, как я её решал - сразу напишу ;)
Div2 Hard - WickedTeacher. Человеку, знакомому с динамическим программированием и решавшему задачи на битмаски, задача не должна показаться особо оригинальной. Понятно, что вероятность равна отношению [количества таких перестановок входящих фрагментов, для которых итоговое число делится на K] к [общему количеству перестановок, то есть собственно N!]. А для того, чтобы считать число в знаменателе, надо уметь считать NUM(mask,rem), то есть количество перестановок входных фрагментов, составленных из множества, определённого mask, и дающих при делении на K остаток rem. Всего аргументов у NUM может быть 2^N * K штук, что составляет примерно 3*10^6. В конечном счёте, в задаче было над чем повозиться, и решил её один-единственный участник.
Div1 Hard - SquareFreeSets. К этой задаче я видел два различных подхода. Первый, который я заметил в пяти из 7 прошедших systest решений и который описан в editorialе - перебор с запоминанием. Второй, который и использовал Вася - динамическое программирование. Положение описывается тремя параметрами: какие числа уже рассмотрены (а так как их можно рассматривать по возрастанию, то надо запоминать только наибольшее), сколько чисел взято в наше множество и маска простых чисел, которые уже использованы при составлении множества. Ясно, что маску всех простых запоминать невозможно - а достаточно запомнить маску тех простых, которые в квадрате не превосходят N. Чтобы не повторять варианты при рассмотрении чисел, делящихся на более большие простые, надо при рассмотрении простого числа, большего sqrt(N), сразу рассмотреть все кратные ему числа, и вообще исключить их из рассмотрения позднее.
Обзор матча можете посмотреть здесь. Сам я был очень доволен результатами, и матч был, на мой взгляд, очень интересный.
No comments:
Post a Comment