Мы сейчас решаем этот вопрос. Дело в том, что уже забронированы номера в гостинице и есть договоренность об аренде помещений IT-парка. Соответственно, критичным является количество команд, которым более удобно 6-7 апреля (или 13-14) вместо 16-17 марта.

.

Если вы пройдете в основной тур, то удобнее будет, если данные будут у всех участников. Пока можно оставить в том виде, как есть.

Да, можно, если только не наберется два десятка таких желающих =)

.

http://www.icl.ru/turnir/foreign.php

Из текста следует, что самим нужно платить за проезд. Все остальное бесплатно.

Это менее вероятно. Посмотрим.

OK

Разумеется. Вообще, плотность контестов сейчас довольно высока. Какой день ни выбери — будет пересечение с кем-то.

Судя по тому, что осталось меньше минуты, вряд ли :)

Я вот думаю: а нельзяя было провести контест на базе КФ. Тогда таких проблем не было бы.

Мы начнем, не?

.

Раньше отбор был не 5-часовой контест. Хотя в целом было схоже.

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

Мне кажется, они сделали что-то неправильно=) В любом случае, они уже вряд ли смогут что-то изменить или исправить, поскольку кто-то мог и успеть достать задачи. Ну, мне так кажется. Так что я сейчас смотрю на происходящее с лёгкой истерической улыбкой :)

But

К сожалению, Google Chrome не может открыть страницу www.icl.ru.

Судя по тому, что периодически страница доступна, но нету доступа к базе, они сейчас панически пытаются восстановить работоспособность системы. Видимо не до ответов=)

А кто-то смог дойти до этапа скачивания условий =)

Я сумел открыть 2 задачи. Условия вот сюда пока выложил: https://docs.google.com/document/d/1Jx2OfFXTXJI01IMVs__sZHAI6Js94MLi9hZF7UrkJlE/edit

Нияз неужели ты думаешь, что вы можете не пройти?)))))

Предпочтение отдается первому отбору.

Вообще, возможны запутанные ситуации. Будем разрешать на месте.

В двух словах: ставим другое железо, проводим на нашей платформе, но чтобы гарантировать нормальную работу — делаем зеркало. Где — решается.

Да. Если у команд из прочих зачетов будут низкие результаты, то квота может быть расширена.

Исправил =)

Да данный вопрос тоже очень интересует нашу команду

Можно писать и там, и там.

Позже будет построена сводная таблица

Как насчет icl.ru?

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

Возможно потому, что речь идет именно о конечных строках, и потому циклов в автомате не должно возникать.

Ну видимо имелось ввиду, что фраза "и возможно другие конечные строки" подразумевалась как то, что бесконечные принимать нельзя, иначе непонятно к чему слово конечные. Но вообще условие конечно, не очень аккуратно сформулировано.

Задача J. Ищешь хэши всех подстрок строки-образца. По ним строишь декартово дерево (так надо). А по самим строкам суффиксный автомат. Не забудь про Ахо-Корасика. А в конце выводишь: длина строки-образца делить на длину любой строки из словаря.

В B раскладываем N в p-ричную систему счисления, получаем массив циферек a_i, далее для каждого числа a_i считаем количество способов разложить a_i по k корзинам, полученные результаты перемножаем и выводим в ответ. Чтобы вписаться в TL предварительно подсчитываем все факториалы и их минус первые степени до p+k включительно

Изначально в ответе есть все ребра. Сделаем топологическую сортировку вершин. Потом добавим в граф ребра, обратные данным, и запустим обход в глубину из вершин в порядке возрастания времени выхода. Если встретили ребро, которое ведет в вершину, в которой мы есть (от которой рекурсивно работает dfs в данный момент) — убираем обратное ему из ответа.

Исправьте, если неправ, потому что мы D так и не отдебажили. И, уверен, должна быть оптимизация этого алгоритма.

Мы довольно долго думали над ней, в итоге забили и впихнули тупое решение за O(nm) (с оптимизацией при помощи bitset'ов: для каждой вершины храним bitset "из кого она достижима", пересчитываем за bitwise or, проверяем (обратное) ребро за обращение к битсету).

Интересно было бы узнать, есть ли у авторов нормальное решение (асимптотически быстрее O(nm)), или предполагалось именно запихивать тупняк?

Пусть после топологической сортировки все рёбра идут слева направо.

Будем добавлять вершины справа налево. Когда мы добавляем какую-то вершину, множества достижимости всех уже добавленных поменяться не могут, так что нужно только следить за тем, чтобы множество достижимости этой новой вершины сохранилось после выбрасывания ненужных рёбер.

Посмотрим на исходящие из нашей вершины рёбра в порядке, заданном топологической сортировкой: чем левее в отсортированном массиве вершин конец ребра, тем раньше мы его изучим. Если конец ребра и так достижим из нашей вершины, то такое ребро можно выкинуть. А иначе его придётся добавить, обновив при этом множество достижимости.

Это жадное решение за NM / 32.

Я не знаю, как решать, но гуглится http://www.se16.info/js/cuboid.htm и там параграф про "Points of greatest surface distance from a corner"

Мы сдали следующее решение: понятно, что искомая точка будет принадлежать одной из граней, которая не содержит нашу вершину. Переберем каждую из таких граней, и запустим два вложенных тернарных поиска по прямоугольнику, задающему грань. Функция расстояния до заданной точки из вершины пишется несложно — это минимум из четырех формул (прямо сейчас их не выпишу, мы писали контест на зимней школе и это было неделю назад).

Перебираем грань, на которой будет лежать искомая точка. Пусть параллелепипед ABCDA'B'C'D'. Мы в A. Смотрим на грань A'B'C'D'. Легко доказать, что искомая точка будет лежать на бисектриссе угла B'С'D'. Обозначим расстояние от искомой точки до точки C' за sqrt(2)*x. Из того, что если точка не на ребрах параллелепипеда, то до нее можно дойти как минимум 3-мя способами кратчайшим образом, можно вычислить x.

Код на AC:

ld a, b, c;

ld calc2(ld x) {
	if (x > a || x > b || x < 0) {
		return 0;
	}
	ld res = min(
		min(
			sqr(c + a - x) + sqr(b - x),
			sqr(c + b - x) + sqr(a - x)
		),
		sqr(a + b - x) + sqr(c + x)
	);
	return res;
}

ld calc1(ld A, ld B, ld C) {
	a = A;
	b = B;
	c = C;
	ld res = calc2(0);
	res = max(res, calc2(a * (c - b) / c / 2));
	res = max(res, calc2(b * (c - a) / c / 2));
	return res;
}

int main() {
	ld A, B, C;
	cin >> A >> B >> C;
	ld ans1 = calc1(A, B, C);
	ld ans2 = calc1(B, C, A);
	ld ans3 = calc1(C, A, B);
	ld ans = max(max(ans1, ans2), ans3);
	printf("%0.20lf\n", (double)sqrtl(ans));
	return 0;
}

Зафиксируем динамику за куб. d[i][j] — покрыть первые i чисел. Пересчитывать dp[i][j] = min(dp[t][j-1] + calc(t,i)). calc — это что-то с префиксными суммами, считающее ответ для одного отрезка.

Посмотрим на t внимательнее. Пусть t[i][j] — оптимальное t для dp[i][j].
Тогда t[i - 1][j]  ≤  t[i][j]  ≤  t[i][j + 1]. Будем считать по возрастанию i, убыванию k, с использованием этого отсечения. Это квадрат, потому что если все просуммировать, то останутся только правые границы когда либо i = n, либо j = k; Таких состояний линия, каждая из правых границ тоже не больше N.

PS. Эту задачу много где давал Burunduk1. Я удивлен, что ее так мало сдали.

Присоединяюсь к вопросу :(

Ну можно было написать что высота маленькая где-нибудь в более заметном месте. Есть те, кто это не заметил?

Всего в див1 88 АС:
ФФТ — 19
Декартово дерево — 69
Никого, кто бы выводил оба ответа, не обнаружено.
По див2 полных данных нет, поскольку сливались борды.

Почему результаты тут и здесь не совпадают. Был rejudge?

Можно ли на основании этих результатов судить о том, отобралась ли наша команда на онсайт (7-е место)? Или же стоит ждать какого-то официального оглашения результатов со списком приглашённых команд?

Хотелось бы заранее побеспокоиться о билетах в случае успешного отбора.

У меня такой вопрос.

Наша команда (Moscow SU Hamsters) во время контеста в таблице отображалась адекватно, а после контеста остался только логин — moscow59. Соответственно, в листе ожидания у нас тоже записан только логин.

Можете исправить это, пожалуйста?

Суффиксным автоматом, убирая фазу "клонирования" вершины, которая как раз нужна для того, чтобы автомат не принимал лишнее.