Видеозанятие #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)