Разбор задач Educational Codeforces Round 12 ### [problem:665A] Задачу предложил Сергей Эрлих [user:unprost,2016-04-20]. Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами $(x_1, y_1)$, ($x_1=60h+m, y_1=x_1+t_a$). Переберём встречный автобус. Пусть $(x_2, y_2)$ &mdash; это интервал времени, когда встречный автобус будет находиться строго между городами. Если пересечение этих интервалов $(x=max(x_1, x_2), y=min(y_1, y_2))$ не пусто, то Симион посчитает этот автобус. <spoiler summary="Решение на С++"> ~~~~~ int a, ta; int b, tb; int h, m; bool read() { if (!(cin >> a >> ta)) return false; assert(cin >> b >> tb); assert(scanf("%d:%d", &h, &m) == 2); return true; } void solve() { int x1 = h * 60 + m; int y1 = x1 + ta; int ans = 0; for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) { int y2 = x2 + tb; int x = max(x1, x2), y = min(y1, y2); if (x < y) ans++; } cout << ans << endl; } ~~~~~ </spoiler> Сложность: $O(1)$. ### [problem...

Full text and comments »

Разбор задач Educational Codeforces Round 11 ### [problem:660A] Задача предложена пользователем Ali Ibrahim [user:New_Horizons,2016-04-08]. Заметим, что если есть пара соседних не взаимнопростых чисел, то мы обязаны между ними вставить какое-нибудь число. С другой стороны мы всегда можем вставить число $1$. <spoiler summary="Решение на С++"> ~~~~~ const int N = 1010; int n, a[N]; bool read() { if (!(cin >> n)) return false; forn(i, n) assert(scanf("%d", &a[i]) == 1); return true; } void solve() { function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); }; vector<int> ans; forn(i, n) { ans.pb(a[i]); if (i + 1 < n && gcd(a[i], a[i + 1]) > 1) ans.pb(1); } cout << sz(ans) - n << endl; forn(i, sz(ans)) { if (i) putchar(' '); printf("%d", ans[i]); } puts(""); } ~~~~~ </spoiler> Сложность: $O(nlogn)$. ### [problem:660B] Задача предложена пользователем Srikanth Bhat [user:srikkbhat,2016-04-08]. В этой задаче нужно было сделать ровно...

Full text and comments »

Codeforces Round #199 (Div. 2) Разбор Задач [problem:342A] В этой задаче нужно было догадаться, что существует только 3 корректные тройки: 1) 1, 2, 4 2) 1, 2, 6 3) 1, 3, 6 Будем жадно набирать их пока получается. Если остались какие то неиспользованные числа (в том числе 5 и 7, которые очевидно сразу являются плохими), то выведем -1. Иначе выведем найденный ответ. [problem:342B] Эта задача решается жадно. Будем всегда двигаться только по направлению от $s$ до $f$. Причем, если в данный момент можно совершить действие, обязательно будем его совершать. Иначе не будем передавать записку соседу и оставим ее у себя (такой ход можно делать в любой ситуации). Очевидно, что такой подход приводит к правильному решению, остается его аккуратно реализовать. [problem:342C] В задаче нужно было аккуратно выписать формулу. Оптимальное решение укладывает шарики по два в ряд, пока это возможно. А потом сверху кладет еще один шарик, если это возможно. Основная хитрость и сложность была именно в последнем шаге. В ком...

Full text and comments »

Как решать задачи на ДП: Обычный подход Привет! В прошлом посте я ввёл два вида динамического программирования: _обычное_ и _с симуляцией процесса_. В нём я рассказал, как решать задачи на ДП, используя симуляцию процесса, пожалуйста, прочитайте, если пропустили, чтобы понимать разницу. Сейчас же я хочу поговорить о хитростях, которые помогают мне при решении задач на ДП обычным подходом. Тогда как в симуляции процесса нам требовалось изобрести некий процесс, который бы строил нам необходимые объекты, **в обычном подходе мы будем работать с объектами напрямую**. Каждое состояние ДП _(т. е., набор значений по каждому параметру)_ будет соответствовать некому классу желаемых объектов, а соответствующее значение в таблице ДП будет содержать информацию об этом классе, _что в действительности эквивалентно формулировке через подзадачи, описанной в предыдущем посте_. В этом посте я сосредоточусь на том, как придумывать переходы в ДП с обычным подходом, если вы уже определились с параметрами. Общий план такой: 1. Сформулируй...

Full text and comments »

Разбор задач Educational Codeforces Round 1 Задачи учебные &mdash; постараемся сделать разбор подробным. ### [problem:598A] Если бы в этой задаче не было бы "хитрости" и надо бы было просто найти сумму $1 + 2 + \dots + n$, то, воспользовавшись формулами суммирования арифметической прогрессии, можно было прийти к результату $s=n \cdot (n+1) / 2$ (числа такого вида называются треугольными). Однако каждое число, которое является степенью двойки, должно быть просуммировано не со знаком "плюс", а со знаком "минус". Давайте вычтем по два раза (так как первое вычитание просто изымет число из суммы, а второе &mdash; вычтет) каждую из степеней двойки, которые не превосходят $n$. Проще всего это сделать с помощью цикла вроде этого: ~~~~~ long long pow2 = 1; while (pow2 <= n) s -= pow2 * 2, pow2 *= 2; ~~~~~ Значение $s$ после такого цикла и будет ответом. Количество итераций этого цикла не превосходит двоичного логарифма числа $n$ (точнее &mdash; еще плюс единица), что является числом около 30 для максимального возмо...

Full text and comments »

Маленькая хитрость для перфекционистов Наверное, все, кому приходилось писать текст с формулами на Codeforces, знают, что каждую формулу, если это возможно, местный TeX пытается набрать символами, и, только если не получается, вставляет картинку с формулой так, как она бы выглядела в обычном ТеХе. Иногда это выглядит нормально, например, $2 \cdot 10^9$ (`2 \cdot 10^9`) или $(x_i+y_i)^2$ (`(x_i+y_i)^2`). Но иногда получается совершенно не то, что вы хотели, например, так: $C_{x_i+y_i-2}^{x_i-1}$ (`C_{x_i+y_i-2}^{x_i-1}`). В таком случае можно поставить в начале формулы символ `\quad`. Это, так называемый, "символьный пробел". Он представляет из себя белый квадратик, иными словами, пустой символ, но который при этом не считается пробельным символом. Местный ТеХ по какой-то причине не знает, как этот символ написать и поэтому вставляет формулу в виде картинки в настоящем ТеХовском виде, но символьный пробел игнорируется формулой так же, как и обычный пробел, поэтому на вид формулы это никак не влияет. Получается вот...

Full text and comments »

Школьная индивидуальная олимпиада #1 - Codeforces Beta Round #38. (Разбор задачи G) <h1>Задача G. "Очередь"</h1>Данная задача имеет несколько возможных решений, но я расскажу 2 возможных подхода:<br><br><h2>1. Декартово дерево (дуча, treap или дерамида)</h2>Будем считать, что читатели знакомы с этой структурой (если это не так, то советую почитать <a href="http://e-maxx.ru/algo/treap">тут</a>). Самое простой по логике подход использует неявное декартово дерево, и этот алгоритм действует так: будем добавлять людей по очереди, в порядке их прихода. В вершине дерева, кроме служебной информации, будем поддерживать число $maxValue$, равное максимальному значению из чисел $a_i$ в этом дереве.<br><br>Бинарным поиском переберем возможную позицию нового человека, пусть он имеет номер $k$, $pos$ от $0$ до $c_k$ (для удобства нумерацию введем с конца очереди). Человек достигнет этой позиции тогда и только тогда, когда среди чисел $a_i$, $0 \le i &lt; pos$ не существует ни одного, большего числа $a_k$. Это можно проверить, отщепив от декартова дерева поддерево размера $pos$, и пр...

Full text and comments »

Как можно ускорить решение на python3? Привет, codeforces! В рамках [проекта по подготовке к олимпиадам по программированию](https://www.youtube.com/channel/UCM01TVLxMvqEXq4Z9AFl-jA) в качестве задания была выдана эта [задача](https://acmp.ru/index.asp?main=task&id_task=621) на двумерное динамическое программирование. Кратко суть задачи: дана матрица размера $n^2$, где $n \le 200$ , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками $(x_1, y_1)$ и $(x_2, y_2)$ определяется как $dist = |x_1 - x_2| + |y_1 - y_2|$. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений. Я написал [решение на C++](https://github.com/dmkz/olymp/blob/master/acmp.ru/0621-dp.cpp), которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. [Вот что из этого вышло](https://github.com/dmkz/olymp/blob/master/acmp.ru/0621.py). Действий получается по...

Full text and comments »

Интерактивные задачи: алгоритм тестирования В последнее время формат типичных задач на соревнованиях по программированию расширяется новым видом задач, которые принято называть интерактивными. Решения таких задач в некотором роде общаются (взаимодействуют) с тестирующей оболочкой. Обычно, интерактивные задачи используются для задач двух видов: - Задачи на online-алгоритмы, т.е. такие алгоритмы, которые не читают все входные данные сразу, а могут читать их только по мере своей работы. Простой пример: задано множество из n чисел. Надо обработать n запростов. Каждый запрос содержит элемент множества, до обработки запроса надо вывести минимум чисел в множестве, а потом удалить этот элемент. Естественно, после последнего запроса множества станет пустым. Если решать эту задачу как офлайн-задачу, то можно решать ее <<с конца>>, обрабатывая запросы от последнего к первому (т.е. фактически добавляя в множество элементы). В таком случае решение совсем тривиально. Онлайн-формулировка не позволяет решению прочитать очередной запрос до об...

Full text and comments »

Помогите с идеей — SPOJ — 8843 Complete the Set Я временно перестал участвовать в соревнованиях по "личным обстоятельствам", но продолжаю урывками прорешивать задачки на разных сайтах. Напоролся на задачку (точнее мой генератор случайных чисел напоролся на задачку) [8843 Complete the Set](http://www.spoj.com/problems/COMPLETE/). Честно говоря ничего в голову не приходит &mdash; судя по параметрам задачи &mdash; 1100 случаев в одном тесте, 65536 чисел в одном сете &mdash; полный перебор вряд ли пройдёт, я имею в виду каждое число с каждым пробовать по OR и AND пока не перестанут появляться новые числа. (хотя бы понятно, что в такой ситуации не надо пробовать что-то большее, чем пары чисел &mdash; уже прогресс от "absolute brute force"). Но в голове вертится одна из недавних задачек с Topcoder, где нужно было смешивать краски с помощью XOR и решалась она элегантно гауссовой элиминацией &mdash; может быть и здесь какая-нибудь хитрость? Задачка не очень порешенная, "запылившаяся", решило её меньше 50 человек и разборов в интерн...

Full text and comments »

Сканирующая прямая Здравствуйте! Решал сегодня такую задачу: [задача](http://informatics.mccme.ru/mod/statements/view3.php?id=4252&chapterid=3721) На первый взгляд ничего сложного: сортировка событий + сканирующая прямая.Но я запутался в реализации(случай, если несколько начал/концов отрезков в одной точке). Отсюда возник вопрос: а есть где-нибудь статья о сканирующей прямой, рассказаны все хитрости(в идеале еще и двумерный случай)? Спасибо большое!

Full text and comments »

Школьная индивидуальная олимпиада #1 - Codeforces Beta Round #38. (Разбор задачи A) <h1>Задача А. "Армия"</h1>Эта задача была утешительной и самой простой на этом контесте. Ответ считается по формуле:<br><br>$$result = \displaystyle\sum_{i=a}^{b-1}d_i$$<br><br>Никаких "подводных камней" и хитростей эта задача не содержит.

Full text and comments »

Python и Time limit Как видно из цвета моего ника, я новичок в спортивном программировании. Начал примерно год назад, но серьезно увлекся после того, как попал на **ICL-2013**. Но суть не в этом. Сейчас в основном я стараюсь сдавать задания на Python, но часто происходит так, что у меня выходит тайм лимит, даже если по самым приближенным прикидкам все нормально, и даже если используются быстрые алгоритмы. Но стоит переписать код на С++, ничего не меняя, и все хорошо. Вопрос к вам, опытные питонисты, есть ли какие-то хитрости или советы, как дать питону волшебный пендель для ускорения? Или мне наедятся на Иисуса? Я понимаю, что не я 1 задаю подобный вопрос, но все-таки.

Full text and comments »

Вычисление арифметического выражения Всем привет. Недавно решил освоить метод рекурсивного спуска, нашел задачу http://informatics.mccme.ru/mod/statements/view3.php?id=11575&chapterid=112500 , написал код который прошел 10 тестов из 21. Попытался сдать на питоне, опять таки 10 из 21. Хотел спросить, кто нибудь сдавал эту задачу? Если да подскажите, может там есть хитрость какая то, которую я не могу понять

Full text and comments »