Олимпиада IT-CON 2013. Разбор + Материалы + Монитор

Условия задач

A. Счастливые билеты
Суть задачи сводится к грамотному написанию двух функций:
   1. Проверка счастливости по-московски
   2. Проверка счастливости по-питерски.
Задача имела поощрительный характер.
Решение
  
B. Пагинация
Задача решается очень просто, если нумерации участников и листов вести с нуля. А именно:
n / k – номер листа
n % k – номер строки на нужном листе.
Для перехода на нумерацию с единицы можно было воспользоваться таким приемом:
(n - 1) / k + 1 – номер листа
(n - 1) % k + 1 – номер строки.
Решение

C. Палиндромы
Еще одна поощрительная задача. Суть ее сводится к написанию функции проверки строки на палиндромность:

bool is_palindrome(const string &s){
	int l = 0, r = s.size() - 1;
	while (l < r) {
		if (s[l++] != s[r--])
			return false;
	}
	return true;
}

Решение

D. Арифметическая прогрессия
Пожалуй самая сложна задача =).
Решение

E. Права пользователя
В задаче предполагалось использовать битовые операции и умение использовать структуру данных “словарь”. Ключевой момент – умение установить i-ый бит число в 1 или в 0. Более подробно о распространненных битовых операциях можно почитать здесь.
Решение
 
F. Шифр Кардано
Смысл задачи сводится к умению поворачивать квадратную матрицу по часовой стрелке.

void transposition(int mask[][SIZE]){
	int tmp[SIZE][SIZE];
	for (int i=0;i<n;++i){
		for (int j=0;j<n;++j){
			tmp[i][j] = mask[n-j-1][i];
 
		}
	}
	memcpy(mask,tmp,sizeof(tmp));
}

Решение

G. Количество секретных баз
Данную задачу можно было решать по-разному. Рассмотрим два решения.
1. Рекурсивная закраска связных областей
   По сути дела в условии задачи нет информации о том, что кроме военных баз на карте могут находиться другие объекты. Также сказано, что военные базы не пересекаются и не соприкасаются. Поэтому можно смело свести задачу к поиску количества компонент связностей, реализуя обычный DFS(поиск в глубина)
2. Поиск самой северной точки военной базы.
   Рассмотрим военную базу размером 2:

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

H. T9
Еще одна несложная задача. На первом этапе переводим строковое представление контакта в цифровой ряд, который нужно набрать. При этом нужно обратить внимание на:
1) Возможное наличие пробелов в начале и в конце строкового представления контакта. На этом моменте падали почти все решения. 
2) Нужно хранить изначальный вариант контакта для его последующего вывода
3) Корректно обрабатывать буквы в разных регистрах.
Решение

I. Пятнашки 3x3
В самом худшем случае любые пятнашки размером 3x3 можно собрать не более за 31 шаг. Данную задачу по замыслу жюри нужно было решать BFS’ом, но в последний момент было принято решение ослабить максимальное количество шагов до 15. В результате получилось, что грамотно написанный DFS без меморизации заходил в установленные лимиты.
В написании BFS’а есть интересный момент:
Как организовать быструю проверку – было ли данное состояние пройдено на предыдущих шагах. Тут можно воспользоваться двумя подходами:
  1) Ленивый. Представим поле в виде 9-ти значного числа, которое состоит из цифр поля, записанных слева направо, сверх вниз. Пустое поле будем кодировать нулем. При этом получается, что самое большое число, которое может быть 876543210, которое с успехом помещается в int. Общее количество всех валидных состояний в пятнашках равно 9! / 2 = 181440. Поэтому для хранения все предыдущих состояний можно использовать множество, в котором хранить закодированное состояние пятнашки. Используя множество можно с логарифмической сложностью ответить на вопрос – было ли данное состояние пройдено на предыщущих шагах
   2) Комбинаторный. Используем всю ту же логику что в первом пункте, но обращаем внимание на то, что общее количество всех перестановок сравнительно невелико. Если каждое закодированное состояние пятнашки представимо в виде перестановки, то состояние пятнашки можно кодировать не самой перестановкой, а ее порядковым номером в лексикографическом порядке. Получается что что можно множество заменить на битовый массив размером 9!. Сложность поиска текущего состояние среди предыдущих уменьшается до O(1).

BFS можно заменить на алгоритм A*. В качестве оценочной функции можно использовать сумму манхэттенских расстояний для каждой цифры. Начальная позиция цифры совпадает с ее позицией в текущем состоянии. Конечная позиция – позиция цифры в финальном состоянии. Чем меньше оценочная функция тем ближе данное состояние к финишу.
Решение

Арифметическое выражение
Последняя задачу на динамику. Будем последовательно будем находить ответ на задачу для каждого числа от 0 до n.
Пусть len(j) – длина арифметического выражения для числа j. Если число j нельзя набрать, то длина равна 0.

Текущее число i можно набрать тремя способами:
1) Непосредственно разрешенным набором цифр. Если можно набрать число данным способом, то второй и третий способ можно не проверять.
2) i = A + (i-A), где A принадлежит интервалу [1, i-1]. Для каждого числа из этого интервала уже найден ответ. Получается, что len(i) = len(A) + 1 + len(i-A). Заметим, что размер интервала можно сократить в два раза.
Для каждого числа нужно хранить метку: получено ли данное число с помощью плюса двух арифметических выражений.
3) i = P * (i/P), где P принадлежит интервалу [2, sqrt(i)]. При этом i делится на P без остатка. len(i) = len(P) + 1 + len(i/P). Если число P было получено оптимальным способом с использованием сложения, то его арифметическое выражение при формировании числа i нужно обрамить в скобки и добавить к len(i) число 2. Аналогично нужно поступить и с числом i/P.

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

Условия задач: http://goo.gl/ApbiPW
Полный монитор: http://goo.gl/lAAkdh
Тесты: http://goo.gl/5anx35