анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 25 из 26

312 
Глава 15. Дополнительные темы диапазон состоит всего из одного момента, который и является ответом на запрос. На каждом раунде мы добавляем в сеть m дорог за время O(m log n)
и проверяем, соединены ли k пар городов, за время O(k log n). Поскольку всего раундов log m, получившийся алгоритм имеет временную сложность
O((m + k) log n log m).
15.6.4. Динамическая связность
Пусть имеется граф, содержащий n вершин и m ребер. И пусть задано
q запросов вида «добавить ребро между вершинами a и b» или «удалить ребро между вершинами a и b». Требуется эффективно вычислять коли- чество компонент связности графа после каждого запроса.
На рис. 15.35 приведен пример выполнения этого процесса. Вначале граф состоит из трех компонент. Затем добавляется ребро 2–4, соединяю- щее две компоненты. После этого добавляется ребро 4–5 и удаляется реб- ро 2–5, но количество компонент не изменяется. Далее добавляется реб- ро 1–3, соединяющее две компоненты, и, наконец, удаляется ребро 2–4, в результате чего одна компонента разделяется на две.
1 2
3 4
5
the initial graph number of components: 3 1
2 3
4 5
step 1: add edge 2–4
number of components: 2 1
2 3
4 5
step 2: add edge 4–5
number of components: 2 1
2 3
4 5
step 3: remove edge 2–5
number of components: 2 1
2 3
4 5
step 4: add edge 1–3
number of components: 1 1
2 3
4 5
step 5: remove edge 2–4
number of components: 2
Начальный граф
Количество компонент: 3
Шаг 1: добавление ребра 2–4
Количество компонент: 2
Шаг 2: добавление ребра 4–5
Количество компонент: 2
Шаг 3: добавление ребра 2–5
Количество компонент: 2
Шаг 4: добавление ребра 1–3
Количество компонент: 1
Шаг 5: добавление ребра 2–4
Количество компонент: 2
Рис. 15.35. Задача о динамической связности

15.6. Разное

313
Если бы было разрешено только добавлять ребра, то задачу было бы лег- ко решить с помощью системы непересекающихся множеств, но операции удаления сильно усложняют дело. Мы обсудим алгоритм типа «разделяй и властвуй» решения пакетной версии этой задачи, когда все запросы из- вестны заранее, а результаты разрешено выдавать в любом порядке. Опи- санный алгоритм основан на работе Kopeliovich [25].
Идея заключается в том, чтобы создать временную шкалу, на которой каждое ребро представлено интервалом, показывающим моменты его вставки и удаления. Временная шкала охватывает диапазон [0, q + 1], а реб ро, добавленное на шаге a и удаленное на шаге b,представлено интер- валом [a, b]. Если ребро принадлежало начальному графу, то a = 0, а если ребро не удалялось, то b = q + 1. На рис. 15.36 показана временная шкала для нашего примера.
0 1
2 3
4 5
6 1–2 2–5 2–4 4–5 1–3
Рис. 15.36. Временная шкала вставок и удалений
Для обработки интервалов мы создадим граф, имеющий n вершин и ни одного ребра, и воспользуемся рекурсивной функцией, которая вызывает- ся с диапазоном [0, q + 1] в качестве параметра. Для диапазона [a, b] функ- ция работает следующим образом. Сначала если [a, b] целиком расположен внутри интервала некоторого ребра и это ребро не принадлежит графу, то оно добавляется в граф. Затем если размер [a, b] равен 1, то мы выводим количество компонент связности, а в противном случае рекурсивно обра- батываем диапазоны [a, k] и [k, b], где k = ⌊(a + b)/2⌋. Наконец, мы удаляем все ребра, которые были добавлены в начале обработки диапазона [a, b].
Всякий раз при добавлении или удалении ребра мы также обновляем количество компонент. Это можно сделать с помощью системы непере- секающихся множеств, поскольку мы всегда удаляем ребро, добавленное последним. Следовательно, достаточно реализовать для системы непе- ресекающихся множеств операцию отмены (undo), и это вполне возмож- но, если хранить информацию об операциях в стеке. Поскольку каждое ребро добавляется и удаляется не более O(log q)раз и каждая операция занимает время O(log n), полное время работы алгоритма составляет
O((m + q)log q log n).

314 
Глава 15. Дополнительные темы
Отметим, что, помимо подсчета количества компонент связности, мы можем поддержать любую информацию, которую можно объединить с си- стемой непересекающихся множеств. Например, можно подсчитывать ко- личество вершин в самой большой компоненте или определять двудоль- ность каждой компоненты. Эту технику можно также обобщить на другие структуры данных, поддерживающие операции вставки и отмены.

Приложение
Сведения из математики
Формулы сумм
Любую сумму вида
1 1
2 3
,
n
k
k
k
k
k
x
x
n
=
=
+
+
+ +
∑

где k – целое положительное число, можно записать в виде полинома сте- пени k + 1. Например
1
:
1
(
1)
1 2 3 2
n
x
n n
x
n
=
+
= + + + + =
∑

и
2 2
2 2
2 1
(
1)(2 1)
1 2
3 6
n
x
n n
n
x
n
=
+
+
= +
+
+ +
=
∑

Арифметической прогрессией называется такая последовательность чи- сел, что разность между любыми двумя соседними членами постоянна.
Например:
3, 7, 11, 15
– арифметическая прогрессия с разностью 4. Сумма арифметической про- грессии вычисляется по формуле
(
)
2
÷èñåë
n
n a
b
a
b
+
+ + =


,
где a – первый член, b – последний член, а n – количество членов. Напри- мер:
3 + 7 + 11 + 15 =
4 · (3 + 15) = 36.
2 1
Существует даже общая формула для таких сумм, называемая формулой Фаульхабера, но она слиш- ком сложная, чтобы приводить ее здесь.

316 
Приложение . Сведения из математики
Эта формула основана на том факте, что сумма состоит из n слагаемых и каждое слагаемое в среднем равно (a + b)/2.
Геометрической прогрессией называется такая последовательность чи- сел, что отношение любых двух соседних чисел постоянно (оно называется
знаменателем прогрессии). Например:
3, 6, 12, 24
– геометрическая прогрессия со знаменателем 2. Сумма геометрической прогрессии вычисляется по формуле
a + ak + ak
2
+ ... + b =
bk – a ,
k – 1
где a – первый член, b – последний член, а k – знаменатель. Например:
3 + 6 + 12 + 24 = 24 · 2 – 3 = 45.
2 – 1
Приведем вывод этой формулы. Положим
S = a + ak + ak
2
+ … + b.
Умножив обе стороны равенства на k, получим
kS = ak + ak
2
+ ak
3
+ … + bk,
и, решив уравнение
kS − S = bk − a,
приходим к указанной выше формуле.
Частным случаем формулы суммы геометрической прогрессии является формула
1 + 2 + 4 + 8+ … +2
n
−1
= 2
n
− 1.
Частичной суммой гармонического ряда называется сумма вида
1 1
1 1
1 1
2 3
n
x
x
n
=
= + + + +
∑

Эту сумму можно оценить сверху величиной log
2
(n)+1. Действительно, заменим каждый член 1/k числом вида 1/m, где m – ближайшая степень двойки, не превосходящая k. Например, при n = 6 получаем следующую оценку:
1 1
1 1
1 1
1 1
1 1
1 1
2 3
4 5
6 2
2 4
4 4
+ + + + + ≤ + + + + +
Эту оценку сверху можно представить в виде log
2
(n) + 1 частей (1, 2 · 1/2,
4 · 1/4 и т. д.), причем значение каждой части не превосходит 1.

Множества

317
Множества
Множеством называется набор элементов. Например, множество
X = {2, 4, 7}
содержит элементы 2, 4 и 7. Символом ∅ обозначается пустое множество, а символом |S| – размер множества S, т. е. количество элементов в нем.
Так, для приведенного выше множества |X| = 3. Если множество S содержит элемент x, то мы пишем x ∈ S, в противном случае – x ∉ S. Так, в примере выше 4 ∈ X,а 5 ∉ X.
Новые множества можно строить, применяя операции над множествами:
• пересечение A ∩ B содержит элементы, принадлежащие обоим мно- жествам A и B. Например, если A = {1, 2, 5} и B = {2, 4}, то A ∩ B = {2};
• объединение A ∪ B содержит элементы, принадлежащие либо A, либо B, либо тому и другому. Например, если A = {3, 7} и B = {2, 3, 8}, то A ∪ B = {2, 3, 7, 8};
• дополнение A содержит элементы, не принадлежащие A. Интерпре- тация дополнения зависит от универсального множества, которое содержит все возможные элементы. Например, если A = {1, 2, 5, 7}, а универсальным считается множество {1, 2, . . . , 10}, то A
= {3, 4, 6, 8,
9, 10};
• разность A\ B = A ∩ B содержит элементы, принадлежащие A, но не принадлежащие B. Отметим, что B может содержать элементы, не принадлежащие A. Например, если A = {2, 3, 7, 8} и B = {3, 5, 8}, то
A \ B = {2, 7}.
Если любой элемент A принадлежит также S, то A называется подмно-
жеством S и обозначается A ⊂ S. Любое множество S имеет 2
|S|
подмно- жеств, включая пустое множество. Например, подмножествами множества
{2, 4, 7} являются
∅, {2}, {4}, {7}, {2, 4}, {2, 7}, {4, 7} и {2, 4, 7}.
Часто встречаются множества ℕ (натуральные числа), ℤ (целые числа),
ℚ (рациональные числа) и ℝ (вещественные числа). Множество ℕ опреде- ляется одним из двух способов в зависимости от ситуации: ℕ = {0, 1, 2, ...} или ℕ = {1, 2, 3, ...}.
Для определения множеств применяется специальная нотация. Напри- мер, множество
A = {2n : n ∈ Z}
состоит из всех четных чисел, а множество
B = {x ∈ ℝ : x > 2}
– из всех вещественных чисел, больших двух.

318 
Приложение . Сведения из математики
Математическая логика
Логическое выражение может принимать одно из двух значений: true (1) или false (0). Наиболее важны следующие логические операторы: ¬ (отри-
цание), ∧ (конъюнкция), ∨ (дизъюнкция), ⇒ (импликация), ⇔ (эквиваленция).
В табл. A.1 приведены определения этих операторов.
Таблица A.1. Логические операторы
A
B
¬A
¬B
A
∧ B
A
∨ B
A
⇒ B
A
⇔ B
0 0
1 1
0 0
1 1
0 1
1 0
0 1
1 0
1 0
0 1
0 1
0 0
1 1
0 0
1 1
1 1
Выражение ¬A означает противоположность A. Выражение A ∧ B равно true, если A и B одновременно равны true, а выражение A ∨ B равно true, если либо A, либо B, либо A и B одновременно равны true.
Выражение A ⇒ B равно true, если всякий раз, как A равно true, B также равно true. Выражение A ⇔ B равно true, если A и B одновременно равны true или false.
Предикатом называется выражение, принимающее значение true или false в зависимости от параметров. Обычно предикаты обозначаются за- главными буквами. Например, можно определить предикат P(x), равный true тогда и только тогда, когда x – простое число. В соответствии с этим определением P(7) равно true, но P(8) равно false.
Квантор связывает логическое выражение с элементами множества.
Наиболее важны кванторы всеобщности ∀ (для любого) и существования ∃.
Например, запись
∀x(∃y(y < x))
означает, что для любого элемента x множества существует элемент y мно- жества – такой, что y меньше x. Это высказывание истинно для множества целых чисел, но ложно для множества натуральных чисел.
Описанная выше нотация позволяет выразить различные виды логиче- ских высказываний. Например, запись
∀x((x > 1 ∧ ¬P(x)) ⇒ (∃a(∃b(a > 1 ∧ b > 1 ∧ x = ab))))
означает, что если число x больше 1 и не является простым, то существуют числа a и b, большие 1, произведение которых равно x. Это высказывание истинно для множества целых чисел.

Логарифмы

319
Функции
Функция ⌊x⌋ округляет число x до целого с недостатком, а функция ⌈x⌉ округ- ляет x до целого с избытком. Например:
⌊3/2⌋ = 1 и ⌈3/2⌉ = 2.
Функции min(x
1
, x
2
, …, x
n
)и max(x
1
, x
2
, …, x
n
)возвращают соответственно наименьшее и наибольшее значения среди x
1
, x
2
, …, x
n
. Например:
min(1, 2, 3) = 1 и max(1, 2, 3) = 3.
Факториал n! определяется по формуле
1 1 2 3
n
x
x
n
=
= ⋅ ⋅ ⋅ ⋅
∏

Или рекуррентно:
0! = 1
n
! = n · (n − 1)!
Числа Фибоначчи возникают во многих ситуациях. Их можно опреде- лить следующим рекуррентным соотношением:
f (0) = 0
f
(1) = 1
f
(n) = f (n − 1) + f (n − 2)
Вот первые числа Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Существует также замкнутая формула для вычисления чисел Фибонач- чи, которую иногда называют формулой Бине:
(1 5)
(1 5)
( )
2 5
n
n
n
f n
+
− −
=
Логарифмы
Логарифм числа x обозначается log
b
(x), где b – основание логарифма. По определению, log
b
(x)= a тогда и только тогда, когда b
a
= x. Натуральным
логарифмом ln(x) числа x называется логарифм по основанию e ≈ 2.71828.
Полезным свойством логарифмов является тот факт, что log
b
(x) говорит о том, сколько раз нужно разделить x на b для достижения 1. Например, log
2
(32) = 5, потому что необходимо 5 делений на 2:
32 → 16 → 8 → 4 → 2 → 1.

320 
Приложение . Сведения из математики
Логарифм произведения равен сумме логарифмов:
log
b
(xy) = log
b
(x) + log
b
(y)
и, следовательно,
log
b
(x
n
) = n · log
b
(x).
Кроме того, логарифм частного равен разности логарифмов:
log
b
( )
x
y
= log
b
(x) − log
b
(y).
Приведем еще одну полезную формулу:
log ( )
log ( )
,
log ( )
b
u
b
x
x
u
=
позволяющую вычислять логарифмы по любому основанию, если извес- тен способ вычисления их по какому-то фиксированному основанию.
Системы счисления
Обычно числа записываются в десятичной системе счисления, в которой имеются цифры 0, 1, …, 9. Но существует много других систем счисления, например с основанием 2 (двоичная система), в которой есть всего две цифры: 0 и 1. Вообще, в системе счисления с основанием b в качестве цифр используются целые числа от 0 до b – 1.
Для преобразования числа из десятичной системы в систему с основа- нием b нужно делить это число на b, пока не получится нуль. Последова- тельность остатков, выписанных в обратном порядке, и является записью числа в системе с основанием b. Например, преобразуем число 17 в систе- му с основанием 3:
• 17/3 = 5 (остаток 2);
• 5/3 = 1 (остаток 2);
• 1/3 = 0 (остаток 1).
Таким образом, число 17 в системе с основанием 3 равно 122. Обрат- но, чтобы преобразовать число из системы с основанием b в десятичное, достаточно умножить каждую цифру на b
k
, где k – позиция цифры, отсчи- тываемая справа, начиная с нуля, и сложить результаты. Например, пре- образовать 122 из систем с основанием 3 в десятичную систему можно следующим образом:
1 · 3 2
+ 2 · 3 1
+ 2 · 3 0
= 17.
Количество цифр в записи целого числа x в системе с основанием b вы- числяется по формуле ⌊log
b
(x)+ 1⌋. Например, ⌊log
3
(17) + 1⌋ = 3.

Библиография
1. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algo- rithms, and Applications, Pearson, 1993.
2. A. M. Andrew. Another efficient algorithm for convex hulls in two dimen- sions. Information Processing Letters, 9 (5): 216–219, 1979.
3. M. A. Bender and M. Farach-Colton. The LCA problem revisited. Latin Amer- ican Symposium on Theoretical Informatics, 88–94, 2000.
4. J. Bentley and D.Wood. An optimal worst case algorithm for reporting inter- sections of rectangles. IEEE Transactions on Computers, C-29 (7): 571–577,
1980.
5. A. Blumer et al., The smallest automation recognizing the subwords of a text. Theoret. Comput. Sci. 40, 31–55 (1985).
6. Codeforces: On «Mo’s algorithm», http://codeforces.com/blog/entry/20032 7. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Al- gorithms, MIT Press, 2009 (3rd edition).
8. K. Diks et al. Looking for aChallenge? TheUltimate Problem Set fromthe
University of Warsaw Programming Competitions, University of Warsaw,
2012.
9. J. Edmonds, R. Karp, Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM. 19 (2), 248–264 (1972).
10. D. Fanding. A faster algorithm for shortest-path – SPFA. Journal of South- west Jiaotong University, 2, 1994.
11. P. M. Fenwick. A new data structure for cumulative frequency tables. Soft- ware: Practice and Experience, 24 (3): 327–336, 1994.
12. J. Fischer and V. Heun. Theoretical and practical improvements on the
RMQ-problem, with applications to LCA and LCE. Annual Symposium on
Combinatorial Pattern Matching, 36–48, 2006.
13. F. Le Gall. Powers of tensors and fast matrix multiplication. International
Symposium on Symbolic and Algebraic Computation, 296–303, 2014.
14. A. Grønlund and S. Pettie. Threesomes, degenerates, and love triangles. An- nual Symposium on Foundations of Computer Science, 621–630, 2014.
15. D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
16. S. Halim and F. Halim. Competitive Programming 3: The New Lower Bound of Programming Contests, 2013.
17. The InternationalOlympiad in Informatics Syllabus, https://people.ksp.
sk/

misof/ioi-syllabus/
18. D. Johnson, Efficient algorithms for shortest paths in sparse networks.
J. ACM 24 (1), 1–13 (1977).