А719б

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].


Решение

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

Наибольшую сложность, как вычислительную, так и идейную, представляет умножение матриц, в данном случае — возведение в квадрат. Нижеприведенная последовательность шагов позволит перемножать симметричные матрицы, используя их линейное представление в формате исходных данных.


Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]


Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.


Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.


Тесты

[latex]n[/latex] [latex]A[/latex] [latex]B[/latex] [latex]A^{2}-B^{2}[/latex]
2 1 2 5 7 4 8 -60 -48 -51
4 1 7 3 -2 3 1 9 2 8 11 4 5 11 -3 4 -7 22 1 4 0 -108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l


Тесты

Детали реализации

Задачи раздела носят обучающий характер, так что при реализации были произведены определенные обобщения, что делает решение более универсальным.

  • Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
  • Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
  • Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
  • Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

Related Images:

e-olimp 2510. Сортировка очередями

e-olimp 2510. Сортировка очередями

Постановка задачи

Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от [latex]1[/latex] до [latex]k[/latex].

По заданной последовательности различных чисел, которую требуется отсортировать, составить программу для этого устройства, которая будет выводить в выходной поток те же числа, что поступили во входной поток, но упорядоченные по возрастанию.

Программа должна содержать ровно [latex]2n[/latex] операций, каждая из которых либо читает число из входного потока и добавляет его в одну из очередей, либо извлекает число из одной из очередей и выводит его в выходной поток.

Алгоритм решения

  • Естественная идея: поддерживать линейный порядок в каждой из очередей. Для этого следует совершать обход массива очередей сортировочной машины от первой к последней, пока не будет найдена очередь, последний элемент которой не больше данного, либо отсутствует вовсе.
  • Если на одном из шагов подходящей очереди не нашлось, то на таких входных данных задача неразрешима.
  • При выводе следует выбирать очередь, содержающую текущий минимальный доступный элемент, поддерживая линейный порядок в новом массиве.

Реализация:

Ideone: http://ideone.com/X37iWg
Засчитанное решение: http://www.e-olimp.com/solutions/1935453

Детали реализации:

В коде программы активно используется библиотека [latex]algorithm[/latex] и анонимные функции,
объявленные по месту использования (внутри соответствующих методов), что позволяет минимизировать число лишних сущностей
и сделать реализацию более декларативной.

  1. find_if() — найти первый элемент участка контейнера, удовлетворяющий логическому условию. Принимает итераторы
    на левую и правую границу интересующего участка, а также унарное логическое условие. Возвращает итератор на интересующий
    элемент или итератор на область за пределами участка, если условие не выполнилось ни разу.
  2. min_element() — найти минимальный элемент на заданном участке контейнера. Принимает итераторы на левую и правую
    границу интересующего участка и двухместный предикат, задающий отношение порядка. Возвращает итератор на интересующий
    элемент или за на область за пределами участка, если условие не выполнилось ни разу (пустой контейнер, некорректный порядок).

Related Images:

e-olimp: 694. Минимум в очереди

e-olimp: 694 — Минимум в очереди

Постановка задачи

На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или удаления элемента из очереди. После выполнения каждой операции найдите наименьшее число, которое находится в очереди. Сложите все полученные числа и получите ответ. Если после некоторой операции очередь оказалась пуста, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как очередь пуста, то не выполняйте его.

Алгоритм решения

Классическая модификация очереди с поддержкой минимального хранимого значения подразумевает использование двух модифицированных стеков, один из которых служит только для проталкивания элементов в очередь, а другой — только для выталкивания. Стеки хранят пары значений: непосредственно элемент и минимальное значение в очереди на момент его добавления, что позволяет поддерживать актуальную информацию при выполнении модифицирующих запросов (см. классический труд Кормена и статью на e-maxx). Более подробно механика процесса описана в комментариях к коду.

Реализации:

На примере предложенной задачи можно наглядно продемонстрировать различия между стилем программирования, применяемым на соревнованиях, и более вдумчивым, практически ориентированным подходом.

Спортивный подход

ideone: http://ideone.com/pvVixS
засчитанное решение: http://www.e-olimp.com/solutions/1926658

Преимущества

  • Простота. Концепция воплощается буквально — даже в условиях ограниченности во времени ошибиться трудно.
  • Наглядность и компактность кода.
  • Сообразность средств цели: постановка задачи требует реализации только трех функций: проталкивания, выталкивания и взятия крайнего элемента. Каждая из них реализована по возможности наиболее простым способом.

Недостатки

  • Немасштабируемость. При необходимости внедрения дополнительного функционала или изменении постановки задачи (скажем, отсутствии явной верхней границы для входных данных) возникают проблемы, решение которых неизбежно приводит к использованию объектно-ориентированных средств языка.
  • Перерасход памяти. Реальное количество одновременно содержащихся элементов в каждом из стеков на порядок меньше, но из формулировки задания это не следует и выясняется экспериментальным путём.
  • Костыли, избыточные сущности. Отличительная черта одноразового кода. Во время соревнования требования к коду достаточно мягкие: он должен работать. Желательно — предсказуемым образом. Причем, нередко реализуется не оптимальное и логичное решение, а то, которое понимаешь. Отладка и чтение таких программ — занятие не из приятных.

Объектно-ориентированный подход

ideone: http://ideone.com/A6BpwN
засчитанное решение: http://www.e-olimp.com/solutions/1924823

Преимущества

  • Масштабируемость. Добавление функционала сводится к написанию новых методов класса.
  • Универсальность. Основа стека — односвязный список. Следовательно, его размер ограничен только объёмом доступной оперативной памяти.
  • Инкапсуляция. Реализация методов класса отделена от контекста выполняемых им функций в теле программы.
  • Польза процесса. Быстро написать более простое решение, не разобравшись в тонкостях классической реализации, почти наверняка не удастся.

Недостатки

  • Временные затраты. Использование односвязного списка порождает частные случаи, на которые придется обратить внимание. Их классификация и обработка требует вдумчивого подхода.

Related Images: