Отбор для CWC — это в большей степени пробный тур для знакомства с движком, чем отсев. Но участников во всех турнирах суммарно очень много, поэтому жюри вынуждено формально ограничивать число финалистов и для CWC. Тем не менее, вангую, что мест хватит всем, кто зарегистрируется и сделает на отборе хоть что-то :)

По поводу движка и изменений в игрушке напишет один из авторов.

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

Сейчас тестирующая система с задачами прошлого года недоступна. Но ничего выдающегося в отборочных задачах нет — как правило, это 2-3 простые задачи + 2-3 задачи посложнее (часто из наших же контестов давних и не очень лет) из расчёта на решение большинства из них участником среднего уровня в течение 2-х дней.

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

Кстати, в этом году отбор и финал командного турнира впервые пройдут на Yandex.Contest, но все личные турниры пока останутся на собственной системе тестирования.

надо писать после контеста,например сейчас.

Если ты про командную, то вот наше:

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

Тогда сначала найдём lca всех путей. Теперь надо для каждого пути посчитать, сколько же lca лежит на его пути (как это сделать опишу в конце). Из этого числа надо вычесть единицу, чтобы не считать свой собственный lca. Это и будет количество путей, пересекающих текущий.

Теперь мы могли посчитать какие-то пути дважды. Это происходит в случае, если lca двух путей совпадают. Тогда пройдёмся по всем вершинам, пускай количество путей, у которых lca находится в текущей вершине — это count, тогда вычтем из общего количества пересечений величину count * (count - 1) / 2. Всё, осталось вычесть из общего количества путей найденное число и получим ответ, то есть answer = PATHS * (PATHS - 1) / 2 - intersections.

Для того, чтобы считать количество вершин на пути, можно использовать такую структуру данных, как Heavy-Light Decomposition, которая позволяет узнавать сумму на пути в дереве за log(TREE_SIZE). В нашей HLD значением в вершине будет количество путей, у которых lca находится в ней. Внутри HLD мы использовали дерево фенвика, так как все необходимые операции для создания HLD и запросов на ней — это добавление в элементе и запрос на отрезке. Также с помощью HLD можно находить lca, так что не придётся строить никаких дополнительных структур для этого.

Итоговая сложность решения O(TREE_SIZE + PATHS * log(TREE_SIZE)). При этом, наше решение на яве отработало дольше, чем за 0.8 секунд, тогда как ограничение по времени было в 1 секунду, так что писать нужно аккуратно, иначе можно запросто влететь по времени.

P.S.: Хотелось бы призвать сюда Артёма temich Носова, может у него есть более интересное решение.

P.S.2: Код.

Код После того, как нашли lca всех путей, за один dfs-проход для каждого lca в текущей вершине добавляем к ответу все пути, lca которых уже встречалось, но ни один из двух концов пути не лежит в текущем поддереве. Собственно, в коде функция solve это и делает, а возвращает set встреченных концов путей. Вроде, это n * log²(n), но заходит за 307 ms.

E можно решить банальным перебором от числа N включительно. Если в нашем числе меньше разрядов чем d*2, то делаем число 1 и d-1 нулей (пример N=228,d=4, то начинаем перебор с числа 1000).сам перебор делаем так: считаем сколько разрядов у текущего числа и потом делаем такой for(INT mid=d;mid>=sz-d;++i). То есть мы разбиваем текущее число на 2, левое число — от 1 разряда до sz-mid, второе с mid до sz. Во втором числе главное проверить, что первый разряд у него не 0. После нахождения этих чисел проверяем их на простоту. Если они оба простые, значит мы нашли ответ. При проверке на простоту главное не забыть, что 1 не простое число и при нахождении двух чисел в форе нужно использовать операции / и %.

Задачи несколько разбросаны по Банку задач, но найти их там и дорешать можно :) A201, 159, 176, 177, A173, A185, SFU_2012_C, FAVT_2011_D

Seryi ,а как можно посмотреть задачи юниоров и порешать их ? Они тоже в банке задач ?

Посчитаем количество вхождений cnt[i] каждого из символов в строке. Пройдёмся по всем парам <i, j> символов алфавита и прибавим к ответу abs(i — j) * cnt[i] * cnt[j]. В конце умножим на N и разделим на 2, чтобы учесть все сдвиги и повторы. Это верно, потому что позиции символов значения не имеют — все циклические сдвиги всё равно пересекают все символы. Код по ссылке.

На сайте уже есть: http://www.contestsfedu.org/