Надо сказать, что участвуя в прошлом году в TopCoder Open и Google Code Jam, я чувствовал себя значительно более уверенно, чем в этом. Дело в том, что последний год я совсем мало решал задач и участвовал в каких-либо контестах. Это разумеется отразилось и на результатах. Но как бы то ни было я собираюсь участвовать этих соревнованиях этого года и буду бороться до последнего (надеюсь, раунда).

Только что закончился Google Code Jam 2010 Round 1B, который я слил препозорнейшим образом, о чем сейчас и поведаю. Сразу отмечу, что задачи мне очень понравились, отличный отборочный раунд.

Результаты здесь

A. File Fix-it

Я решал эту задачу явно строя дерево директорий. Для этого я каждый путь превратил в vector<string>, разделяя его символом слэш. Вот такая функция добавляла в дерево путь d[idx]->d[idx + 1]->…->d[d.size()-1] из вершины tree дерева. Так же она увеличивает глобальный счетчик z созданных узлов.

void put(const vector& d, int idx, int tree)
{
	if (idx >= d.size())
    	return;

    if (f[tree].inner.count(d[idx]) == 0)
    {
	    z++;
    	f[tree].inner[d[idx]] = p++;
    }

    put(d, idx + 1, f[tree].inner[d[idx]]);
}

Тогда задача сводиться к добавлению в дерево всех существующих путей, а затем (после z:  = 0) добавлению тех директорий, которые надо создать. Значение z после этого (т.е. количество созданных узлов на второй фазе) будет равно ответу на задачу.

B. Picking Up Chicks

Эта задача меня подвела. В первом абзаце я как-то умудрился прочесть, что при обгоне обгоняющая курочка скидывает с беговой дорожке обгоняемую, но продолжает двигаться со скоростью второй. Не спрашивайте меня как я это прочел…

После того как я понял условие правильно, то решил задачу следующим образом. Для каждой курочки я определил добежит ли она до финиша за время t если ей никто не будет мешать. Если таких курочек меньше k, то ответ IMPOSSIBLE. Если таких курочек равно 0, то ответ 0. А вот если таких курочек больше или равно k и k положительно, то выбираем k ближайших к финишу курочек и будем именно их использовать для составления ответа. Пусть это множество A. Для каждой из этих курочек посмотрим на такие, которые находятся правее ее, но не являются выбранными. Такие курочки не успевают добежать до финиша (так как не выбраны), и поэтому в них нельзя упираться. Значит всех их надо проскочить. Таким образом, ответ это сумма для каждого a из A количества курочек впереди a, но не принадлежащих A.

C. Your Rank is Pure

Задачу я решал методом динамического программирования. Пусть z[i][j] = количеству подмножеств {2,3,…,i} которые являются хорошими (в терминах задачи) и число i в них имеет ранг j. Тогда число j тоже принадлежит подмножеству и может иметь любой ранг от 2 до j - 1. Допустим его ранг равен t. Тогда на участке от j + 1 до i - 1 (включительно) нужно выбрать любое подмножество из j - t - 1 элементов, чтобы заполнить пропуск нумерации. Получаем, такую формулу:

Разумеется, все вычисления надо производить по модулю 100003 и предпосчитать таблицу биномиальных коэффициентов.