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

Полный текст и комментарии »

Разбор задач финального раунда Яндекс.Алгоритма 2018 Интеллектуальный вендинг ------------------ Автор идеи и разработчик: [user:glebshp,2018-05-29]. Заметим, что в любом случае Аркадий не может потратить больше денег, чем у него есть, поэтому количество купленных бутылок не превзойдёт $z = \lfloor \frac{b \cdot 10^{6} + c}{r} \rfloor$. Однако, может так получится, что Аркадию придётся купить меньше бутылок, если в какой-то момент у Аркадия не будет хватать мелочи на покупку без сдачи, а нужно количество сдачи в автомате не будет. Заметим, что суммарное количество мелочи в обороте не меняется и составляет $c + d$. При этом, если $c + d \geq 999\,999$, то либо у Аркадия всегда найдётся мелочь, чтобы купить очередную бутылку, либо автомат сможет дать сдачу, если платить только с помощью банкнот. В этом случае ответ равен $z$. Если же $c + d < 999\,999$, то может быть, что у Аркадия хватает мелочи для совершения покупки без сдачи, может быть, что в автомате достаточно сдачи для покупки банкнотами, но не может быть одновременно вы...

Полный текст и комментарии »

Codeforces Round #948 (Div. 2) Editorial Мы надеемся вам понравились задачи. Задача [problem:1977A] была придумана [user:Stefan2417,2024-05-27] и подготовлена [user:alexchist,2024-05-27] Задача [problem:1977B] была придумана [user:alexchist,2024-05-27] и подготовлена [user:Stefan2417,2024-05-27]. Задача [problem:1977C] была придумана и подготовлена [user:Stefan2417,2024-05-27]. Задача [problem:1977D] была придумана и подготовлена [user:alexchist,2024-05-27] Задача [problem:1977E] была придумана и подготовлена [user:Stefan2417,2024-05-27] [problem:1977A] <spoiler summary="Tutorial"> Заметим, что одно действие с кубиком меняет четность количества кубиков в башне. Тогда если четности $n$ и $m$ не совпадают, то нельзя построить башню. Также если $n < m$ то башню тоже нельзя построить. В остальных случаях можно построить башню высоты $m$ за $m$ операций, а потом добавлять и удалять кубик, пока операции не закончатся. </spoiler> <spoiler summary="Author's code"> ```c++ #include <bits/stdc++.h>...

Полный текст и комментарии »

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

Полный текст и комментарии »

Про хеширование без домножения (ну и без деления, конечно) При решении задач на хеширование вам очень частно бывает надо уметь за $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])$. Очевидно, чтобы его вычислить, ...

Полный текст и комментарии »

Хешируемое множество со сравнением за 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$, отвеча...

Полный текст и комментарии »

Неофициальный разбор + обсуждение длинного тура Открытой олимпиады 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$ отрезков с необходимым свойством только тогда, ког...

Полный текст и комментарии »

Как тренироваться: почему для школьных олимпиад не надо учить сложные темы и решать гробы Всем доброго времени суток! На этот пост меня вдохновил [user:Wind_Eagle,2022-04-05] своим [постом](https://codeforces.me/blog/entry/101549). Этот блог является заключительным в цикле [челлендж::поготовься к респе](https://codeforces.me/blog/entry/99856). Советую перед прочтением сначала прочитать его, а также вышеописанный блог, так как данный наследуется от них. Для начала подведу итоги челленджа. Он оказался скорее неуспешным, чем успешным. Единственное, что я получил от него &mdash; опыт, который будет полезен в будущем. Итак, итоги: - Взять диплом на республике. Не выполнил, остался без диплома. Нарешал очень плохо, наконец понял, что главная проблема не столько даже лежит в программировании, сколько в психологии. Заметил очень нехорошую особенность: пришёл как на первый, так и на второй тур, все 5 часов не мог сосредоточиться, чего-то боялся (сам не знаю, чего). Из-за этого я фактически не думал, а скорее просто выписывал на листочке что-то и пытался просто реализовать...

Полный текст и комментарии »

Разбор VK Cup Round 2 [problem:532A] -------------- Доступна только английская версия разбора в английской версии поста. [problem:532B] -------------- Эту задачу можно решить с помощью динамического программирования по поддеревьям иерархии сотрудников. Обозначим за $D[v][e]$ максимальную эффективность, которую можно получить, взяв некоторое количество сотрудников из поддерева человека $v$, таким образом, чтобы их количество имело чётность $e$, и условие задачи выполнялось для всех взятых людей. Тогда нетрудно пересчитать $D[v][e]$ через детей вершины $v$ с помощью подсчёта промежуточной величины $T[i][e]$ &mdash; максимальной эффективности, которой можно достичь, пройдя первые $i$ поддеревьев вершины $v$, если чётность количества взятых людей &mdash; $e$. Важно не забыть, что бывает два случая: когда мы добавляем самого $v$, и когда мы этого не делаем. В первом случае обязательно во всех поддеревьях суммарно должно быть чётное число людей по условию, во втором же подобного не требуется. [pr...

Полный текст и комментарии »

Разбор Задач 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$. Дл...

Полный текст и комментарии »

Разбор VK Cup Round 1 Набор задач в онлайн-трансляции незначительно отличается от набора задач на основном раунде, задачи следуют в порядке, в котором они фигурируют в основном раунде. [problem:524A] ============== В задаче требовалось реализовать ровно то, что описано в условии. Фиксируем человека $x$, проходимся по всем остальным людям $y$, не дружащим с $x$, и считаем количество общих друзей $x$ и $y$. Тонкий момент №1: несмотря на то, пар друзей во вводе не более 100, самих людей может быть до 200, и можно ошибиться в выставлении размеров массивов. Тонкий момент №2: нужно аккуратно сравнивать вещественные числа. Если написать нечто вроде `common / degree >= k / 100.0`, то в силу специфики вычислений с вещественными числами, результат такой проверки может быть недетерминирован (если в какую-то из частей внесётся незначительная погрешность). Поэтому, надо либо сравнивать с точностью до некоторого `eps`, либо выполнять проверку в целых числах: `common * 100 >= degree * k`. [problem:524B] =...

Полный текст и комментарии »

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

Полный текст и комментарии »

Алгоритмы — "Цикл постов. Часть 4" Сегодняшний пост будет посвящён алгоритмам. Я составлю основной список алгоритмов, разделю их по примерному уровню сложности и расскажу, в каком порядке и как их лучше изучать. Также немного поговорю о недостатках чисто алгоритмического подхода к программированию и о том, почему одного знания алгоритмов недостаточно. Как и в предыдущем посте, я выделю следующие основные, на мой взгляд, темы: конструктивные и ad hoc задачи, строки, графы и деревья, структуры данных, динамическое программирование, комбинаторика и теория чисел, математика, жадные алгоритмы, метод отжига и открытые тесты. **Уровень I** — базовые алгоритмы, необходимые для школьных и районных (муниципальных) олимпиад, а также для написания brute-force решений. **Уровень II** — основные алгоритмы среднего уровня, необходимые для **успешного** прохождения и выступления на областных (региональных) олимпиадах. Этот уровень предполагает знание наиболее важных и базовых алгоритмов из каждой темы. **Уровень III** —...

Полный текст и комментарии »

Codeforces Round #345: editorial [problem:651A] ------------------ Автор идеи: [user:fcspartakm,2016-03-09], разработчик: [user:fcspartakm,2016-03-09]. Главной идеей решения является то, что в каждый момент времени нам нужно заряжать джойстик с самым низким уровнем заряда. По-этому мы можем просто проэмулировать процесс или вывести простую формулу за $O(1)$. [problem:651B] ------------------ Автор идеи: [user:fcspartakm,2016-03-09], разработчик: [user:fcspartakm,2016-03-09]. Давайте посмотрим на ответ, в нем будет несколько подряд идущих отрезков возрастания красоты, а между ними красота будет падать. Будем решать задачу жадно: давайте отсортируем массив значений и будем набирать возрастающие куски по очереди. Чтобы набрать очередной кусок мы идем слева-направо и среди каждого множества картин с одинаковым значением мы выберем только одно. Так будем продолжать пока картины не закончатся. Если аккуратно это реализовать, то получим решение за $O(n \log n)$. Но такое решение дает нам всю последователь...

Полный текст и комментарии »

Разбор задач Codeforces Round #242 (Div. 2) [problem:424A] В задаче требуется найти количество хомяков, которые стоят. Если оно меньше половины от общего числа, то требуется заставить некоторых сидящих хомяков встать. Иначе &mdash; требуется посадить некоторых из стоящих хомяков. Если есть выбор какого из сидячих хомяков заставить встать или какого из стоячих хомяков посадить, то можно выбрать любого. [problem:424B] Можно отсортировать все города по возрастанию расстояния до города Томска. После чего требуется найти наименьший индекс $t$, для которого общее население $p_{0} + p_{1} + \ldots + p_{t} >= 10^{6}$. Для такого $t$ значение $d_{t}$ является ответом. Ограничения на $N$ позволяют использовать сортировку с асимптотикой $O(N^{2})$ или любое другое решение с такой асимптотикой. [problem:424C] Рассмотрим следующие формулы: $$c_{i} = p_{i} \oplus (1 \mod i) \oplus (2 \mod i) \oplus \cdots \oplus (n \mod i);$$ $$Q = с_{1} \oplus с_{2} \oplus \ldots \oplus с_{n}.$$ Пусть $f_{i} = 0 \oplus 1 \oplus \ldots \...

Полный текст и комментарии »

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

Полный текст и комментарии »

Зимний отбор на кружки Tinkoff Generation Привет! В сентябре я начал преподавать алгоритмы в кружке Tinkoff Generation. Занятия в кружке бесплатные. Осенью к нам пришли 150 школьников, успешно написавших вступительный контест. Мы готовы взять больше мотивированных школьников, поэтому сделали еще и зимний отбор. Приглашаем вас принять в нем участие. :) Сейчас у нас 3 направления: алгоритмы и структуры данных, машинное и глубокое обучение и олимпиадная математика. В посте я расскажу о кружке по алгоритмам в Москве. Но кружки работают еще в Рязани и Нижнем Новгороде. А с нового года еще в Ижевске и Екатеринбурге. [Подробнее](https://fintech.tinkoff.ru/junior/about). В Москве мы разбили школьников на 3 курса. Они различаются по уровню. Занятия проходят по субботам с 16:00 по 21:00 в [штаб-квартире Тинькофф] (https://yandex.ru/maps/-/CBB0r6S6wA) в БЦ "Водный" на метро Водный стадион. Занятия проводят студенты ФКН ВШЭ и ФИВТ МФТИ, которые в школьные годы были победителями и призерами таких олимпиад как Всероссийская олимпи...

Полный текст и комментарии »

Codeforces Round 1043 (Div. 3) Разбор Мы надеемся, что вам понравился контест! Спасибо вам за участие! Для нас это второй официальный раунд, поэтому мы были бы рады услышать ваши отзывы в комментариях и в мини опросе ниже. <spoiler summary="Как вам контест?"> - Отличный: - Хороший: - Обычный: - Плохой: - Ужасный: </spoiler> <spoiler summary="Какие задачи вам понравились (можно выбрать несколько)?"> - A: - B: - C1: - C2: - D: - E: - F: - G: </spoiler> <spoiler summary="Какие задачи вам не понравились (можно выбрать несколько)?"> - A: - B: - C1: - C2: - D: - E: - F: - G: </spoiler> [problem:2132A] Идея: [user:Wi...

Полный текст и комментарии »

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

Полный текст и комментарии »

Модульная Арифметика: Удобная и простая работа Всем от новичка до профессионала приходится иметь дело с модульной арифметикой в очень широком спектре задач, от хеширования строк, до подсчета дп на деревьях (да-да, сейчас кто-то скажет, что все сводится к хэшам и комбе, но тема от этого не менее часто встречается). Мне же еще с самых первых дней в олимпиадном программировании не нравились задачи с модульной арифметикой, забудешь один раз `ans %= MOD`; И сиди с WA, и, либо минусом по задаче, либо просто трать время на дебаг, поэтому всегда приходилось внимательно расписывать формулы. Однажды меня познакомили с хэшами и удобным способом их написания: функциями необходимыми, чтобы не забыть о модулях по типу add(x, y), sub(x, y) и mul(x, y). Код, хоть и стал выглядеть гораздо лучше, но все еще оставался нечитаемым, да и задумываться о прикладных мелочах, пока считаешь математику, не хочется, поэтому логическим продолжением данной темы с функциями (имхо) будет класс модульных интов. Я предлагаю следующую реализацию: ``` c++ #in...

Полный текст и комментарии »

Анонс кружков и дистанционных туров от Тинькофф Поколение Всем привет! У нас начались вступительные экзамены в образовательные программы Тинькофф Поколение. Я приглашаю вас принять в них участие. В этом году мы хотим попробовать новый формат, который (как мы надеемся) поможет школьникам из регионов начать заниматься и повысить скил решения задач. **Upd.: хорошие новости для тех, кто любит все откладывать на последний момент: мы продлили вступительные испытания на курс «Алгоритмы и структуры данных» до 13 сентября.**  ### Для кого? Для школьников, которые увлекаются программированием и хотят достигнуть результатов на соревнованиях по информатике. Учим алгоритмическому мышлению и решению олимпиадных задач. ### Форматы проведения занятий В этом учебном году занятия будут проводиться в 3 разных форматах. #### 1. Очный Очные занятия будут проходить по субботам для школьников в Москве и Санкт-Петербурге, с 16:00 до 21:00. - Москва: Штаб-...

Полный текст и комментарии »

Кружки и дистанционные туры Tinkoff Generation для школьников Привет! Скоро начнется новый учебный год, а вместе с ним и разные олимпиадные кружки. Я хочу рассказать об одном из них, Tinkoff Generation, а если еще точнее &mdash; о курсе алгоритмов в Москве, преподавателем которого являюсь. Мы открылись в прошлом году, получили много фидбека и за лето провели работу по улучшению, так что надеемся, что в этом году кружок будет еще интереснее и полезнее. Курс алгоритмов проводится еще и в Санкт-Петербурге, Новосибирске, Рязани, Нижнем Новогороде, Екатеринбурге и Ижевске. О других направлениях и городах можете прочитать [здесь](https://fintech.tinkoff.ru/junior). Подробности можете спрашивать у Татьяны Колинковой, контакты которой даны ниже. ### Какой уровень занятий? В этом году у нас будет пять параллелей: C, B', B, A' и A. Параллели примерно соответствуют соответствующим параллелям в ЛКШ по начальному уровню учащихся, но в среднем программа сложнее, потому что занятий за год сильно больше, чем за одну смену в ЛКШ, практики тоже сильно бол...

Полный текст и комментарии »

Хеширование списков Я придумал новый алгоритм хеширования списком с помощью которого вы сможете хешировать списки, когда вам это захочется. Секрет прост: Пусть B &mdash; это dict (map) ar = list (vector) Тогда для списка состоящего из двух элементов нам надо сопоставить вот такому числу: B[pow(ar[0], 37, 1000000007) + pow(ar[1], 43, 1000000007)] = [ar[0], ar[1]] Таким образом мы сопоставили списку из 2 элементов число!!! Чем больше элементов в списке, тем мы дальше можем добавлять pow(ar[i], P_i, 1000000007), где i &mdash; след. индекс в списке (векторе), а P_i след. простое число. При таком хешировании списков (векторов) мы сможете с вероятностью 95-99% загнать задачу на OK не сильно заморачиваясь!!! Надеюсь, статья была полезна!

Полный текст и комментарии »

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

Полный текст и комментарии »

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

Полный текст и комментарии »

Timus 1423 - Задача о строке Решаю [задачу](http://acm.timus.ru/problem.aspx?space=1&num=1423) на тимусе. [Посылка](http://pastebin.com/76RgBm0e) с хешированием получает WA31 (Антихештест). Но [посылка](http://pastebin.com/tP6jm472) с двойным хешированием получает WA8... Помогите мне, пожалуйста, разобраться с двойным хешированием и наконец-таки сдать эту задачу.

Полный текст и комментарии »

Задача с тимуса Здравствуйте ! Я новичёк, хотелось бы узнать каким методом можно решить данную задачу http://acm.timus.ru/problem.aspx?space=1&num=1542 . Пробовал так &mdash; строим префиксное дерево из входных слов. Находим все слова, удовлетворяющие заданному префиксу, сортируем по частоте и выводим. Такое решение вылетало с TLE. Ещё пробовал пару способов, но всё равно получал TLE. Возможно через хеширование или дерево отрезков можно решить. Подскажите, пожалуйста, каким способом можно решить данную задачу

Полный текст и комментарии »

Хеширование бора? Есть ли какие-то способы хешировать бор? ( Я хочу чтобы у одинаковых боров был одинаковый хеш )

Полный текст и комментарии »

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

Полный текст и комментарии »