Квалификационный раунд Google Code Jam начался сегодня в 5 утра по пермскому времени и идет 24 часа. Если вдруг кто-нибудь забыл о нем, то у вас еще есть время поучаствовать
( Read more... )
Большой и красивый едиториал, какие ты пишешь, я конечно не осилю. А так, нормальные задачки для отсеивания непрограммистов :)
В первой - простая динамика за O(S*Q), немного усложненная работой со строками.
Во второй - жадный алгоритм. Идея попроще чем в первой, но реализация сложнее. Решить можно было по-разному: я добавлял поезда по одному, удаляя использованные временные отрезки, пока все не будут удалены; другие решения шли по возрастанию времени, и добавляли новые поезда по мере необходимости.
Третью задачу почему-то многие поленились решать, назвав её гемором, и уйдя работать :) Хотя ничего сложного в ней не было. Во-первых, надо было заметить, что можно уменьшить размер мухи до точки, увеличив t на f, и сдвинув стороны всех квадратов gxg внутрь на расстояние f. Во-вторых, заметить, что проще посчитать площадь области, где муху не прибьют, и вычесть ее из общей площади. Для этого перебираем все квадраты и суммируем площади их пересечения с кругом радиуса R-t-f. Площадь пересечения квадрата и круга можно найти, рассматривая отдельно все вертикальные полоски между "интересными" x-ами, и используя формулу для интеграла от дуги окружности.
Я за выживание мухи :)andrey_stepenkoJuly 19 2008, 07:55:30 UTC
Не участвовал но задачка с мухой понравилось. И уменьшить муху тоже супер! Только не понятно какая связь между "увеличив t на f" и возможностью считать муху точкой?
Re: Я за выживание мухи :)renatmJuly 19 2008, 09:46:57 UTC
Центр мухи не может подлететь на ближе чем на f к окружности радиусом R-t и к сторонам квадратов со стороной g. То есть если мы уменьшим квадраты до размера g-2*f а окружность до R-t-f то можем считать что муха - это только ее центр.
Re: Я за выживание мухи :)andrey_stepenkoJuly 19 2008, 12:13:16 UTC
Браво! И мои поздравления. Мысль о том, что вероятность попасть в муху-точку линией с нулевой толщиной тормозит видение ответа. :) Во как стереотипы порабощают.
Видимо Гугл получил все тайные технологии министерства обороны для отсева ненужных кандидатов. Стараются.
В первой - простая динамика за O(S*Q), немного усложненная работой со строками.
Во второй - жадный алгоритм. Идея попроще чем в первой, но реализация сложнее. Решить можно было по-разному: я добавлял поезда по одному, удаляя использованные временные отрезки, пока все не будут удалены; другие решения шли по возрастанию времени, и добавляли новые поезда по мере необходимости.
Третью задачу почему-то многие поленились решать, назвав её гемором, и уйдя работать :) Хотя ничего сложного в ней не было. Во-первых, надо было заметить, что можно уменьшить размер мухи до точки, увеличив t на f, и сдвинув стороны всех квадратов gxg внутрь на расстояние f. Во-вторых, заметить, что проще посчитать площадь области, где муху не прибьют, и вычесть ее из общей площади. Для этого перебираем все квадраты и суммируем площади их пересечения с кругом радиуса R-t-f. Площадь пересечения квадрата и круга можно найти, рассматривая отдельно все вертикальные полоски между "интересными" x-ами, и используя формулу для интеграла от дуги окружности.
Reply
Reply
Reply
Мысль о том, что вероятность попасть в муху-точку линией с нулевой толщиной тормозит видение ответа. :) Во как стереотипы порабощают.
Видимо Гугл получил все тайные технологии министерства обороны для отсева ненужных кандидатов. Стараются.
Reply
Leave a comment