Google Code Jam

Давно я что-то ничего не писал. Начну пожалуй, для разминки, с GCJ :)

Задача 1. Saving the Universe

Краткое условие

Дан список поисковых систем S (все названия различны, до 100 элементовв) и список запросов Q (каждый запрос – строка из S, до 1000 элементов). Необходимо распределить запросы по системам так, чтобы ни один запрос не совпал с названием системы, которой он будет обработан. При этом запросы должны выполняться в заданном порядке и количество смен поисковых систем должно быть минимизированно (смена системы происходит, когда система, обрабатывающая i-й запрос не совпадает с системой, обрабатывающей j-й запрос).

Решение

Шаг первый, очевидный. Превратим все в числа, то есть i-й элемент Q будет номером строки из S.

Шаг второй. Подумаем: раунд квалификационный, следовательно задачи легкие, для отсевки «ботов», эта задача первая, значит с вероятностью 99% она решается первым пришедшим в голову жадным алгоритмом – на каждом шагу брать ту систему, которая сможет обработать наибольшее количество запросов.

Шаг третий. Поленимся (или не сможем) доказать жадное решение и начнем писать обычную динамику: d[i,j] – минимальное количество смен систем, если обработано i запросов и последняя система была j. Очевидно, что d[i,j] не имеет смысла (то есть равно -1), если Q[i] = S[j]. Далее:

  • начальное условие: d[0,j] для всех j таких, что Q[0] != S[j] равно 0;
  • рекуррентное соотношение: d[i,j] = min(d[i - 1, k] + (k != j)) для всех i, j, k таких, что Q[i] != S[j] и Q[i - 1] != S[k]

Шаг четвертый. Отправляем решение, радуемся тому, что оно пройдет с вероятностью 100% и переходим к следующей задаче.

Шаг пятый. После контеста обсуждаем решение с другими участниками и понимаем, что ступили на третьем шаге :(

Шаг шестой. Понимаем, что для данных ограничений написанная динамика и ненаписанная жадность занимают примерно одинаковое количество кода, но за жадность придется заплатить либо временем на доказательство, либо адреналином после отправки решения. А раз результат одинаков, то зачем платить больше? :)

Задача 2. Train Timetable

Краткое условие

Есть две железнодорожные станции: A и B. Также имеется расписание поездов на сутки: какой поезд, с какой станции, на какую станцию, когда отправляется и когда прибывает. Нужно посчитать, сколько минимум поездов должно ездить между этими станциями, если на разворот поезд затрачивает время T.

Решение

Шаг первый. Подумаем: раунд квалификационный, следовательно…

Шаг второй. Придумаем несколько интуитивно понятных фактов в пользу жадного решения и напишем его:

  1. сложим все времена отправки в одно место;
  2. возьмем поезд, отправляющийся раньше всех (если несколько, то возьмем любой);
  3. прибавим единицу к результату, отправим поезд, уберем время отправки из общей кучи и развернем поезд;
  4. посмотрим, куда его еще можно отправить, и, желательно, пораньше;
  5. пока это возможно повторяем с пункта 3;
  6. как только текущий поезд не может никуда поехать, возвращаемся к пункту 2, если еще остались неиспользованные элементы расписания.

GCJ 2008 QR Task 2

Задача 3. Fly Swatter

Краткое условие

Это история о теннисной ракете и мухе… Кто-то хочет попасть первой по второй. Но есть проблема: бьющая поверхность ракетки сетчатая. Лень описывать геометрические параметры – лучше посмотреть рисунок, и все станет ясно :) Муха представляет собой сферу радиусом f. Надо посчитать вероятность того, что муха все-таки встретится с ракеткой, если она движется перпендикулярно ракетке и ее (мухи) центр всегда попадает в окружность ракетки.

Решение

Решение очевидно: посчитаем площадь геометрического места точек, где должен быть центр мухи, чтобы ненулевая ее площадь соприкоснулась с ракеткой и разделим на площадь ракетки. Проблема лишь в определении того самого геометрического места и в вычислении его площади. Пойдем от обратного: определим геометрическое место точек, где должен быть центр мухи, чтобы он пролетела через ракетку. Им будут исходные дырки со сдвинутыми внутрь на f границами. Вычислить площадь полных дырок труда не составляет. Для дырок, пересекающихся с границей ракетки все немного сложнее. Можно поступить так:

  1. рассматриваем только первую четверть (правую верхнюю) ракетки;
  2. возьмем дырку и найдем все различные точки пересечения ее сторон с окружностью ракетки;
  3. если таких точек не две, то дырка полная;
  4. пусть таких точек ровно две: (x1,y1), (x2,y2). Пусть (x0,y0) – левый нижний угол дырки, x3 = min(x1,x2), y3 = min(y1,y2) тогда площадь дырки S = (g – 2f) ^ 2 – (g – 2f – (x3 – x0)) * (g – 2f – (y3 – y0)) + S1(x0,y0,x1,y1,x2,y2), где S1 – площадь части круга, ограниченного заданными точками. S1 можно посчитать следующим образом: S1(x0,y0,x1,y1,x2,y2) = S2(x1,y1,x2,y2,R – t – f) – S3(0,0,x0,y0,x1,y1) – S3(0,0,x0,y0,x2,y2), где S2 – площадь сектора круга, S3 – площадь треугольника.
    Google Code Jam Task 2
  5. в конце не забываем все умножить на 4 – это сбережет много нервных клеток :)

Далее, надеюсь, все понятно – ушел слушать Radio-T.