Shtrix's blog

By Shtrix, 8 years ago, , Замечательные впечатления оставил следующий эксперемент. Одно и тоже решение задачи С использующее priority_queue было сдано на двух компиляторах.

Итог:

Visual Studio 2005: TL 101 (как и на контесте)
GCC 4.6+: AC, 1090ms

Посылки:
442400
442399 By Shtrix, 8 years ago, , Недавно занялся изучением питона и уперся в проблему с переполнением стека.

Случай нулевой, достигается придел рекурсивных вызовов:
import sys
def rec(x):
print x,
if x < 1000:
rec(x + 1)
rec(0)

Случай первый, переполнения стека не наблюдается, полет в норме:
import sys
sys.setrecursionlimit(2000000)
def rec(x):
print x,
if x < 1000:
rec(x + 1)
rec(0)

Случай второй, достигается переполнение стека:
import sys
sys.setrecursionlimit(2000000)
def rec(x):
print x,
if x < 10000:
rec(x + 1)
rec(0)

После долгого поиска я так и не нашел никаких способов увеличения стека. Жизнь с максимумом в 10 тысяч рекурсивных вызвов меня сильно удручает. Соответственно, вопрос, кто-нибудь знает какие-то хаки для глубокой рекурсии в питоне? By Shtrix, 9 years ago, , Для решения этой задачи, в первую очередь нам потребуется двоичное дерево. Естественно все его узлы хранить не удастся, соответственно прибегнем к помощи мапа/хешмапа или же пропишем свое дерево. Пускай мы для каждого поддерева храним текущее количество заряда в нем. Это несложно делается за O(H) проходом от заданной вершины к корню дерева.

Как же найти теперь математическое ожидание?
Рассмотрим корень дерева. Пускай L - заряд левого поддерева + заряд корня, а R - заряд правого поддерева + заряд корня.  Если L == R то очевидно, что в любом случае потенциал дерева равен L (Вне зависимости от того куда путь распада пойдет). Не теряя общности допустим L < R. Тогда если путь распада пойдет в левое поддерево то потенциал дерева будет равен R. То есть с вероятностью 0.5 потенциал равен R. В другом же случае нам необходимо перейти в правое поддерево и помнить, что вероятность того что мы туда попадем уже сама по себе 0.5, а также что на предыдущем шагу мы уже оставили одну из компонент связности. Такое рассуждение необходимо применять рекурсивно, волоча за собой в рекурсии: максимальный заряд уже встретившейся компоненты связности и вероятность попадания в вершину.
В кратком псевдокоде это выглядит так:

f(curVertex, maxWas, curProbability)
{
if (curVertex is leaf) result += maxWas * curProbability;
if (L == R) result += curProbability * L;
if (L < R)
{
result += curProbability* 0.5 * R;
f(curVertex->right, max(maxWas, L), curProbability * 0.5);
}
if (L > R)
{
result += curProbability* 0.5 * L;
f(curVertex->left, max(maxWas, R), curProbability * 0.5);
}
}
Таким образом, вызовом функции
f(root, 0, 1.0)
за время O(H) находится математическое ожидание потенциала.

Итоговая сложность алгоритма O(HQ) Tutorial of Codeforces Beta Round #62 By Shtrix, 9 years ago, , В довесок добавлю от себя "Где это можно сдать?":
Robotic Sort на Spoj.pl By Shtrix, 9 years ago, , А)          Необходимо было отсортировать все дома по возрастанию координаты центра х. Для каждой пары последовательных домов (x_i, a_i) и (x_(i+1), a_(i+1)) определить расстояние между домами:
d = x_(i + 1) - x_i + a_(i+1) / 2 + a_i / 2;
если d > T то ans = ans + 2
если d == T то ans = ans + 1
иначе ничего не делаем
в конце к ответу нужно было добавить два, чтобы еще закрыть крайние позиции.

B)            Для простоты написания, нужно было заметить, что геометрическое место точек которые можно выжечь лазером это два прямоугольника. Оставалось только посчитать их суммарную площадь, что делается очень просто по формуле включения-исключения. И не забудьте про 64 битное целое!

С)             Еще раз извиняюсь за ошибку в описании входа. Прочитав немного материала по теории игр и числам Шпрага Гранди вам станет очевидно, что для решения этой задачи достаточно проксорить все числа: x_1, x_1 + 1, ... x_1+m_1-1, x_2, x_2 + 1, .. x_2+m_2 ... x_n, x_n + 1, ... x_n + m_n - 1 и определить является ли результат нулем или нет. Что правда учитывая их количество вам не удастся вложится в ТЛ. По-этому заметим что Вам требуется проксорить не просто какие-то числа, а несколько отрезков вида [x_i, x_i + m_i - 1]. Пускай f([a,b]) = a^(a+1)^(a+2)..^(b - 1) ^ b.
Так как f([x_i, x_i + m_i - 1]) = f([1, x_i + m_i - 1]) ^ f([1, x_i  - 1]); можно ксорить отрезок за О(1), учитывая то что f([1,x]) можно считать так:
if (x mod 4 == 0) f(x) = x;
if (x mod 4 == 1) f(x) = 1;
if (x mod 4 == 2) f(x) = x + 1;
if (x mod 4 == 3) f(x) = 0;
тогда имеем сложность решения О(N)

D)              Решать ее стоило так:
1. Перебрать все левые верхние углы прямоугольников годных для размещения города и для каждого из них посчитать количество земли которую бы было необходимо вывезти для того, чтобы построить город. Для этого нам необходимо считать сумму на прямоугольнике и минимум. Первое делается частичными суммами, а второе на выбор либо двумерным деревом отрезков, либо для этого можно приспособить очередь с минимумом за О(1) (вместо нее также подойдет эмуляция ее с помощью STL-евских multiset и priority_queue).
2. После первого этапа необходимо собрать все данные в массив в форме (<количество вывезенной земли,  координата верхнего угла>) и отсортировать его в лексикографическом порядке (по увеличению количества земли).
3. Пройтись по уже отсортированному массиву проверяя можно ли поставить в данной клетке левый верхний угол города. Для этого нужно оценить не накладывается ли он на уже поставленный. Это можно делать заведя массив булеанов used[][] в котором будут отмечаться уже покрытые клетки. При добавлении города нужно будет просто оббегать весь прямоугольник и проставлять в его клетках true, а при запросе на возможность покрытия будем смотреть только на угловые клетки. (Так "халтурить" можно потому что у нас все прямоугольники одинакового размера и статической ориентации). Не сложно посчитать, что таким образом будет выполнено в сумме не более N*M операций.

E)           Можно было перейти к графу двойственному данному и обнаружить, что он дерево, а также установить взаимно однозначное соответствие между путями о которых шла речь в условии и не пустыми компонентами связности включающих корень данного дерева. Такие компоненты легко считать используя ДП по дереву: DP[u] = (DP[child1] + 1) * (DP[child2] + 1), DP[leaf] = 1. Но конечно такое решение не укладывалось в ТЛ и потому нужно было используя уравнение ДП свести к комбинаторной формуле благодаря рекуррентному соотношению между "нишами"(поддеревья которые идут от края карты вглубь). Tutorial of Codeforces Beta Round #15 By Shtrix, 9 years ago, translation, , Greetings, CodeForces users. CodeForces Beta Round #15 will be held today, 29th of May at 19:00 MSK. My name is Roman Iedmeksyi and I am lucky to introduce this problem set.

I would like to thank Dmitry MatovJulia Satushina and Mike Mirzayanov for well-coordinated work on this match. Also I would like to mention the contribution of Yaroslav Tverdokhlib in problems testing.

Some information about me:

I am a student of Kyiv National Taras Shevchenko University. I started programming at school. As my first achievement I had taken third place in Ukrainian Olympiad in Informatics. Next year I’ve worked harder and was qualified to IOI 2009 selection. Unfortunately I had not enough experience to pass.

In this contest I wish you good luck and high results.

UPD contest extended by 15 minutes

UPD Codeforces team apologizes that during today's round the server was regularly unavailable due to different technical reasons. We will try to do our best to avoid similar situations on the upcoming contests. Our apologies for some mistakes in the statements. Because of these reasons today's competition results will not affect your rating.

Looking forward to seeing you at Codeforces Beta Round 16. Announcement of Codeforces Beta Round #15 Announcement of Codeforces Beta Round #15 