Видеозанятие #0. Вводный урок

Сегодня записал первый видеоурок. Получилось таксе. Качество пока не радует. Видно, что снимал “проф”. Оказывается это очень сложно =). Надеюсь со временем из этой затеи получится что-нибудь хорошее.

Подсчет значения арифметического выражения методом рекурсивного спуска

Для начала давайте ознакомимся с одноименной статьей Матюхина Виктора Александровича.
Особо стоит обратить внимание на рисунок, который описывает суть всего подхода

Практиковать навыки по этой теме будет на задаче 451(acmp.ru)
Составим нотацию Бекуса-Наура для арифметического выражения, представленного в этой задаче.

1. <Выражение> = <Слагаемое>{(+|-)<Слагаемое>}
2. <Слагаемое> = <Множитель>{(*|/)<Множитель>}
3. <Множитель> = (+|-) <ДробноеЧисло>|<Функция>|(<Выражение>)
4. <ДробноеЧисло> = <ЦелаяЧасть>|<ЦелаяЧасть>.<ДробнаяЧасть>
5. <ЦелаяЧасть> = <Цифра>|<Цифра><Цифра>
6. <ДробнаяЧасть> = <Цифра>|<Цифра><Цифра>
7. <Функция> = <ИмяФункции>(<Выражение>)
8. <ИмяФункции> = "sin"|"cos"
9. <Цифра> = 0|1|2|3|4|5|6|7|8|9

Можно заменить, что дробное число может быть представлено либо целым числом, состоящим, как минимум из одной цифры, либо “составным”, состоящим из целой части и дробной. При этом и целая и дробная часть должна состоять, как минимум из одной цифры. Отсюда можно сделать следующие выводы:
1) Число может содержать ведущие нули (например 0056.89). Это более чем валидно.
2) Числа вида “56.” или “.89” не являются валидными. С++сный компилятор жует такое с причмокиванием, но ругается на “.” (и это не может не радовать =) ). Компилятор FreePascal понимает только “56.”. Для решения данной задачи будем считать такие числа невалидными.
3) в третьей записи знаки плюс и минус стоит расценивать исключительно как унарные.

Есть два момента, которые затрудняют решение данной задачи:
1)выражение может содержать ошибки
2)наличие разделителей(пробелов), которые могут повлиять на корректность вычислений.
В разборе к данной задаче сказано, что первым делом нужно удалить все встречающиеся пробелы. Это неверный подход, потому что пробелы могут находится в имени функции (“s in” != “sin”) или в определении числа (“5 6. 89” != “56.89”). Такие случаи нужно корректно обрабатывать.

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

Первый подход предпочтительней по следующим причинам:
1)нет возни с разделителями.
2)перевод из строки в дробное число можно возложить на встроенные функции, например sscanf.
3)работу с лексемами легко приспособить под string

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

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

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

Реализация первого подхода: 451_lex_ac.cpp
Реализация второго подхода: 451_nolex_ac.cpp Т.к. в условии задачи используются только функции косинус и синус с прототипом double func(double), то в обоих реализациях было удобно одновременно хранить указатели на функции и их строковые представления:

1. char* funcName[] = {"sin","cos",0};
2. double (*pfuncs[])(double) = {sin,cos};

* This source code was highlighted with Source Code Highlighter.

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

P.S: На самом деле метод рекурсивного спуска для этой задачи – не самое удачное решение. Здесь много подводных камней и писанины. Но для того, чтобы осознать глубину подхода и развить внимательность – самое то.

В качестве альтернативы могу предложить более простую задачу с точки зрения реализации 14F. Электронная таблица (Меньшиков)

Алгоритм Грэхэма-Эндрю

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

Реализация данного алгоритма на e-maxx’e порадовала свой лаконичностью.
Но увиденное у indy256 порадовала еще больше: 

1. vector<point> convexHull(vector<point> p) {
2.   int n = p.size();
3.   if (n <= 1)
4.     return p;
5.   int k = 0;
6.   sort(p.begin(), p.end());
7.   vector<point> q(n * 2);
8.   for (int i = 0; i < n; q[k++] = p[i++])
9.     for (; k >= 2 && !cw(q[k - 2], q[k - 1], p[i]); --k)
10.       ;
11.   for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--])
12.     for (; k > t && !cw(q[k - 2], q[k - 1], p[i]); --k)
13.       ;
14.   q.resize(k - 1 - (q[0] == q[1]));
15.   return q;
16. }

* This source code was highlighted with Source Code Highlighter.

Очень крутая реализация =). Возьмем ее на вооружение, как и весь сайт indy256

Тренировка #15 [Меньшиков]

[Условия задач]                   [Список тренировок]

15A. Игра с калькулятором
[calcgame]
Пожалуй самая сложная задача на тему последовательности в данном задачнике. Самый интересный момент – это как определить, что нужно выводить “Impossible”. Один из подходов – искать решение, пока позволяет TLE, и если такого ответа не найдено за отведенное время, то считаем, что решений нет. Как показывает практика, если асимптотика решения допустимая, то такой подход “канает”. Но все равно остается чувство сомнения и неуверенности. Вот чтобы такого чувства не было, сводим решение к поиску остатков от деления. Решение соответствует первому разбору на эту задачу.
15B. Площадь треугольника
[tria-abm]
Очень интересная задача. Немножко поколдовав сводим решение к бинарному поиску по ответу.
15C. Формирование поезда
[train-ab]
Пожалуй самая сложная задача на ДП, если пытаться решить способом, который предложил Никита Рыбак. Это способ, в котором все ответы на подзадачи для заданной длины храним в матрице [40][40][2].
15D. Стена
[wall]
Очередная задача на выпуклую оболочку. В предложенной реализации был использован алгоритм Грехема-Эндрю. Реализация самого алгоритма, была взята здесь. Она потрясла меня своей лаконичностью.
15E. Семечки
[seeds]
Признаюсь долго придумывал решение. Хотя задача по хорошему вообще несложная. И отсечение перебора довольно легко придумать.
15F. Умножение многочленов
[polymul]
Такие задачи для нас уже не должны представлять серьезной угрозы =).

[Все решения]

P.S: 17 января 2011 года в 02:43:58 по серверному времени была зачтена последняя нерешенная задача. Ну чтож, СПАСИБО автору за столь шикарный задачник.

Топологическая сортировка (Topological sort)

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

Есть ряд очень качественных публикаций на эту тему:
1) e-maxx
2) habrahabr
3) rain.ifmo.ru

Рассмотрим три задачи на эту тематику:

1) 1022(timus) Генеалогическое дерево 
Входные данные можно представить в следующем виде:

Однако тот же самый граф можно представить в другом виде:

Как можно заметить - все стрелки смотрят вправо, следовательно нужный порядок найден. В данной задаче гарантируется, что нет циклов. Это несколько упрощает задачу. Основной код программы изложен ниже: 

1. int n;
2. enum TYPE_VERTEX{WHITE,GRAY,BLACK};
3. vector<vector<int> > adj;
4. vector<TYPE_VERTEX> used;
5. ...
6. void dfs(int cur, vector<int> &ans) {
7.   used[cur] = GRAY;
8.   for (int i=0; i<adj[cur].size(); i++) {
9.     int next = adj[cur][i];
10.     // if (used[next] == GRAY) // Circle
11.     if (used[next] == WHITE)
12.       dfs(next,ans);
13.   }
14.   used[cur] = BLACK;
15.   ans.push_back(cur);
16. }
17. void topological_sort(vector<int> &ans) {
18.   for (int i=0;i<n;i++) {
19.     if (used[i] == WHITE) {
20.       dfs(i,ans);
21.     }
22.   }
23. }

* This source code was highlighted with Source Code Highlighter.

Полное решение задачи 1022(timus): здесь

2) 138(contester.tsure.ru) Квадраты из неравенств 
Задача выглядит угрожающе. Можно сразу догадаться, что всю эту таблицу нужно представить в виде графа(тестовый пример)

Логично предположить, что следующим нашим шагом будет топологическая сортировка полученного графа. При этом последовательность вершин получится в порядке возрастания. Т.е. сначала идут листья, которые не ссылаются на другие вершины, а на последнем месте – вершина, на которую не ссылается ни одна вершина:

Как видим все стрелки направлены влево, значит мы сделали все правильно. Следующее, что мы должны сделать – это определить численные значения всех 9 переменных. Для этого можем рассмотреть упрощенную задачу. Представим, что изначально наш граф состоял только из вершин B,D,A. Тогда чисто интуитивно можно присвоить B = 1, D = 2, A = 3. Если же обобщить на произвольный граф, то можно руководствоваться правилом, что численное представленное вершины равно количеству топологически меньших вершин + 1, т.е. количеству вершин левее рассматриваемой вершины в упорядоченном списке + 1. Из этих соображений получаем один из ответов на поставленную задачу:

Также не забываем грамотно обработать случай, когда граф имеет циклы.

Полный исходник на задачу 138(constester.tsure.ru): здесь (не тестировался, т.к. сервак висел во время написания поста).

3) 14F [Меньшиков]
Эта задача, демонстрирует, как можно применить топологическую сортировку в более сложной задаче. По своей сути решение данной подзадачи мало чем отличается от первой разобранной задачи(timus-1022)

Тренировка #14 [Меньшиков]

[Условия задач]                   [Список тренировок]

14A. Марковский цикл
[markovc]
Довольно интересная задача. Во-первых нужно придумать механизм быстрого перебора всех подстрок заданной длины. Лобовой алго за O(N*N) не принимается. Следует подумать как это можно сделать за O(N). Один из самых распространённых методов по решению этой подзадачи – это использование хэш-функции. Дело облегчается тем, что длина максимальной строки не превышает 12, а сама строка состоит из алфавита {A,B,C}. Следовательно любую строку такого вида можно закодировать числом <= 3^12 = 531441.
14B. Д-44
[d44]
Необычная задача. Нужно вспомнить все формулы по физике на тему “бросание тела под углом к горизонту”. Затем промоделировать движение, фиксирую только некоторые дискретные моменты времени и рассчитать в них параметры тела(например проекцию стрости на ось OX и OY). Некоторую сложность может вызвать поиск коэффициента сопротивления воздуха(k). В авторском разборе предлагается это сделать “ручками”. Признаюсь, еле хватило терпения сделать это.  В первую очередь это связано с тем, что в проверяющей системе нужно подобрать такой k, чтобы результирующая длина совпадала вплоть до метра, вместо заявленной погрешности в 10 метров.
14C. Упаковка символов
[folding]
Я очень хорошо помню, когда я был зеленым студентом, какой ужас наводила на меня эта задача. Казалось, что ее может сделать только Петр Митричев. Конечно и сейчас решение представляется каким-то волшебством, но мы уже многому научились за прошлые тренировки и думаю сделаем ее, немного подумав. Как и прошлые задачи на двумерное ДП, эту задачу решаем интервально, постепенно увеличивая интервал до длины исходной строки. Ответ восстанавливаем по аналогичной схеме, как в 13С.
14D. Пирамиды
[pyramids]
Первое мое решение было очень тяжеловесным, но корректным. Опишу его вкратце: на плоскость OXY кладем треугольник ABC. A=(0,0), B= (AB,0). Координаты точки С можно вычислить. Точка D находилась над плоскостью OXY, т.е. Zd>0. Затем нужно было найти проекцию точки D на плоскость OXY. Эта задача сводилась в нахождению точки пересечения двух отрезков. Первый отрезок был возможной проекцией точки D при повороте треугольника ABD на произвольный угол относительно плоскости OXY. Второй отрезок получался из аналогичных рассуждений с треугольником ACD. Когда увидел авторское решение, понял, что перемудрил =). Здесь привожу именно авторское решение, т.к. в данной задаче оно куда уместнее. 
14E. Поле для крикета
Суть решения в переборе нижнего левого угла(O(N*N)) и последующий подбор максимально возможной длины поля с заданным углом. Именно подбор длины является очень интересной задачей.
[cricket] O(N*N*N*logN)
Первое, что пришло в голову это подобрать длину бинарным поиском, что затребует N*logN операций для каждого угла. Общая сложность нас устраивает и при аккуратной реализации получаем законный Accepted.
[cricket] O(N*N*N) 
Но есть более изящное и красивое решение за O(N).
14F. Электронная таблица
[sprsheet]
Задача, которая требует уже неплохой подготовки. Для начала давайте вспомним/узнаем:
1) Топологическую сортировку, которая поможет в нахождении циклических ссылок.
2) Подсчет арифметического выражения методом рекурсивного спуска (второй подход).
Значения ячейки можно хранить не в матрице, а в одномерном массиве.
Я попался на тесте, на котором была циклическая ссылка, не участвующая в подсчете ячейки A1. Получил досадный штраф =).

 
[Все решения]

Тренировка #13 [Меньшиков]

[Условия задач]                   [Список тренировок]

13A. Двойная решетка
[dlattice]
В данной задаче можно использовать принцип сетки, который был описан при решении 6D. Текущая задача является логическим продолжением задач 11A и 12A, где мы имели дело с начальной ацикличной и последующей периодической частью. Здесь ацикличной части нет, но ситуация осложняется тем, что последовательности две: по оси OX и OY. Это пугать никак не должно. Обработку последовательностей будем проводить отдельно. В приведенной реализации предложен механизм обнаружения последнего элемента первого цикла. Используя этот подход, можно по аналогичной схеме решить задачу для N решеток. 
13B. Последовательность Фибоначчи
[fiboseq] Бинарный поиск
Если особо не углубляться в природу чисел Фибоначчи и пытаться решить эту задачу с наскоку, то решение с помощью бинарного поиска - то что надо. И нужно еще не забыть, что число n может быть меньше min(i,j).
[fiboseq] Формула
Если же немного углубиться в эту самую природу, то можно получить формулу, которая однозначно восстанавливает элемент рассматриваемый последовательности с индексом min(i,j) + 1. Этих данных более чем достаточно для получения ответа.
13C. Скобки (3)
[bracket3]
Очередная “волшебная” задача на ДП. Учитывая бесценный опыт, по решению прошлых задач на эту тематику, особых трудностей возникнуть не должно. На первом этапе заполняем квадратную матрицу размерностью N*N, где N – длина исходной строки, куда в элемента [i][j] кладем длину ответа на исходную задачу для интервала исходной строки с i-ого символа по j-ый. Затем в обратном порядке восстанавливаем ответ.
13D. Центр тяжести
[centgrav]
Были проблемы с мат. частью, поэтому я ознакомился с решением авторского разбора и привел реализацию по нему.
13E. Сумма произведений
Что требуется в задаче осилил не сразу. Привожу два решения 
[prodsum] O(N*N)
Суровый перебор. Такое решение не должно было пройти по задумке автора. Но сейчас мощности возросли и мы можем себе это позволить. Но стоит N увеличиться на порядок и нас может спасти только второе решение.
[prodsum] O(N)
Оказывается для получения ответа необходимо перебирать только количество нулей(z). Отсюда можно однозначно определить общее количество(k) единиц и минус единиц. Для получения количества единиц(p) необходимо решить квадратное уравнение(a*p*p + b*p + c = 0), где коэффициенты a,b,c выражаются через k и s. Весь смак в получении этого квадратного уравнения.
13F. Статическая сложность
[icomplex]
В последнее время прям нравятся задачи на разбор выражения. Здесь, как и в 12F был реализован рекурсивный спуск.


[Все решения]

Тренировка #12 [Меньшиков]

[Условия задач]                   [Список тренировок]

12A. Последовательность (2)
[seq2]
Данная задача, решается аналогично 11A. Есть два принципиальных отличия. Во-первых, цикл в данной последовательности наступит тогда, когда повторится тройка подряд идущих цифр. Поэтому, максимальное количество элементов в цикле не более 1000. Во-вторых, экспериментальным путем было выявлено, что в данной последовательности нет ацикличной начальной части, т.е. первая повторяющаяся тройка совпадает с первой тройкой последовательности. Правда второе наблюдение не было отражено в решении, сохраняя общность подхода к решению подобных задач. 
12B. Гирлянда
[garland]
Интересная задача. Долго не мог понять условия. Главное уловить принцип прогибающейся гирлянды: чем ближе находится самый нижний из узлов гирлянды к оси OX, тем ниже будет находится точка B. Подход к решению аналогичен 11B.
12C. Головоломка умножения
[mpuzzle]
Хорошее двумерное ДП. Суть подхода – ищем ответ на поставленную задачу сначала для интервала длины 2, постепенно увеличивая длину. Когда длина интервала будет равно длине первоначальной последовательности – решение найдено. Остается главное – продумать переход от меньших интервалов к более большим.
12D. Точки в многоугольнике
[polygonp]
Несложная задача, если знаешь мат.часть, которая в данном случае заключается в формуле Пика.

S = В + Г/2 − 1

где
S – Площадь многоугольника (4D),
Г – Количество целочисленных точек на границе(10D),
B – Количество целочисленных точек внутри многоугольника.
Учитывая полученную информацию, найти значение B – дело техники.
12E. Водопровод
Оба подхода делают примерно одно и тоже. Пытаемся набрать длины dx = |x2-x1| и dy = |y2-y1|, используя набор предложенных труб.
[wpipe] Рекурсивный перебор с отсечением
В первом решении сначала пытаемся набрать длину dx, и только если это удалось – пытаемся набрать длину dy из оставшихся труб. Итак как можно набрать длину dx? Предположим, что имеем дело с крайним случаем, т.е. имеется 4 типа труб. Рассмотрим формулу:

a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx

где a,b,c,d некоторые коэффициенты, которые по модулю не превышают C[0], C[1], C[2] и C[3] соответственно.
L[i] – длина трубы типа i.
C[i] – количество труб типа i. 1<=i<=K.
Перебор можно уменьшить, если перебирать только первые K-1 коэффициентов, т.к. последний K-ый коэффициент однозначно можно восстановить по первым K-1 коэффициентам и значению dx. Итак для нахождения замощения длины dx понадобится максимум 20*20*20 = 8000 итераций. Аналогично для dy - тоже 8000 итераций. Общее количество действий будет значительно меньше 8000*8000 действий.
[wpipe] Нерекурсивный перебор с использованием ДП
Второе решение начнем с того, как можно представить набор труб, которыми можно набрать определенную длину, если положить все трубы на одной прямой. Очевидно, что это будет картеж максимум из 4 элементов: {X,Y,Z,P}, где X<=C[0], Y<=C[1], Z<=C[2] и P<=C[3]. Если используем все трубы, то получаем картеж {10,10,10,10} в худшем случае. Если не используем ни одной трубы, то – {0,0,0,0}. Такой картеж можно упаковать в десятичное число равное числу XYZP в 11-ричной системе счисления. Картеж {10,10,10,10} будет эквивалентен 14640.
Если выложить все трубы в одном направлении, то получим длину не более MAX_LEN = 4*10*1000 = 40000.
Заполним рванную матрицу vector<vector<int> > dp(MAX_LEN * 2), где в dp[len] будут хранится упакованные в число наборы труб, которыми можно набрать длину len.
После чего достаточно будет взять наборы dp[dx] и dp[dy] и перебрать все возможные пары в поисках нужного ответа.
12F. Химические реакции
[chem]
Первая задача на рекурсивный спуск. Также эту задачу можно было сделать с помощью конечного автомата. Для начала нужно ознакомится с нотацией Бэкуса-Наура а дальше проявить внимательность и аккуратность. В таких задачах я практикую принцип “Тише едешь – дальше будешь”. Исходных код ответит на все остальные вопросы.

[Все решения]