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

Еще один баг: посылки с виртуальных контестов не отображаются на вкладке "Мои посылки".

Вопрос: планируется ли это фиксить, и если да, то когда?

UPD. Поднял тему.

UPD2. Судя по всему, баги пофикшены. Огромное спасибо :).

UPD3. Оказывается, баг с "Моими посылками" пофикшен только в тренировках, на обычных контестах он остался.

UPD4. Поднял тему еще раз.

У меня одного возникает идея, что раз Гена перешагнул 3000-очковый барьер, то стоит ввести новое звание? Как отличительный признак предлагаю золотистый "ореол" вокруг никнейма (хотя я точно не знаю, как такое отрендерить, чтобы при этом еще не было проблем с масштабированием).

Вопрос к финалистам: можно ли на финале выводить лишние пробелы в конце строки? Примерно так:

for (int i = 0; i < n; i++) {
    out.println(arr[i] + " ");
}

Предисловие

Пишу с надеждой, что есть те, кто этот алгоритм не знают, но он им может пригодиться :). В-общем, утром 16 июня я открыл задачи с NEERC 2010 и остановился на C-шке (Cactus Revolution), в которой нужно было разрезать кактус так, чтобы у нас получилось сколько-то равных связных частей, или сказать, что это сделать невозможно. Мне быстро пришла в голову идея, что нужно этот кактус как-то подвесить на манер дерева, и после этого решать задачу по аналогии с задачей о разрезании дерева. Вначале были идеи о конденсации простых циклов, введении псевдовершин и т.п. Но вскоре пришла та самая идея, о которой я и хочу рассказать в этом топике.

Идея

Мысленно выполним "раздваивание" всех мостов, вот что получится с графом из примера:

Теперь каждая вершина лежит на цикле. Заметим, что любые два цикла имеют максимум одну общую вершину (доказывается через определение кактуса). Мысленно сожмем все циклы в одну вершину и проведем ребра между смежными циклами. В этом графе могут быть циклы, но при этом все они являются частью какой-то клики. Теперь мы можем мысленно выполнить DFS по этому графу, и при попадании в вершину клики, разомкнуть эту клику, удалив все ее ребра кроме ведущих в вершину, в которую мы зашли первой. Теперь у нас получилось дерево. Мысленно подвесим это дерево за ту же вершину, через которую мы выполняли первый DFS и получим между смежными циклами отношение "предок-потомок". Но как мы будем это все хранить? А очень просто: разомкнем каждый цикл путем выкидывания из него вершины, входящей кроме этого цикла также и в его предок, а в список потомков этой вершины добавим массив, содержащий разомкнутый цикл. Вот изображение той структуры, которую мы получим в конечном итоге, если подвесим кактус из примера за вершину 1 (извиняюсь за качество — рисовал в MSPaint'е):

Реализация (на Java)

На практике все можно реализовать при помощи одного DFS'а, без предварительного сжатия циклов, построения графа их смежности и т.п. Алгоритм в целом такой: мы ищем мосты и циклы. Когда мы находим цикл, мы записываем по порядку все его вершины (кроме одной — той, которая будет как бы его корнем) в массив и добавляем этот массив в список потомков этого самого "как бы корня". С мостами же очевидно, что они ни на каких циклах не лежат, поэтому после спуска по мосту (v, e) из вершины v мы просто добавляем массив из одной вершины e в список потомков v.

int n;
ArrayList<Integer>[] graph;
ArrayList<int[]>[] cactus;

int[] stack;
int cnt = 0;
int[] color;

int[] tin;
int[] tchild;
int curtime = 0;

void hang(int v, int prev) {
	color[v] = 1;
	tin[v] = tchild[v] = curtime++;
	stack[cnt++] = v;
	for (int e : graph[v]) {
		if (color[e] == 1 && e != prev) {
			tchild[v] = min(tchild[v], tin[e]);
			int start = cnt - 1;
			while (stack[start - 1] != e) {
				start--;
			}
			int[] cycle = new int[cnt - start];
			for (int i = 0; i < cycle.length; i++) {
				cycle[i] = stack[start + i];
			}
			cactus[e].add(cycle);
		} else if (color[e] == 0) {
			hang(e, v);
			tchild[v] = min(tchild[v], tchild[e]);
			if (tchild[e] > tin[v]) {
				cactus[v].add(new int[] { e });
			}
		}
	}
	cnt--;
	color[v] = 2;
}

void solve() throws Exception {
	/*
	 * Инициализируем массивы, считываем граф и т.п.
	 */
	
	hang(0, -1);
	
	/*
	 * Решаем задачу
	 */
}

Послесловие

Мне было бы интересно узнать две вещи:
1. Боян или нет?
2. Как решала задачу, ради которой я придумал этот алгоритм, команда ИТМО 2?

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

UPD3. Вопрос: кто минусуют пост и при этом никак его не комментируют? Те, для кого это уже боян или те, кто ничего не поняли?

1. Задача: даны два множества точек на плоскости (оба размером N), нужно найти совершенное паросочетание с минимальным весом самого тяжелого ребра в нем (вес ребра — очевидно, Евклидово расстояние). Я умею решать Куном с бинпоиском по весу самого тяжелого ребра за O(N³ logN). Вопрос: как решить эту задачу за чистый куб путем добавления в алгоритм какой-то жадности? Хопкрофта-Карпа и Диница прошу не предлагать. Ответ: вот так.

2. Задача о поиске совершенного паросочетания в регулярном двудольном графе объяснялась в харьковской ЗКШ в этом году, но только для тех графов, в которых степени каждой вершины являются степенями двойки. Вопрос: как решать эту задачу для графов с произвольными степенями вершин? Применение алгоритма Хопкрофта-Карпа очевидно, но мне кажется, что существует что-то побыстрее.

3. Задача: дан регулярный граф, нужно найти в нем гамильтонов цикл. Вопрос: существует ли алгоритм, который гарантированно найдет этот гамильтонов цикл за полиномиальное время, если он имеется?

4. Эта задача с Тимуса имеет очевидное решение через паросочетание. Вопрос: можно ли обойтись без паросочетания и решить задачу жадно? Ответ: да, можно, а я тупой идиот, потому что думал как раз о таком решении, но не удосужился проверить 3 случая.

Решение этой задачи с помощью Heavy-Light декомпозиции очевидно. Но в обсуждении поминали какое-то решение за O(N * sqrt(N)) с помощью кластеризации. Можете кто-нибудь объяснить поподробнее?

Во время решения задачи С со 119 раунда я столкнулся с невозможностью запихать в ТЛ решение на Java, де-факто аналогичное авторскому: бинпоиск + БФС с СНМом. В чем причина столь маленького ТЛа? Команда Codeforces не переписала авторское решение на Java? Или я не прав? В любом случае, я считаю, что это ненормально, когда на жабе заходит решение только у 14 человек (включая дорешивание).

P.S. Решение через построение "диаграммы Вороного" и последующий запуск алгоритма Крускала у меня зашло за 840мс.

UPD. Под выражением "построение "диаграммы Вороного"" я подразумевал разбиение вершин на множества в соответствии с тем, какой из волонтеров (или точка назначения) находится ближе всех, делал я это БФСом. Можно сказать, что я неявно построил граф с этими множествами в качестве вершин, и объединял их до тех пор, пока s и t не окажутся в одном множестве (как в алгоритме Крускала).

http://codeforces.com/contest/185/submission/1656438 — что это такое?! Погрешность идет в восьмом знаке. Почему в чекере проверка на <= выполняется без эпсилона?

Мое решение с использованием двух указателей и бинпоиска, вложенного в тернарник, занимает 343 строчки. Можно ли как-то решить задачу проще (может быть, с намного худшей асимптотикой)? Все, что описано в обсуждении, я прочитал, интересно услышать другие идеи.

Собственно, сабж. Достаточно ли знать КТО, изоморфизмы аддитивных и мультипликативных групп по модулю, лемму Бёрнсайда, теорему Пойа и еще парочку тем, или нужно учить теорию групп основательно? Если нужно, то буду рад услышать совет по поводу литературы (с английским проблем не имею :) ).

Собственно, расскажу о своей проблеме. SSP мне попалась в задаче J с финала ACM 2011 года. Я написал динамику по аналогии с рюкзаком за O(n) памяти и O(n * k) = O(n ^ (4/3)) времени (n - максимальное число, которое нужно разложить на слагаемые, k - количество элементов во множестве). Каким образом можно улучшить асимптотику? Можно ли как-то использовать две следующих вещи: а) множество состоит из квадратно-пирамидальных чисел, б) для разложения произвольного числа из промежутка [1; 1000000] требуется в худшем случае 6 чисел?

UPD. Буду особенно рад услышать финалистов :).

UPD2. От NEERC'а в прошлом году в финал вышли 13 команд, если не ошибаюсь, все они J решили. Почему такая гробовая тишина?

UPD3. По комментарию Артема я понял, что мое решение на финале бы прошло. Теперь буду рад услышать тех, кто загнали задачу на испанском сервере в ТЛ 3 секунды.

UPD4. Судя по топ20 решивших задачу на livearchive, наличие кого-то из русскоговорящих среди оставшихся 13 маловероятно. Придется загонять самому и/или с сокомандниками. Хотя если у кого-то есть идеи - буду очень благодарен, если этот человек ими поделится.

UPD5. Идея решения у меня появилась, скоро реализую, загоню, докажу асимптотику и отпишусь.

UPD6. Идея неверна, да и пытаться загнать такое решение на медленный сервер - дело бесполезное.

UPD7. Переписал динамику по вот этому разбору со следующими изменениями: а) искал не максимальную пирамидку, с которой возможен переход, а минимальную (максимальную находил при восстановлении ответа), б) отсек диапазон пирамидок, меньших n / count, где count - количество пирамидок в наборе. Решение зашло за 1 секунду. Вот код, спасибо Jokser'у за идею насчет минимальной пирамидки.

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

Собственно, данный пост ориентирован больше на новичков (большинство профессионалов с проблемой уже знакомы). Как известно, многие из тех, кто пишут quicksort вручную, попадались на anti-quicksort, и их решения получали TLE или, еще хуже, Stack Overflow. Явакодеров, казалось бы, эта проблема не касается: они пользуются стандартной функцией, которая, по идее, должна быть написана корректно. Не тут-то было... Короче, прилагаю исходник (лицензия GNU GPL 2 with Classpath exception, т.к. основан на исходном коде из OpenJDK). Запускать следует с параметром -Xss64m; сгенерированный массив выведется в файл.

Я отправлял решения выбором файла и кнопкой "отослать". Когда просмотрел свои отправки - в начале исходного кода показывается какой-то непонятный символ. В чем причина?