Первое информационное сообщение

Общая информация

Саратовский государственный университет со 2 по 12 августа 2010 года проводит международную летнюю студенческую школу по программированию.

К участию приглашаются как команды из трех человек, так и индивидуальные участники.

Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки.

В программе школы запланированы лекции тренерского состава Саратовского государственного университета, совместные тренировки, разборы задач и тематические семинары. Учебная программа рассчитана на студентов младших курсов, которые хотят достичь значительных успехов на соревнованиях по программированию.

Организационный сбор составляет 15000 рублей на одного участника. Кроме того, каждая команда или индивидуальный участник должны привезти с собой ноутбук (с поддержкой WI-FI).

Заинтересованным участникам и командам необходимо пройти предварительную регистрацию на сайте http://acm.sgu.ru/sazanka-2010/ до 10 июня 2010 года. Не откладывайте регистрацию, так как количество мест ограничено.

Дополнительную информацию можно получить по телефону 88452522711 или по электронной почте mirzayanovmr[символ с кодом 64]gmail.com.

Надо сказать, что участвуя в прошлом году в 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 и предпосчитать таблицу биномиальных коэффициентов.

Все видимо уже в курсе, что Codeforces Beta Round #3 не состоялся в назначенное время. Произошло это, видимо, по причине возросшей популярности с одной стороны и некоторых наших багов с другой. Конечно, жалко, что все так произошло. С другой стороны, если бы все упало во время контеста, было бы хуже. Соревнование перенесено на воскресенье (7 марта), 15:00.

Хочу напомнить, что проект находится в стадии Beta и по результатам инцидента будет проведена соответствующая работа. Но я верю, что главное из таких случаев делать правильные выводы, находить ошибки, их исправлять и двигаться вперед.

Спасибо за понимание,
MikeMirzayanov

UPD. Как стало известно, в субботу будут проходить еще два популярных контеста, по этому встретимся в воскресенье на Codeforces Beta Round #3.

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

Не так давно на Codeforces была введена система рейтинга. Для полноты картины представляю вам табель о рангах.

Отныне участникам будут присваиваться звания, которые будут отражать ваши знания, навыки и умения в таком нелегком деле как решение задач по программированию. По результатам прошедших раундов вам будет начисляться (у кого-то сниматься, но, надеюсь это не про вас) рейтинг, и при достижении определенных успехов вас ждет повышение по службе. Ниже представлена таблица, отражающая зависимость между рейтингом и званиями. Более того, званиям присвоены цвета, и это тоже отражено в таблице.

Как некоторые уже успели заметить – на сайте появился рейтинг участников соревнований. Пока он тоже находится в состоянии beta, но выглядит вполне адекватным. Вот как он считается.