Замечательные впечатления оставил следующий эксперемент. Одно и тоже решение задачи С использующее priority_queue было сдано на двух компиляторах.
Итог:
Visual Studio 2005: TL 101 (как и на контесте)
GCC 4.6+: AC, 1090ms
Посылки:
442400
442399
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Недавно занялся изучением питона и уперся в проблему с переполнением стека.
Случай нулевой, достигается придел рекурсивных вызовов:
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 тысяч рекурсивных вызвов меня сильно удручает. Соответственно, вопрос, кто-нибудь знает какие-то хаки для глубокой рекурсии в питоне?
Для решения этой задачи, в первую очередь нам потребуется двоичное дерево. Естественно все его узлы хранить не удастся, соответственно прибегнем к помощи мапа/хешмапа или же пропишем свое дерево. Пускай мы для каждого поддерева храним текущее количество заряда в нем. Это несложно делается за 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)
Разбор задач Codeforces Beta Round 62
Наш союзер Skiminok написал замечательную статью по сабжу.
В довесок добавлю от себя "Где это можно сдать?":
Robotic Sort на Spoj.plА) Необходимо было отсортировать все дома по возрастанию координаты центра х. Для каждой пары последовательных домов (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. Но конечно такое решение не укладывалось в ТЛ и потому нужно было используя уравнение ДП свести к комбинаторной формуле благодаря рекуррентному соотношению между "нишами"(поддеревья которые идут от края карты вглубь).
Разбор задач Codeforces Beta Round 15
Доброго времени суток всем пользователям CodeForces. Сегодня, 29 мая в 19-00 по московскому времени состоится CodeForces Beta Round #15. Меня зовут Роман Едемский, и сегодня мне посчастливилось выступить в роле автора задач.
Хочу выразить огромную благодарность Дмитрию Матову, Юлии Сатушиной и, конечно, Михаилу Миразаянову за очень слаженную работу над этим матчем. Также большую помощь в тестировании оказал, мой друг и товарищ Ярослав Твердохлеб.
Немного о себе:
Сейчас я студент Киевского Национального Университета. Мой путь в олимпиадном программировании начался на школьной скамье примерно два с половиной года назад. Первым моим достижением был третий диплом всеукраинской олимпиады по информатике, а уже через год я попал на отборы к международной олимпиаде школьников 2009. К сожалению, тогда чтобы пройти, мне немного не хватило опыта, что я старательно исправляю сейчас.
Желаю всем удачи и хороших результатов!
UPD: Контест продлен на 15 минут
UPD: Краткий разбор здесь
UPD: Администрация Codeforces приносит свои глубочайшие извинения за то, что во время сегодняшнего соревнования сервер регулярно оказывался недоступен по различным техническим причинам. Нами будут приложены все усилия для избежания подобных ситуаций на последующих соревнованиях. Так же приносим свои извинения за некоторые неточности в условиях. По этим причинам этот раунд признается нерейтинговым.
Ждем Вас на Codeforces Beta Round 16.
Анонс Codeforces Beta Round 15
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 03:30:20 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
