Прожарка #228: adamant Всем здарова! Вечно можно смотреть на три вещи: как горит огонь, как бежит вода и как кто-то пытается несмешно шутить на codeforces Видя, как [<b style="color:#FF0000">I_love_plov27</b>](https://codeforces.com/profile/I_love_isaf27) натужно пытается исследовать просторы юмора своими унылыми блогами, мне, как чемпиону Иркутской области по юмору, захотелось дать ему отеческого подзатыльника и своим примером показать, как на самом деле надо шутить Сегодняшний гость прожарки &mdash; Александр [<b style="color:green">adamant</b>](https://codeforces.com/profile/adamant) Кульков, известный специалист по строкам и непрохождению в финал (да, он существует, я раньше тоже думал, что это мем) Надеюсь, что Александру Кулькову понравится прожарка, ведь у него дома нет газа Однажды Александр Кульков пытался собрать стол из IKEA, но у него всё равно получился суфмас Александр Кульков очень любит мемы, потому что слово "мем" &mdash; палиндром Когда Александр Кульков едет в автобусе, о...

Full text and comments »

Полиномиальные хеши Добрый день. Это пост о мелочах в реализации хешей. Сегодня ребята гуглили "как писать полиномиальные хеши", но нагулили лишь две ссылки на тему "как не надо писать полиномиальные хеши" &mdash; [e-maxx](http://e-maxx.ru/algo/string_hashes) и [habr](http://habrahabr.ru/post/142589/). А можно писать иначе &mdash; [short](http://acm.math.spbu.ru/~sk1/algo/hash/hash.cpp.html) и [full](http://acm.math.spbu.ru/~sk1/algo/hash/HashStrComparator_simple.cpp.html). Последняя версия устойчива к антихеш тестам, её **можно копипастить**. Теперь подробно. Есть два способа. Оба для краткости будут написаны по модулю $2^{64}$, то есть падают на строке [Туе-Морса](http://codeforces.com/blog/entry/4898). **Общая часть:** ~~~~~ const int P = 239017; // Если брать простой модуль, здесь стоит писать rand()! // s - строка, n - её длина ~~~~~ **Первый способ (я пишу так):** ~~~~~ // deg[] = {1, P, P^2, P^3, ...} // h[] = {0, s[0], s[0]*P + s[1], s[0]*P^2 + s[1]*P + s[2], ...} unsi...

Full text and comments »

Общие идеи Всем привет! Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я &mdash; терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :) [cut]<br> **1. Слияние множеств за $O(n\log{n})$ амортизированно.** Если у нас есть некоторые множества, которые нам потом нужно будет соединять, поддерживая промежуточные результаты, то можно делать это в лоб, всегда добавляя меньшее множество к большему. Таким образом, каждый элемент будет перенесён в какое-то другое множество не более, чем $O(\log{n})$ раз, так как новое множество для него каждый раз будет увеличиваться хотя бы в два раза. На этом, в частности, основана одна из версий общеизвестного _DSU_. Из применений &mdash; можно сливать множества внутри обхода дерева в глубину и таким образом можно для каждой вершины в какой-то момент времени подержать в руках множество всех элементов её поддерева. **2. Подвохи в задачах. Час...

Full text and comments »

[Tutorial] Полиномиальное хэширование + разбор интересных задач Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них: 1. Поиск всех вхождений одной строки длины $n$ в другую длины $m$ за $O(n+m)$ 2. Поиск наибольшей общей подстроки двух строк длин $n$ и $m$ $(n \ge m)$ за $O((n+m \cdot log(n)) \cdot log(m))$ и $O(n \cdot log(m))$ 3. Нахождение лексикографически минимального циклического сдвига строки длины $n$ за $O(n \cdot log(n))$ 4. Сортировка всех циклических сдвигов строки длины $n$ в лексикографическом порядке за $O(n \cdot log(n)^2)$ 5. Нахождение количества подпалиндромов строки длины $n$ за $O(n \cdot log(n))$ 6. Количество подстрок строки длины $n$, являющихся циклическими сдвигами строки длины $m$ за $O((n+m) \cdot log(n))$ 7. Количество суффиксов строки длины $n$, бесконечное расширение которых совпадает с бесконечным расшир...

Full text and comments »

Хеширование корневых деревьев Я обнаружил небольшую нехватку материалов на эту тему и хочу начать со статьи [user:rationalex,2023-03-03]: Задача ------ Хотим научиться сравнивать корневые деревья на изоморфизм (равенство с точностью до перенумерования вершин + корень одного дерева обязательно переходит в корень другого дерева). Хеш вершины ----------- Заметим, что поскольку мы не можем апеллировать к номерам вершин, единственная информация, которую мы можем оперировать &mdash; это структура нашего дерева. Положим тогда хешем вершины без детей какую-нибудь константу (например, 179), а для вершины с детьми положим в качестве хеша некоторую функцию от отсортированного (поскольку мы не знаем истинного порядка, в котором дети должны идти, нужно привести их к одинаковому виду) списка хешей детей. Хешом корневого дерева будем считать хеш корня. По построению, у изоморфных корневых деревьев хеши совпадают (доказательство индукцией по числу уровней в дереве автор оставляет читателю в качестве упражнения). ...

Full text and comments »

Язык D в спортивном программировании Всем привет! Недавно участнику [user:yosupo,2018-07-28] задали [вопрос](/blog/entry/51923?#comment-446901) о том, в чём преимущества [языка программирования D](https://dlang.org) в соревнованиях перед языком C++. Я регулярно использую D в соревнованиях (и при подготовке задач) с 2014 года, иногда вполне успешно (например, программа на D принесла мне победу в [AZsPCs: Alphabet City](http://azspcs.com/Contest/AlphabetCity/Standings)). Так что хочу поделиться своим опытом. Постараюсь ограничиться только тем, что имеет значение для соревнований. Общее ощущение такое. На D можно писать как на чистом C, когда нужен полный контроль над происходящим. А можно &mdash; как на Питоне, используя довольно мощную библиотеку. При этом D &mdash; компилируемый язык, так что в обоих случаях производительность сравнима с C++. Кроме того, после написания программы её гораздо проще отладить, чем аналогичную программу на C++. В качестве примера давайте посмотрим на два решения одной ...

Full text and comments »

Разбор Educational Codeforces Round 41 [problem:961A] <spoiler summary="Разбор"> [tutorial:961A] </spoiler> <spoiler summary="Решение (Vovuh)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int n, m; cin >> n >> m; vector<int> cnt(n); for (int i = 0; i < m; ++i) { int col; cin >> col; ++cnt[col - 1]; } cout << *min_element(cnt.begin(), cnt.end()) << endl; return 0; } ~~~~~ </spoiler> [problem:961B] <spoiler summary="Разбор"> [tutorial:961B] </spoiler> <spoiler summary="Решение (Vovuh)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int n, k; scanf("%d %d", &n, &k); vector<int> a(n); vector<int> t(n); int overall = 0; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n...

Full text and comments »

Anti-hash-table тесты в Python TLDR ==== Если вы пишете на питоне, используете set или dict и хотите избежать взломов -- можете читать только последний раздел. Введение ======== Большинство людей, интересующихся взломами знают про метод создания тестов, нацеленных против unordered контейнеров в C++. Подробнее этот метод описан в [посте](https://codeforces.com/blog/entry/62393). Однако гораздо хуже освещено создание подобных тестов для set и dict в python, что я и решил исправить данным постом. Немного теории о хеш-таблицах ============================= Я не буду вдаваться в подробные описания и доказательства, поскольку их полно в открытых источниках. Разберем только то, что нас интересует в данном случае. Хеш-таблица c открытой адресацией -- это структура данных, которая хранит набор элементов в массиве заведомо большего размера, определяя позицию очередного элемента, как его хеш, взятый по модулю размера массива. Если хеши нескольких элементов дают одну и ту же ячейку в массиве, то хеш-таблица пытае...

Full text and comments »

Неофициальный разбор + обсуждение длинного тура Открытой олимпиады 2023 Привет, Codeforces! Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте. Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;) Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем): <spoiler summary="А на 100 баллов"> Заметим тот факт, что для любого $1 < i \le n$ будет выполняться $max(p_{0:i}) \ge i$. Назовём _хорошей позицией_ такое $i$, что $max(p_{0:i}) = i$. Понятно, что если закончить очередной подотрезок не на _хорошей позиции_, то само число $i$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $max(p_{0:i})$, противоречие. То есть, концы отрезков могут совпадать только с _хорошими позициями_ -> перестановку можно разбить на $k$ отрезков с необходимым свойством только тогда, ког...

Full text and comments »

Разбор Codeforces Round #124 [problem:197A] Если первый игрок своим ходом не может поставить тарелку на стол (стол слишком маленький, и тарелка не помещается, т.е. $2r > min(a,b)$), выигрывает второй игрок. Иначе выигрывает первый игрок. Выигрышная стратегия такова: первый игрок ставит свою первую тарелку в центр стола, а затем симметрично отражает ходы соперника относительно центра стола стола. Легко видеть, что если в этом случае второму игроку удастся совершить ход, первому это также удастся. А если не удастся, первый игрок победит, что ему и было нужно. [problem:197B] Решение задачи --- разбор случаев. Легко понять, что важны лишь степени многочленов и их коэффициенты при старшем члене, остальные числа в инпуте --- для отвода глаз. 1. Если степень знаменателя больше, ответ равен "0/1". 2. Если степень числителя больше, ответ --- бесконечность. Чтобы понять, какая именно, надо посмотреть на знаки при старших коэффициентах. Если знаки одинаковые, то положительная, иначе --- отрицательная. 3. ...

Full text and comments »

Хешируемое множество со сравнением за O(1) Итак, многие из Вас знают, что можно легко и просто хешировать множества. Например, множество $s = \{ s_1, s_2, ..., s_n \}$ можно захешировать числом $x(s_1) + x(s_2) + ... + x(s_n)$ или даже $x(s_1) \oplus ... \oplus x(s_n)$ (где $x$ &mdash; какая-то случайная функция). С такими хешом можно поддерживать операции добавления и удаления элемента, слияния множеств, нахождения симметричной разности множеств и так далее. Но у такого подхода есть и достаточно серьезный минус, например, имея на руках только хеш мы не можем понять, какие элементы содержит это множество. Сегодня я хочу поведать о не очень сложной структуре данных, основанной на дереве отрезков, которая позволяет совершать различные операции с множествами, в частности, сравнивать эти множества за время O(1), надеюсь, после прочтения вы поделитесь своими идеями, как ее можно улучшить и какие еще операции с ней можно делать. :D Итак, для начала рассмотрим следующую задачу. В первой строке даны числа $N,Q \leq 10^5$, отвеча...

Full text and comments »

Способы разрешения коллизий в хеш-таблицах. До сих пор я знал только два принципиально различных способа разрешения коллизий, оба описаны в кормене. Разумеется это разрешающие цепочки и двойное хеширование.<br><br> Читал немного про perfect hashing, но то что следует ниже придумал час назад. <br><br> Итак, мы хотим положить в хеш таблицу **n** заранее известных объектов. А потом спрашивать её, содержит ли она такой объект. Предлагается завести массив размера **n** значениями которого могут быть объекты или null. И второй массив, где i-тый элемент равен **true**, если в этой ячейке есть коллизия, либо **false** в противном случае. Без особого матана, я численно прикинул, что порядка **1 / exp(1.0)** (1/2.71828…) объектов должны с кем-то образовать коллизию. Для этой части объектов заведем подобную хеш-таблицу рекурсивно. Когда у нас осталось n < K объектов, для построения хеш-таблицы, мы просто применяем линейный поиск по списку. Ну или бинарный поиск, значение K фиксированное, и может быть выбрано оптимально исходя из практики...

Full text and comments »

Codeforces Round #897 (Div. 2) Editorial Всем привет! Просим прощения за задержку >_< Надеемся, что вам понравились наши задачи! Извините за то, что лимиты по времени и памяти в некоторых задачах были слишком жесткими и решения на Java не проходили С (кстати, у одного из авторов бывшый ник &mdash; "java." :D). Постараемся не допустить таких ошибок вновь. Оставляйте впечатления и пожелания в комментариях! Спасибо за участие! [1867A &mdash; green_gold_dog, массив и перестановка](https://codeforces.com/contest/1867/problem/A) Автор: [user:green_gold_dog,2023-09-12] <spoiler summary="Разбор"> Из минимального числа вычтем $n$, из следующего $n - 1$, из следующего $n - 2$, $\ldots$, из максимального $1$. Тогда количество различных элементов будет $n$. Очевидно лучшего результа достичь невозможно. Докажем, что количество различных элементов будет равно $n$. Допустим $c_i = c_j$, тогда без ограничения общности скажем, что $b_i > b_j$, тогда $a_i \leq a_j$, значит $c_i = a_i - b_i$ < $a_j - b_j = c_j$. Противоречие....

Full text and comments »

Codeforces Round #109: разбор Формулы генерируются со скрипом, надо обновлять страницу, чтобы они появлялись. [problem:155A] Надо сделать, что написано: считать массив и посчитать количество элементов, больших или меньших всех предыдущих. Массив для этого можно даже не хранить, а поддерживать текущий минимум и максимум. Сложность --- O(N), хотя проходил и квадрат. [problem:155B] Заметим, что мы всегда можем сперва сыграть все карты с $b_i > 0$, т.к. каждая из них дает хотя бы один дополнительный ход. Количество оставшихся дополнительных ходов после этого не зависит от порядка их отыгрыша. После этого у всех оставшихся карт $b_i = 0$, и из них надо играть те, у которых максимально $a_i$. Простой вариант того же решения: отсортировать все карты по убыванию $b_i$, а при равенстве --- по убыванию $a_i$, а затем идти от начала к концу, моделировать счетчик оставшихся ходов и суммировать очки. При этом надо не вылететь за границу массива, если дополнительных ходов больше, чем карт. Сложность --- $O(n \log{n...

Full text and comments »

Отбор в кружок олимпиадного программирования «Тинькофф» 2021-2022 Всем привет! Начинается новый учебный год, вместе с ним стартует и сезон олимпиад. Этот пост будет полезен школьникам, которые хотят заниматься олимпиадным программированием, но не знают где. Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт **до 12 сентября включительно**. Зарегистрироваться и начать решать можно здесь: [algocode.ru](https://algocode.ru). Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты). Каждый год мы стараемся быть лучше и действительно полезными, так что в этом году кружок будет еще интереснее. ## Про формат занятий По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, п...

Full text and comments »

Codeforces Round #207: разбор задач #### [problem:357A] В задаче нужно было перебрать все варианты проходного балла от 1 до 100 и для каждого варианта посчитать, какие получаются размеры групп. Если нашли подходящие разбиения, выводим соответствующий одном из них проходной балл, иначе выводим 0. #### [problem:357B] Будем обрабатывать танцы в порядке их исполнения, и определять цвета формы участвующим в них танцорам. Если в текущем танце нет ни одного ранее танцевавшего участника, то назначим всем троим танцорам различные цвета формы произвольным образом. В случае же, если есть один такой танцор, тогда для него цвет формы уже известен. Два других цвета формы произвольным образом распределим между остальными двумя танцорами. #### [problem:356A] Пусть в очередной битве $(l, r, x)$ сражается $K$ рыцарей. Тогда в этой задаче было достаточно научиться находить всех этих рыцарей за время $O(K)$ или $O(KlogN)$. Рассмотрим несколько способов сделать это. Способ первый: хранить множество рыцарей в std::set (C++) ...

Full text and comments »

Дерево палиндромов: немного закулисья Всем привет! Как некоторые уже знают, на этих летних сборах в Петрозаводске [user:MikhailRubinchik,2014-09-25] презентовал новую структуру данных, а именно дерево палиндромов. Я имел честь поучаствовать в изучении структуры за полгода до этого, о чём и хочу теперь рассказать :) [cut]<br> Но для начала краткий экскурс. Если вы уже знаете базовые идеи реализации, можете смело <a href="#inter">переходить</a> к интересной части. Давайте каждому палиндрому поставим в однозначное соответствие строку, равную его правой половине, то есть, радиус и булеву переменную, обозначающую его чётность. Теперь объединим все радиусы подпалиндромов строки $S$ в два бора &mdash; для чётных и нечётных длин раздельно. Утверждение: такой бор будет занимать $\mathit O(n)$ памяти. Ну действительно, в строке может быть не больше $n$^{<a name = "ref10" href="#ref11">[1]</a>} различных палиндромов, а каждая вершина в дереве соответствует одному уникальному подпалиндромы. Следовательно, у нас не бол...

Full text and comments »

Про хеширование без домножения (ну и без деления, конечно) При решении задач на хеширование вам очень частно бывает надо уметь за $O(1)$ вычислять хеш любой подстроки заданной строки. Стандартный подход к таким задачам — давайте посчитаем хеши всех префиксов, а дальше будем с этим что-то делать... (Это кросс-пост [поста](http://blog.algoprog.ru/hash-no-multiply/) из моего блога.) ...Итак, стандартный подход устроен следующим образом. Начнем немного с начала. Определим хеш строки (хеш-функцию) так: $$h(s) = s_0 + s_1 \cdot p + s_2 \cdot p^2 + \ldots + s_{n-1} \cdot p^{n-1}.$$ (Все вычисления здесь и ниже подразумеваются по некоторому модулю $M$.) Посчитаем хеши всех префиксов: $$ H[i] = h(s[0..i]) = s_0 + s_1 \cdot p + \ldots + s_i \cdot p^i $$ Массив $H[i]$ можно насчитать за $O(n)$ очевидным образом ($H[i] = H[i-1] + s_i \cdot p^i$, массив степеней $p$ можно насчитать заранее, будет полезно и в дальнейшем). Хорошо. Но нам надо знать хеш произвольной подстроки, т.е. $h(s[i..j])$. Очевидно, чтобы его вычислить, ...

Full text and comments »

Codeforces Beta Round #30. Разбор E <h1>Разбор задачи "E. Хитрый и умный пароль"</h1><h3>Общая схема решения</h3><p>Общая схема авторского решения следующая. Переберём позицию $pos$ центра средней части $middle$ ответа (той, которая является палиндромом). Дальше возьмём в качестве $middle$ максимальный подпалиндром, имеющий середину ровно в позиции $pos$. После этого надо взять в качестве $prefix$ и $suffix$ такие максимальные по длине строки, что они удовлетворяют всем условиям задачи, и при этом не пересекаются с выбранной серединой.</p><p>Выполнив эту процедуру для каждой позиции $pos$ и выбрав среди всех найденных ответов наилучший, - получим ответ на задачу.</p><h3>Реализация</h3><p>Фактически, задача состоит из двух подзадач:</p><p>Во-первых, определение максимальной длины палиндрома, имеющего центр в заданной позиции. Это делается за $O(n)$ алгоритмом, описанным <a href="http://e-maxx.ru/algo/palindromes_count">у меня на сайте</a>. Иначе это можно делать с помощью бинпоиска и, например, хешей: переберём бинарным п...

Full text and comments »

C++ STL: map и set Всем доброго времени суток! Сегодня мне захотелось написать статью о таких зачастую важных на олимпиадах элементах STL, как $map$ и $set$, то есть, о множествах. Понимаю, что практически все участники div. 1, которые пишут на С++ с ними знакомы и для них статья будет малополезной. Однако, как мне кажется, многие участники div. 2 напротив, могут о них не знать. В первую очередь на них и ориентирована данная статья. Также хочу отметить, что буду рад всякой критике, если Вы сочтёте её необходимой. [cut] <br><br> Итак, приступим. Как многие знают, "set" переводится с английского как "множество". Отсюда можно сделать логичный вывод, что $set$ &mdash; это некая структура данных, которая реализует множество как математический объект. В С++11 есть две различные реализации множества. Первая пришла к нам из С++98. Это обычный $set$ и основан он на реализации красно-чёрного дерева. Вторая реализация &mdash; $unordered$_$set$, которая была "узаконена" с введением стандарта С++11. Она осно...

Full text and comments »

EZ Collections, EZ Life (new Java library for contests) Доброго времени суток, дорогие друзья. В этом посте я расскажу об одной из негативных сторон языка Java на соревнованиях по программированию (да и вообще), а точнее, как я попытался ее решить. Как известно, язык Java страдает недостатком при работе с коллекциями: ограничения этого языка заставляют программиста использовать объектные типы данных даже там, где этого как бы и не требуется. Сравните `ArrayList<Integer>` и `vector<int>`: в Java-варианте лист хранит объекты типа Integer, которые создаются при каждом добавлении элемента в список и распаковываются при каждом обращении, тогда как C++-ный вектор хранит обычные честные int-ы. Это замедляет работу программ на Java и много кому не нравится. Вся фигня в том, что нельзя просто так взять и написать примитивный тип внутри угловых скобок. Ну не спроектировали так Java, бывает. Несколько месяцев назад я подумал: а почему бы не обойти эту проблему? Ведь можно просто написать собственные коллекции, и дело в шляпе. Тем более что ни од...

Full text and comments »

Codeforces Beta Round #86 Разбор <p></p><div><b>Div 2. Задача А.</b>&nbsp;<span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 13px; background-color: rgb(248, 248, 248); "><a href="http://codeforces.com/contest/114/problem/A" style="color: rgb(0, 0, 204); ">Cifera</a></span><br></div><div>Если переформулировать задачу то необходимо было определить&nbsp;является ли число l, некоторой положительной степенью числа &nbsp;$k$. Для этого можно делать одно из двух:</div><div>1) В 64-битном типе данных найти минимальную степень $h$ числа $k$, такую что $k^h \ge l$. Если $k^h = l$, то ответ&nbsp;$YES$, и число артиклей - $h-1$, иначе $NO$.</div><div>2) Будем делить $l$ на&nbsp;$k$, пока&nbsp;$l$ делится на&nbsp;$k$ и $l \ne 1$. Если $l = 1$, то ответ - $YES$ и число делений-1, иначе ответ $NO$.</div><div><br></div><div><b>Div 2. Задача B.</b>&nbsp;<span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-size: 13px; background-color: rgb(255, 255, 255); "><a href="...

Full text and comments »

Остаток от деления на 2^p-1 **UPD**. Оригинал статьи оказался доступен в кэше поисковой системы mail.ru, спасибо [user:r3t,2019-03-09]. [запрос](https://go.mail.ru/search?src=go&fr=main&sbmt=1552134725484&frm=main&q=https%3A%2F%2Fzealint.ru%2Feducation%2Fostatok-ot-deleniya-na-2s-1.html), [результат](http://hl.mailru.su/mcached?q=https%3A%2F%2Fzealint.ru%2Feducation%2Fostatok-ot-deleniya-na-2s-1.html&qurl=http%3A%2F%2Fzealint.ru%2Feducation%2Fostatok-ot-deleniya-na-2s-1.html&c=14-1%3A680-1&r=10064250&frm=webhsm) Всем привет! Сегодня обнаружил, что [старая статья](https://zealint.ru/education/ostatok-ot-deleniya-na-2s-1.html) про остатки от деления на $2^p-1$ недоступна больше по этому адресу, ее нет ни в кэше яндекса, ни в кэше гугла. В ней описывались и доказывались интересные факты о вычислении остатков от делений на числа вида $2^p-1$, а также было указано как и где они применялись. Если эта статья доступна на каком-то другом ресурсе, или вы знаете аналогичную статью, то прошу поделиться в комментариях. Ниж...

Full text and comments »

Опять об оптимизациях, или Сколько будет от нуля до трех Дебагая хеш-таблицу, я вчера наткнулся на очередное забавное проявление оптимизатора g++. Вот минимальный код, на котором я смог его воспроизвести. ``` #include <iostream> int main() { for (int i = 0; i < 4; ++i) { std::cout << i*1000000000 << std::endl; } } ``` Казалось бы, вывод предсказуем. Более того, без оптимизации это действительно так. Однако... ``` ifsmirnov@carbon:./tmp$ g++-4.8 a.cpp -O2 && ./a.out | head -n 10 0 1000000000 2000000000 -1294967296 -294967296 705032704 1705032704 -1589934592 -589934592 410065408 ``` И так бесконечно долго. Логическая цепочка оптимизатора понятна: по стандарту переполнение инта при умножении -- это UB, значит, можно делать всё, что угодно. Но во что превратилось условие остановки цикла, я так и не понял. У меня это воспроизводится на g++-4.8 c -O2 и выше. На 4.4, 4.6 и 4.7, clang-3.4 выводятся четыре числа даже с любыми уровнями оптимизации. Интересно, что по этому поводу думает MinG...

Full text and comments »

Разбор личной олимпиады для 6-9 классов Разбор [contest:368205]. [problem:375720A] <spoiler summary="Разбор"> Для тестов до 10 было достаточно повыписывать ответы на листочке. Для второй группы можно было перебрать все возможные пары $i$, $j$ и проверить выполнение условия. $O(n^2)$ Для третьей группы нужно было понять, что для фиксированного $i$ $j = n - i$. $O(n)$ Для полного решения заметим, что для каждого числа от $0$ до $n$ мы сможем найти пару. Тогда ответ это $n + 1$. Итоговая асимптотика $O(1)$. </spoiler> <spoiler summary="Код"> ~~~~~ #include <bits/extc++.h> #define int int64_t using namespace std; int32_t main() { int n; scanf("%lld", &n); n++; printf("%lld", n); } ~~~~~ </spoiler> [problem:375720B] <spoiler summary="Разбор"> Для первой группы было достаточно заметить, что ответ всегда равен $k$. Для второй группы необходимо было найти количество единиц и двоек и решить аналогично первому случаю. Для третьей группы необходимо было ...

Full text and comments »

Russian Code Cup 2017 Finals — Results and Editorial Во-первых, поздравляем [user:moejy0viiiiiv,2017-09-10] с победой, [user:LHiC,2017-09-10] и [user:jcccccccccccccccccccccsb,2017-09-10] со вторым и третьим местом. Финал оказался сложным и мы рады, что борьба была жесткой. Задачи для раунда придумали и готовили [user:Aksenov239,2017-09-10], [user:GShark,2017-09-10], [user:izban,2017-09-10], [user:manoprenko,2017-09-10], [user:niyaznigmatul,2017-09-10], [user:qwerty787788,2017-09-10] и [user:SpyCheese,2017-09-10], руководитель жюри [user:andrewzta,2017-09-10]. Отдельно хочется отметить Илью Збаня [user:izban,2017-09-10], который является автором задач D, E и F, а также дал огромное количество полезных комментариев по всем задачам раунда. Теперь перейдем к разбору. <div class="problem-statement"><div class="header"><div class="title">A. Теория множеств</div></div><div class="tutorial"><p>Для начала докажем, что ответ всегда <span class="tex-font-style-tt">YES</span>.</p><p>Будем последовательно перебирать <span class="tex-span"><i...

Full text and comments »

Генераторы на testlib.h Генераторы &mdash; это такие вспомогательные программы в задаче по программированию, которые выводят тесты. Далеко не всегда ручные тесты в задаче достаточно маленькие, чтобы обойтись только ими. В этом случае на помощь и приходят генераторы. Если вы пишете генератор на С++, то использование [testlib.h](https://github.com/MikeMirzayanov/testlib) &mdash; хороший выбор. ### Виды генераторов Есть два вида генераторов: обычные и мультигенераторы. 1. Первые за один свой запуск выводят ровно один тест. Обычно, чтобы сгенерировать несколько тестов, такой генератор надо запустить несколько раз с разными параметрами командной строки. Такие генераторы выводят тест в стандартный поток вывода (на экран). 1. Мультигенераторы за один запуск выводят сразу много тестов. Такие генераторы выводят тесты в файлы (один файл &mdash; один тест). ### Пример простого обычного генератора на testlib.h Выводит пару чисел от 1 до $n$, где $n$ &mdash; переданный параметр запуска генератора. ~~~~~...

Full text and comments »

Генератор против двойных хешей по модулям порядка 10^9 Во многом, продолжение этой [темы](http://www.codeforces.ru/blog/entry/4898). Для многих не секрет, что построить коллизию для полиномиального хеша по модулю, например, 10^9 + 7, не очень сложно. Вот [здесь](http://pastebin.com/JfTEUwCe) находится генератор, который достаточно быстро находит коллизию для двойного хеша по достаточно маленьким модулям (технически --- порядка 10^10, хотя можно сделать более быструю версию до 10^12). При желании, можно сделать то же самое и для тройного хеша. Идея в следующем: парадокс дня рождения позволяет генерировать хеш-коллизию первого хеша простым перебором за O(sqrt(p)), где p --- модуль, по которому берется хеш. После этого каждая из полученных строк коллизии первого хеша считается отдельным символом, и при помощи парадокса дня рождения генерируется коллизия для второго хеша (коллизией первого хеша строка-конкатенация коллизий будет автоматически). Примечание. Для неизвестного хеша по простому модулю универсальных контртестов, по-в...

Full text and comments »

Codeforces Round #857 Editorial [problem:1802A] ------------------ Автор: [user:Aleks5d,2023-03-13], разработчик: [user:vaaven,2023-03-13] <spoiler summary="Решение"> Давайте покажем конструкцию, которая максимизирует количество лайков. Нам нужно сначала оставить все лайки, которые мы можем поставить, а только потом убирать их. Для того, чтобы минимизировать количество лайков, нам нужно убирать лайк (если мы можем) сразу после того как мы его поставили. Приведенный ниже код реализует эти конструкции. </spoiler> <spoiler summary="Код"> ~~~~~ #include "bits/stdc++.h" using namespace std; void solve() { int n; cin >> n; int likes = 0, dislikes = 0; for (int i = 0; i < n; i++) { int x; cin >> x; if (x > 0) likes++; else dislikes++; } for (int i = 1; i <= n; ++i) { if (i <= likes) cout << i << ' '; else cout << likes * 2 - i << ' '; } cout << '\n'; for (int i = 1; i <= n; ++i) { if (i...

Full text and comments »

Об упорядоченных множествах Всем привет! Думаю, многие знают про такой тип данных, как множество. Он должен поддерживать следующие операции: * Добавить элемент в множество; * Узнать, есть ли элемент в множестве; * Удалить элемент из множества. Если речь идёт о множестве упорядоченном, то элементы также должны располагаться в нём в определённом порядке. Лично я считаю, что для упорядоченных множеств также очень важны следующие операции: * Узнать, какой элемент является K-ым в множестве; * Узнать, какой номер был бы у элемента, если бы он находился в этом множестве. Чаще всего для реализации такого функционала используются двоичные сбалансированные деревья (AVL-дерево, красно-чёрное дерево, декартого дерево, etc). Однако в этой статье я бы хотел поговорить о некоторых особенностях в реализации упорядоченного множества на других структурах. В частности, в этой статье мною будут рассмотрены реализации на дереве Фенвика и на дереве отрезков. Сразу хочу отметить, что это позволяет воссоздать множест...

Full text and comments »

Разбор задач Codeforces Round #291 (Div. 2) [problem:514A] -------------- **Автор:** [user:Rebryk,2015-02-15] Очевидно, что все цифры, которые больше 4, нужно инвертировать. Кроме цифры 9, если она первая цифра числа. **Асимптотика:** $\mathcal{O}(\text{длина числа})$ [problem:514B] -------------- **Автор:** [user:Antoniuk,2015-02-15] Переберем точки, в которых находятся солдаты. Если в данной точке солдаты еще не убиты, то сделаем выстрел и уничтожим всех солдатов, находящихся на прямой, проходящей через месторасположение пушки и данную точку. Точки $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ лежат на одной прямой, если $(x_2 - x_1)(y_3 - y_1) = (x_3 - x_1)(y_2 - y_1)$. **Асимптотика:** $\mathcal{O}(N^2)$ [problem:514C] -------------- **Автор:** [user:Rebryk,2015-02-15] При добавлении строки в множество, посчитаем от нее полиномиальный хэш и добавим его в массив. Затем этот массив отсортируем. Теперь для ответа на запрос будем пробовать менять каждый символ в строке и с помощью бинарного поиска про...

Full text and comments »

Разбор Задач Codeforces Beta Round #25 <h3>Задача A - IQ Тест</h3>Надо просто посчитать количество чётных и нечётных числ. В данных числах может быть или только одно чётное число, или только одно нечётное число --- надо найти его и вывести его номер.<br><br><h3>Задача B - Телефонные Номера<br></h3>Есть много методов разбить на группы из 2 или 3 цифр. Представим один простой вариант: вывести группы из двух цифр пока останется больше чем 3 цифр:<br><br>&lt;code&gt;<br>for( i=0; i&lt;n; i++ )<br>{<br>&nbsp;&nbsp;&nbsp; putchar(buf[i]);<br>&nbsp; &nbsp; if( i%2 &amp;&amp; i&lt;n-(n%2)-2 ) putchar('-');<br>}<br>&lt;/code&gt;<br><br><br> <h3>Задача C - Дороги в Берляндии<br></h3>Входнные данные --- матрица $D$, в которой $D[i][j]$ явлется кратчайшим расстоянием между городами $i$ и $j$. Если создадим новуюу дорогу между городами $a$ и $b$ с расстоянием меньше чем $D[a][b]$, как обновить остальные расстояния в $D$?<br><br>Пусть матрица $D'[i][j]$ --- кратчайшее расстояние между $i$ и $j$ если добавим в граф новое ребро $ab$. Дл...

Full text and comments »

MIPT Open Warmup I. Разбор задач. Задача A.<BR><BR>Задача решается с помощью поиска максимального потока. Проведём ребра от истока ко всем ядрам, от ядер к пушкам, если мы успеем взять его и принести обратно, от пушек к целям, если пушка в состоянии достать до неё, и от всех целей до истока. Все рёбра имеют пропускную способность 1. И надо ещё заметить, что, так как пушка может стрелять только 1 раз, то вершины, отвечающие за пушки надо раздвоить.<BR><BR>Задача B.<BR><BR><P>Не знаю, как можно решить её по-нормальному, но я сдал её рандомом. Пометим случайно все рёбра числами от $1$ до $3*n$. Далее $20\, 000$ раз проделаем следующую операцию: за $O(n\times \log n)$ определим есть ли две тройки с одинаковой суммой, если есть, тогда выберем случайное число из первой тройки и случайное число из второй тройки и поменяем их местами. Так как числа разные, то суммы у этих троек теперь станут разными.</P><P></P><P>[cut]<BR></P><BR>Задача C.<BR><BR>Сначала избавимся от игры на круге и перейдём к игре на ленте, для этого просто б...

Full text and comments »

C++11. Все, что нужно олимпиаднику. Всем привет! В качестве предисловия отмечу, что эта статейка написана скорее от нечего делать, нежели ради благих целей, но тем не менее, надеюсь, что некоторую пользу она все же принесет. Заниматься олимпиадами я больше не хочу, поэтому это что-то вроде "прощания" с миром спортивного программирования. Звучит глупо, но начать как-то надо было... Как известно, на данный момент официальным стандартом С++ является ISO/IEC 14882:2011, или же, проще говоря, С++11. Поддерживается он не на всех серверах, но со временем, думаю, ситуация изменится. Codeforces, например, идет в ногу со временем. C++0x, доступный здесь, фактически ничем от С++11 не отличается, просто другое наименование ("рабочее" название в ходе работы над будущим стандартом на самом деле). По крайней мере, начиная с GCC 4.7, установленного здесь, это так. Сразу скажу, что я буду опираться на GCC, ибо в Visual C++ практически все новые фичи появляются только в 10 и, в основном, 11 версии, которые не шибко то распространены....

Full text and comments »

Летняя школа Сазанка-2017 <img src="http://assets.codeforces.com/photos/sazanka-2010/large-IMG_2742.JPG" style="width:350px;float:right;margin:1em;"> ### Общая информация Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы &mdash; десять дней, школа пройдет с 31-го июля по 10-е августа 2017 года. К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники. Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки. В программе школы запланировано 10 рабочих дней, включающих ежедневные пятичасовые тренировки, разборы задач, дорешивания. Будет прочитана серия лекций. Учебная программа рассчитана на студентов, которые хотят достичь значительных успехов на соревнованиях по ...

Full text and comments »

Летняя школа Сазанка-2015 <img src="http://assets.codeforces.com/photos/sazanka-2010/large-IMG_2742.JPG" style="width:350px;float:right;margin:1em;"> ### Общая информация Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы &mdash; десять дней, школа пройдет с 3-го по 13-е августа 2015 года. К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники. Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки. В программе школы запланировано 10 рабочих дней, включающих ежедневные пятичасовые тренировки, разборы задач, дорешивания. Будет прочитана серия лекций. Учебная программа рассчитана на студентов младших и средних курсов, которые хотят достичь значительных успехов н...

Full text and comments »

Куча с удалением по значению Как известно, обычная реализация кучи не поддерживает удаление произвольного элемента по его значению. Конечно, проблема решается стандартным методом: завести хеш-таблицу и для каждого элемента кучи поддерживать указатель на его место. Не самый оптимальный по скорости написания метод. Существует другой подход, на мой взгляд, более удобный. Тем более у нас уже есть реализация кучи, и это нужно использовать. </p> <p> Пусть $H$ &mdash; куча с которой мы хотим работать. Создадим новую кучу $Del$, В которую будем складывать "удаляемые элементы". То есть, когда пришёл запрос на удаление $x$, с исходной кучей ничего не происходит, мы просто берём $x$ и добавляем его в $Del$. (Для простоты я пока что считаю, что все запросы корректны, то есть удаляемый элемент гарантированно есть в $H$). <p> При обращении к максимальному элементу может так случиться, что он уже был удалён, поэтому надо восстановить нашу кучу. А именно, пока элементы на вершине $Del$ и $H$ совпадают &mdash; извлекаем их обои...

Full text and comments »

Летняя школа Саратовского ГУ — "Сазанка 2013" <img src="http://assets.codeforces.com/photos/sazanka-2010/large-IMG_2742.JPG" style="width:350px;float:right;margin:1em;"> ### Общая информация Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы &mdash; десять дней, школа пройдет с 5-го по 15-е августа. К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники. Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки. В программе школы запланировано 10 рабочих дней, включающих ежедневные пятичасовые тренировки, разборы задач, дорешивания. Будет прочитана серия лекций. Учебная программа рассчитана на студентов младших и средних курсов, которые хотят достичь значительных успехов на соревнов...

Full text and comments »

Почему не надо использовать Java.HashSet/HashMap для целых чисел. После небольших обсуждений, мы решили все-таки выложить код генератора, который вызывает #TLE у коллекций HashSet и HashMap в Java. Вот он --- [http://pastebin.com/qpyNcD3R](http://pastebin.com/qpyNcD3R) Идея: давайте заставим хеш-коллекции складывать все элементы в одну корзину. Особенность реализации HashSet/HashMap в том, что они использует линейное преобразование хеша, а затем как номер корзины использует остаток от деления хеша на bucketsNumber. Цитаты из оригинального кода: ~~~~~ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); /*length всегда степень двойки --- DK*/ } ~~~~~ Собственно, вся сложность...

Full text and comments »

Открыта регистрация на Volga Winter Camp 2021 Мы рады сообщить, что c 27 января по 5 февраля пройдут открытые зимние сборы по спортивному программированию Volga Winter Camp 2021, организованные НИТУ “МИСиС” совместно с Ярославским государственным университетом им. Демидова. На этот раз сборы будут индивидуальными (наличие команды не требуется) и пройдут дистанционно. К участию приглашаются студенты и учащиеся школ. Будет организован только **Дивизион C**: там мы проведем личные тематические контесты. Примерный план тем: дерево отрезков, метод Гаусса, работа со строками (хеши, КМП, Z-функция), битсеты и т.д. В рамках сборов предусмотрено 8 учебных дней и 2 выходных. Учебные дни пройдут в привычном формате: лекция->контест -> разбор -> дорешивание. Проводить занятия будут тренеры из НИТУ “МИСиС” и ЯрГУ. Лекции будут проводиться на одной из платформ для видеоконференций. Чтобы принять участие в сборах, необходимо оплатить оргвзнос 5000 рублей с человека и до 20 января пройти регистрацию по [ссылке](https://forms....

Full text and comments »

Разбор [ДВГУПС — тренировка 28](http://codeforces.com/group/mEZDf6b5KH/contest/215086) ### [А. Ярмарка оружия](http://codeforces.com/group/mEZDf6b5KH/contest/215086/problem/A) [реализация, математика] Необходимо последовательно сравнить силы наборов, если текущая сила строго больше максимальной предыдущей, то обновляем максимальную и индекс лучшего набора. Вычислить силу набора можно было в нецелых числах как (сумма $s_{i,j}$ / $w_i$), или сохранить числитель и знаменатель дроби ($sum_{s_max}$ и $w_max$) и сравнивая с текущим набором домножить обе части на ($w_max \cdot w_i$). Не стоит забывать, что суммирование $10^5$ чисел до $10^9$ приведёт к переполнению типа integer. Асимптотика: $O(n \cdot max(w_i))$ [Код в нецелых числах](http://codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29433143) [Код в целых числах](http://codeforces.com/group/mEZDf6b5KH/contest/215086/submission/29429166) ### [B. Имённо-фамильный никнейм](http://codeforces.com/group/mEZDf6b5KH/contest/215086/problem/B) [перебор, строки] Любое решение сводится к тому, чтобы мак...

Full text and comments »

Volga Winter Camp 2022 — регистрация уже открыта! Дорогие друзья! Мы рады сообщить, что **c 26 января по 6 февраля** пройдут открытые зимние сборы по спортивному программированию **Volga Winter Camp 2022**, организованные НИТУ «МИСиС» совместно с Ярославским государственным университетом им. Демидова. Сборы пройдут в двух форматах: **очном** и **дистанционном**. **Очный формат** будет организован для студентов в Ярославле на базе ЯрГУ им. Демидова. Вам доступно два варианта участия: - С проживанием в отеле &mdash; в стоимость входят проживание в отеле, учебная программа и обеды. **Оргвзнос &mdash; 35000 рублей**; - Без проживания в отеле &mdash; в стоимость входят учебная программа и обеды. **Оргвзнос &mdash; 13000 рублей**. В случае выбора очного формата участия настоятельно рекомендуем **пройти вакцинацию от COVID-19**. Возможно, во время сборов дополнительно потребуются результаты ПЦР-теста. **Дистанционный формат** представляет из себя занятия в онлайн-режиме в Zoom. К участию приглашаются как студенты, так и ...

Full text and comments »

Нужны идеи как быстро решать онлайн поиск длиннейшей общей подстроки в тексте Здравствуйте, столкнулся с такой задачей: Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 1 запрос на 10 символов): найти max длину подстроки между (pointer, cur_pos) которая повторяет строку начинающуюся с (pointer). Например, для строки (abcab[запрос префикса с 0, ответ длина 2, pos 3]cab[запрос префикса с 2, ответ длина 3, pos 5]). Т.е. для первого запроса ищем префикс abcab на участке bcab, находим ab; Для второго запроса ищем префикс cabcab на участке abcab, находим cab. Сейчас решаю ее с помощью хешей, но не устраивает производительность, на больших данных слишком много cache misses. Знает ли кто-то возможно ли решение быстрее? В теории суффиксное дерево позволяет искать max подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска. Хочется алгорит...

Full text and comments »

Полезные и не очень ссылки _Я какое-то время назад собирал полезные ссылки с codeforces, какие-то очень полезные, какие-то нет._ _Черновик был создан около года назад, а сейчас на дворе июнь 2019._ _Мой друг попросил меня скинуть ему парочку интересных статей с codeforces, и я вспомнил про этот блог._ _Поэтому этот пост опубликован)_ <spoiler summary="algorithms"> [Non-recursive segment tree tutorial](http://codeforces.com/blog/entry/1256) [user:Urbanowicz,2017-10-21] [Efficient and easy segment trees](http://codeforces.com/blog/entry/18051) [user:Al.Cash,2017-10-21] [Dynamic connectivity problem](http://codeforces.com/blog/entry/15296) [user:adamant,2017-10-21] [Суффиксное дерево. Основы. Построение за O(nlogn)](http://codeforces.com/blog/entry/11337) [user:adamant,2017-10-21] [K-я порядковая статистика на отрезке](http://codeforces.com/blog/entry/2954) [user:yarrr,2017-10-21] [[Tutorial] Sack (dsu on tree)](http://codeforces.com/blog/entry/44351) [user:arpa,2017-10-21] [Convex ...

Full text and comments »

Краудсорсинг перебора паролей Всем добрый день! Примерно полтора месяца назад я откликнулся на вакансию в одной московской компании. Мне дали "небольшое тестовое задание", в котором требовалось сбрутить пароль от небольшого (2 килобайта) зашифрованного файла. Файл состоит из шифртекста и хеша от открытого текста. Идея была такая: пароль может состоять из не более, чем 7 латинских букв различного регистра и цифр. Пароль хешируется, и его хеш используется в качестве ключа для расшифровки. Правильность расшифровки можно проверить, прогнав полученный plaintext через хеш-функцию и сравнив результат с хешом в зашифрованном файле. В чем проблема? 62^7 &mdash; это примерно 3.5 триллиона различных паролей. Если перебирать миллион паролей в секунду, то понадобится потратить на это порядка тысячи машинных часов, что абсолютно неприемлемо делать ни на своей машине (слишком долго), ни на амазоновском инстансе (слишком дорого). Собственно говоря, на тестовое задание я забил (хоть там и было сказано, что если вы не сможе...

Full text and comments »

Russian Code Cup 2015 — Qual 1 — Разбор задач <p> Всем привет! <p> Мы рады представить вашему вниманию разбор задач первого квалификационного раунда Russian Code Cup и заодно напомнить, что тем, кто не смог пройти квалификацию с первого раза, стоит принять участие во втором квалификационном раунде, который состоится [25 апреля в 12-00 по московскому времени](http://www.timeanddate.com/worldclock/fixedtime.html?msg=Russian+Code+Cup+2015+-+Qual+2&iso=20150425T12&p1=166&ah=2). <h2>Задача A. Магические карточки.</h2> <b>Идея:</b> Виталий Аксёнов.<br> <b>Реализация:</b> Григорий Шовкопляс.<br> <b>Разбор:</b> Григорий Шовкопляс.<br> <p> В задаче требуется проверить, верно ли, что Гриша в любом случае выиграет раунд, независимо от выбранных карточек. </p> <p> Рассмотрим случай, когда у Гриши будут выбраны <i>l</i> минимальных карточек, а у Димы <i>l</i> максимальных. Очевидно, что если в этом случае Гриша выиграет, то он выиграет в любом другом, так как если заменить среди выбранных любую к...

Full text and comments »

ABBYY Cup 2.0 — Hard: разбор Разбор задач будет пополняться :) ### Разбор задачи <<Развивающая игра>> Это была самая простая задача из сложного набора. Для начала заметим, что можно решать данную задачу для каждого элемента $a_i$ отдельно. То есть, если мы фиксируем некоторое $k$, то вклад каждого $a_i$ в ответ можно считать отдельно. Итак, фиксируем некоторое $a_i$. Найдем максимально возможное $j$ такое, что $i+2^j \le n$. Несложно видеть, что для всех $k < i + 2^j$ вклад $a_i$ в ответ будет равен $a_i$. То есть нужно будет сделать $a_i$ ходов с переходом в $a_{i+2^j}$. Далее найдем такое максимальное $u$, что $2^j+2^u \le n$. Заметим, что $u < j$. Также заметим, что для всех $k$ таких, что $i+2^j \le k < i+2^j+2^u$ вклад $a_i$ в ответ будет равен $2 \cdot a_i$. Далее найдем такое $q$, что $i+2^j+2^u+2^q \le n$. Итак, для каждого элемента $a_i$ мы должны найти соответствующую последовательность степеней двойки. Очевидно, что общая сложность этого процесса $O(n \cdot \log(n))$. Теперь нам нужно с...

Full text and comments »

Умножение 64-битных чисел по 64-битному модулю ассемблерной вставкой в GCC Компилятор [GCC](https://gcc.gnu.org/onlinedocs/gcc/Using-Assembly-Language-with-C.html) предоставляет возможность использовать ассемблерные вставки. Это может быть полезно например для умножения двух 64-битных чисел по 64-битному модулю. Дело в том, что умножая два 64-битных регистра, процессор сохраняет результат в паре регистров **rdx** (верхнюю часть) и **rax** (нижнюю часть). Деление же работает похожим образом: делимое берется с регистров **rdx** и **rax**, после чего в **rax** сохраняется частное, а в **rdx** остаток. Используя эти знания можно реализовать аналог следующей функции: ~~~~~ inline long long mul(long long a, long long b) { return (__int128)a * b % 1000000014018503; } ~~~~~ Вот таким образом: ~~~~~ inline long long mul(long long a, long long b) { long long res; asm( "mov %1, %%rax\n" "mov %2, %%rbx\n" "imul %%rbx\n" "mov $1000000014018503, %%rbx\n" "idiv %%rbx\n" "mov %%rdx, %0\n" :"=res"(res) :"a"(a), "b"(b) ); ...

Full text and comments »

Найти период каждой подстроки за O(N^2) На днях столкнулся с задачей, где при обработке строки мне приходится вычислять минимальный период (длина периода делит длину строки) для каждой ее подстроки. Возможно ли это как-то делать за O(N^2) или хотя бы просто быстрее, чем за O(N^3)? UPD: Ночью я хорошо поспал, поэтому, проснувшись, я вроде как нашел решение. Буду рад, если его кто-нибудь проверит: 1. Для каждого префикса `P` исходной строки `S` будем считать ДП по длине `i - j + 1` его суффикса `S[j..i]`. 2. Пусть мы нашли минимальный период подстроки `S[j..i]`, который равен `p = dp[j][i]`. Тогда предположим, что этот же период будет и у подстроки `S[j-p..i]`. Чтобы проверить наше предположение нужно только проверить равенство подстрок `S[j-p..j-1]` и `S[j..j+p-1]`, что можно сделать с помощью хэшей за O(1). ~~~~~ def is_eq_substr(beg1, end1, beg2, end2): # Тут должен быть код для хешей, но писать хеши на питоне - себя не любить, так что я просто поставлю заглушку global S return S[beg1:end1+1] ==...

Full text and comments »

IOI-2011 - заметки тренера сборной России <p></p><div>Лог первого тура:</div><div><br></div><div>Окончательная информация: у сборной России 300 баллов у Паши, 269 у Саши, и по 212 у Димы и Егора. Общее количество полных баллов - 17, участников с &gt;=243 баллами - 35, &gt;= 170 баллов имеют 99 участников. &gt;= 138 баллов - 145 участников. Кстати, ребята говорят, что на туре было подозрительно много реджаджей. Также добавлены мелкие багфиксы к решениям по итогам общения с командой.</div><div><br></div><div>12:56 - За 15 минут до конца, есть 17 участников с полным баллом, 30 участников с баллом &gt;= 243, 96 набрали &gt;= 170 баллов, 141 участник - &gt;= 138 баллов. У России пока без изменений :( Пойду встречать ребят, может, какие хорошие вести появятся.</div><div><br></div><div>12:41 - Полчаса до конца, 14 полных, 43 участника &gt;= 200, 87 участников &gt;= 170, 132 участника &gt;= 138. Россия - 300 (Паша), 237 (Саша), 212 (Дима), 190 (Егор). Эх, ещё бы немножечко!</div><div><br></div><div>12:30 - Число полных баллов выросло ...

Full text and comments »

Algoprog Meetup Contest #4: Разбор задач <p></p><h2><b>A. Подстрока</b></h2><div><br></div><div>Думаю все поймут по коду:</div><div><br></div><div><img src="http://pics.kz/s3/7a/7c/23/7a7c23461396bdc1ba1fbf19976f0d5e.jpg"><br></div><div><br></div><div><b>p.s.</b> При больших длинах можно воспользоваться алгоритмом КМП.</div><div><br></div><h2><b>B. Третья степень</b></h2><div><br></div><div>Ответ равен ${[\frac{n(n+1)}{2}]}^2$ по модулю $P$.</div><div>Единственная проблема - при вычислении&nbsp;${[\frac{n(n+1)}{2}]}^2$ происходит переполнение.</div><div>Как избежать переполнения:</div><div><ol><li>Написать длинку</li><li>Написать быстрое умножение по модулю (аналог быстрого возведения в степень)</li></ol><div>Объясняю второй способ:</div></div><div><br></div><div><br> $$ a*b = \left\{ \begin{array}{l} 2{(a*\frac{b}{2})} \\ a+a(b-1) \\ \end{array} \right. \left. \begin{array}{l} \textrm{if $b$ is even} \\ \textrm{if $b$ is odd} \\ \end{array} \right. $$ </div><div><br></div><div>Псевдокод:</div><div><br></div><div><img sr...

Full text and comments »

Russian Code Cup 2017 — Разбор задач третьей квалификации <h2>A. Электронные таблицы</h2> <p>Вычтем из <i>k</i> единицу, перейдя к нумерации столбцов с 0.</p><p>Выясним сначала, сколько символов входит в название столбца. Для этого будем последовательно отнимать от <i>k</i> степени числа 26, пока очередная степень не окажется больше оставшегося числа <i>k</i>'.</p><p>Теперь для получения имени столбца достаточно перевести <i>k</i>' в 26-ричную систему счисления с цифрами A&ndash;Z и дополнить ведущими нулями (точнее символами A) до необходимого числа символов. Это можно сделать стандартными методами языка программирования (правда при этом получатся цифры 0&ndash;9, A&ndash;P, их надо будет заменить), либо самостоятельно реализовав алгоритм перевода в систему счисления с заданным основанием.</p><p>Небольшое замечание: за день до тура один из тестеров указал, что задача B с раунда CF Beta 1 очень похожа на эту задачу. После некоторого обсуждения, учитывая, что раунд 1 на CF был очень давно, наша задача существенно проще, а хорошо подготовленно...

Full text and comments »

Работа с вещественными числами Всем привет! Имея уже некоторый опыт в программировании (хоть и олимпиадном, но все же), я, пожалуй, так и не научился нормально работать с вещественными числами. И, думаю, не только я :) Поэтому в данном блоге мне бы хотелось увидеть, например, ссылки на полезные статьи, практические рекомендации от опытных участников, ну и тому подобное. Например, как понять, когда стоит использовать eps, а когда он только мешает? Как оценивать собственно, какой надо использовать eps? Также очень интересует, как обрабатывать вещественные числа в деревьях поиска (например, map <double> или set <double>), хеш-таблицах (потому что домножение на степень 10 и приведение к long long с последующим вычислением хеш-функции не очень хорошо себя показывает) с заданной точностью. Как правильно сравнивать их при сортировке? Когда на С++ следует использовать long double, а когда double? Ну и так далее... Прикольно бы было увидеть всякие хаки с вещественными типами (ну типа [этого](http://codef...

Full text and comments »

Про gcc и std::hash Всем привет! Я не знаю, возможно, эта тема где-то уже поднималась, но быстрый гуглинг не помог. Такое ощущение, что стандартная хеш-функция для целых чисел в gcc работает плохо (для Visual C++ все нормально). Для $0 \le x \le 2^32 - 1$ ~~~~~ std::hash<int>()(x) == x std::hash<long long>()(x) == x ~~~~~ Для остальных чисел верно ~~~~~ std::hash<long long>()(x + (1LL << 32)) == std::hash<long long>()(x) ~~~~~ Например, код ниже работает в запуске на Codeforces более 10 секунд, потому что хеши всех чисел равны нулю. <spoiler summary="Код"> ~~~~~ #include <iostream> #include <unordered_set> using namespace std; int main() { unordered_set<long long> d; int n = 1e5; long long t = 1LL << 32; for (int i = 0; i < n; i++) { d.insert(i * t); } cout << d.size() << endl; } ~~~~~ </spoiler> Можно ли что-то с этим сделать без написания собственной хеш-функции?

Full text and comments »

Одна задача на составление словаря Доброго всем времени суток! Не столь давно во время отборочно-тренировочных занятий команды Украины перед Международной лингвистической олимпиадой был озвучен ряд довольно интересных задач на составление словарей. Что они из себя представляют? В общем случае задача такого плана формулируется следующим образом: _Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска слова в нем, которое определенной характеристикой._ Пример: Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска строки в нем, полностью совпадающей с строкой на входе. Очевидно, в таком случае неплохим вариантом будет стандартный словарь, в котором слова отсортированы в алфавитном порядке (тогда алгоритмом бинарного поиска мы за логарифмическое время от количества слов найдем нужную статью) (хотя на самом деле это не оптимальный вариант, но об этом чуть позже). Позже мы решили, что операцию открытия страницы с заданным номером или статьи с задан...

Full text and comments »

Интерфейс для нашего приложения под Android Всем привет! Мы с [user:ilyakor,2013-01-17] написали минималистичный клон [PasswordMaker](http://passwordmaker.org/). Вкратце идея: вместо того, чтобы помнить N разных паролей, помним один (master password), а затем, чтобы, к примеру, получить пароль для gmail.com, мы просто вычисляем H(master-password || gmail.com), где H -- криптографическая хеш-функция (мы используем [SHA-512](http://ru.wikipedia.org/wiki/SHA-2)). Это был наш первый опыт написания кода для Android, с основной логикой и интерфейсом мы худо-бедно справились ([вот](https://github.com/ilyaraz/password_generator/tree/master/android/PasswordGenerator) ссылка на github), но с дизайном полная беда. Пока это выглядит примерно так:  Может быть, найдется доброволец, который перерисует [все четыре layout'а](https://github.com/ilyaraz/password_generator/tree/master/android/PasswordGenerator/res/layout), чтобы это не выглядело настолько то...

Full text and comments »

Крылатые выражения 2:эпизод 1 <p>"Алексей" был приятно удивлён сумашедшей популярности его слов и решил не останавливацца на достигнутом.</p><p>Так и появивились "Крылатые выражения 2:эпизод 1".</p><p>Собраный материал был настолько велик что я его разделил на 3 Эпизода</p><p>Вот они:</p><p>Ароматизировано за О(n) &nbsp; &nbsp;(хотел сказать - амартизировано за О(n))</p><p>БЛИН!!!Что-ж я такое говорю? &nbsp; &nbsp;(говорил неверные вещи ,а потом понял что несёт полную пиздаболию - ой извените извените)</p><p>И вобщемто да &nbsp; &nbsp;(соглашается с собой)</p><p>Есть ли вопросы вобще? &nbsp; &nbsp;(узнаёт понили мы или нет)</p><p>Кто Что сказал? &nbsp; (палит)</p><p>Значит я совсем ошибся? &nbsp; (признаёт ошибки)</p><p>Я непобоюсь этого слова . Даже возможно , что трихотомия работает быстрее дихотомии &nbsp; &nbsp;(убеждает нахуй)</p><p>Потому что восемь отлично делится на три &nbsp; &nbsp;(КЕП невсебе)</p><p>Это не пиши сейчас. Это всё было правильно. &nbsp; &nbsp;(коректирует выход фраз)</p><p>Там производную на...

Full text and comments »

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

Full text and comments »

Russian Code Cup 2017 Elimination Round — Разбор задач <h2>A. Маленькие числа</h2> <p>Для начала разложим числа <i>a</i> и <i>b</i> на простые.</p><p>Теперь заметим, что если какое-то простое число <i>p</i> входит в произведение <i>ab</i> в степени выше первой, то мы можем либо сразу поделить оба числа на число <i>p</i>, либо если же одно из чисел не делится на <i>p</i>, то перенесём в него множитель <i>p</i> из другого числа, после чего поделим на <i>p</i>.</p><p>Очевидно, что чётность вхождения простых чисел в произведение <i>ab</i> не меняется во всех операциях. Тогда давайте оставим все простые в первой степени. Остались числа <i>p</i>₁,&thinsp;<i>p</i>₂,&thinsp;...,&thinsp;<i>p</i>_<i>n</i>. Давайте назовём произведение всех этих простых чисел <i>d</i>, <i>d</i>&thinsp;&le;&thinsp;<i>ab</i>. Утверждается, что этих простых не может быть больше 14. Если 1&thinsp;&le;&thinsp;<i>a</i>,&thinsp;<i>b</i>&thinsp;&le;&thinsp;10⁹, то произведение <i>ab</i>&thinsp;&le;&thinsp;10¹⁸, а произве...

Full text and comments »

Одна интересная задача с тренировок ИТМО. На одной из прошлых тренировок ИТМО я наткнулся на одну интересную задачу. В ней давалась строка и делались следующие запросы, перевернуть отрезок с L по R, найти LCP двух суффиксов i, j, длина строки 10⁶,^&nbsp;да и запросов тоже 10⁵. На контесте тогда я не успел добраться до нее, заступорился на более простых задачах, а в дорешивании не смог придумать как решать.<b>&nbsp;</b>Подозрительное слово<b> переворот </b>так и напрашивает декартово дерево<b>&nbsp;</b>из хешей, но как его поддерживать не очень понятно <b>=)</b><div><b><br></b></div><div><b><br></b></div><div><b><span class="Apple-style-span" style="font-weight: normal; ">В общем,&nbsp;</span><span class="Apple-style-span" style="font-weight: normal; ">Хотелось бы узнать как решается эта замечательная задача</span><span class="Apple-style-span" style="font-weight: normal; ">&nbsp;</span><span class="Apple-style-span" style="font-weight: normal; "><b>=). Жду комментариев!=)</b></span><br></b></div...

Full text and comments »

TCO Semifinal 1 <p>Люди, объсните мне кто-нибудь чем неверно мое решение 500-ки.</p><p>Решение:</p><p>Считаем хеши для всех подстрок, в мапе отмечаем сколько раз каждая подстрока встречается.</p><p>Затем все количества кидаем в отдельный массив и строим дерево хаффмана стандартным алгоритмом с кучей - достаем из кучи два элемента(самых маленьких), объединяем их, и кладём этот элемент снова в кучу. моё решение для теста &quot;abbac&quot; даёт ответ 3.4, авторское решение даёт ответ 3.6666</p><p>либо мое решение лучше чем авторское, либо оно неверно.</p><p>где ошибка?</p><p> <strong>UPD:</strong> Естественно хеши не прямо для подстрок считаю, а так чтобы строки-анаграммы имели одинаковый хеш. &nbsp;</p><p><strong>UPD2: </strong>Ага, понял за что минуса, в посте скиданова спойлится хаффман, но я только сейчас дорешивал, и пост прочел только сейчас. Кстати, мне хаффман почти сразу вспомнился.</p>

Full text and comments »

Путь к 1100(день 2) **Всем привет!** **Расскажу,что я успела сегодня сделать:** - Прочитала главу книги про хеш таблицы - порешала дивы 3 прошлых лет - закрыла почти все долги по проге(осталось задач 6-5) Сейчас буду делать задания по МОШ роботу. И ближе к вечеру подготовлюсь к завтрашнему 2 диву... рейтинг:не изменился,708(макс.969) вклад: +13 место в школе: 48 **завтра всем удачи на диве,кто пишет)**

Full text and comments »

Codeforces Round #120 (Div.2) — разбор Прежде чем опубликовать разбор задач сегодняшнего раунда, приношу извинения администрации и участникам за свою глупую ошибку, допущенную по криворукости и неопытности. Несмотря на то что раунд откровенно не удался, мы, авторы, рады, что многим участникам задачи понравились. Вот, собственно, решения: #### $A$ --- [Вася и автобусы](http://codeforces.com/contest/190/problem/A) Во-первых, если $n=0$, то ни одного ребенка по условию нельзя провезти. Значит, если при этом $m=0$, от ответ $(0, 0)$, иначе ответ $Impossible$. Теперь $n>0$. Если $m=0$, то ответ, очевидно, $(n, n)$. Иначе, чем больше родителей везет с собой по ребенку, тем меньше плата за проезд. Поэтому максимальная плата будет тогда, когда всех детей везет один родитель --- получаем ответ $n+m-1$. Если $n<=m$, то все $n$ родителей везут детей, и ровно $n$ детей не платят за проезд. Если же $n>m$, то все $m$ детей распределяются по родителям и не платят за проезд. В обоих случаях получаем минимальный ответ $max(n, ...

Full text and comments »

Anti-doublehash test. Всем привет! Многие видели [статью](/blog/entry/4898) пользователя [user:Zlobober,2014-03-24], в которой говорилось о том, что строка Туэ-Морса с ужасающей силой валит хеши по модулю 2^64. Одиночные же хэши оказались слишком небезопасными из-за парадокса Дней Рождения. Единственное оставшееся спасение от инфернальных суффиксных структур было двойное хэширование. Однако, скоро и ему прийдёт конец. Основательно изучив строку Туэ-Морса и её возможные модификации, я пришёл к выводу, что тест, ломающий даже решения с двойным хэшем **возможен**. [Здесь](http://u.to/qME6) я подробнее описал построение теста, его использование против реальных решений с различных контестов и обоснование его работы. Теперь же предлагаю пользователям codeforces обсудить, что следует делать в сложившейся ситуации. Неужели больше совсем не осталось способов решать задачи полиномиальными хэшами? У кого какие мысли по этому поводу?

Full text and comments »

Точки на прямой Банальная задача: Дано $n$ точек на плоскости. Необходимо найти наибольшее количество точек, лежащих на одной прямой. Вопрос: Решаема ли эта задача быстрее, чем за $O(n^2\log{n})$, или же $О(n^2)$ &mdash; с хеш-мэпом.

Full text and comments »

Signed и хеши 1) Можно ли использовать signed типы данных для хеширования? Не создает ли это ситауаций, когда хеши не совпадают (особенно если пользоваться всеми прелестями хешей, вроде поиска хеша подстроки за O(1))? 2) Почему в G++ операции с unsinged long long заметно тормознутее, чем с signed long long?

Full text and comments »

Создание хешей. <p>Всем привет!!!</p><p>Подскажите пожалуйста пару приёмов придумывать хорошие хеш-функции.<br /></p><p>Спасибо.</p>&nbsp;

Full text and comments »