Олимпиада-2014: Итоги

После затяжной проверки всех тестов подведены окончательные итоги «Олимпиады по программированию». Победителем соревнования стал Дзабаев Юрий – 3 курс, гр.6, ф-т ИДиП. Второе место завоевал Курман Владимир – 4 курс, гр.7, ф-т ИДиП. Третье место разделили между собой Навроцкий Ярослав –2 курс, гр.8, ф-т ИДиП и Семеняк Павел – 3 курс, гр.6, ф-т ИДиП. 

Поздравляем победителей!
Обзор задач

Уравнение
Краткая формулировка: Найти сколько существует пар целых неотрицательных чисел x и y, при которых выполняется x + y + xy = n, где n <= 10^9
Пример входных данных: 5
Ответ: 4

Разбор:
Ошибкой всех предложенных решений является подсчет количеств пар путем прямой подстановки всех возможных значений в уравнение, что не проходит по времени, при больших значениях n. В некоторых решениях есть оптимизация, за счет сокращения диапазона перебираемых чисел, но он не может дать необходимого ускорения алгоритма.
Возможное решение:
1. Преобразовать уравнение к виду ab = n. 
x + y + xy = n
x + y*(1+x) = n
1+x+y*(1+x) = n+1
(1+x)*(y+1) = n+1
2. Найти количество пар, используя формулу комбинаторики для подсчета количества способов выбора элементов — (p1 + 1)(p2 + 1)…(pK + 1), где pi – число вхождений простого множителя в заданное число (например, у числа 18 есть два простых множителя (2 и 3) при этом 18= 2 * 3* 3, т.е. p1 = 1, p2 = 2). После чего умножить найденное количество на 2 так как ответы симметричны, и отнять 1, если одним из ответов является x=y.

Следующий палиндром
Краткая формулировка: По данному натуральному числу N определите следующее за ним натуральное число являющееся палиндромом. Число N может содержать до 100 цифр.
Пример: 4321
Ответ: 4334

Разбор:
Многие не учли, что на вход могут подаваться числа меньше 10.
Важным моментом является работа с числом N, как со строкой (или массивом символов). При этом в некоторых решениях, все равно происходил перевод к числовому типу, для произведения арифметического сложения, из-за чего происходила потеря данных.
Возможное решение:
1. Заменить правую половину чисел на симметричное отображение левой половины.
2. Если получившееся в результате число меньше исходного, то увеличить центральную цифру, после чего вновь произвести отображение.
3. Поскольку данный алгоритм не подходит для числа 9, его значение обработать отдельно.

Максимальное число
Краткая формулировка: Дан квадрат 3х3, заполненный уникальными числами от 1 до 9. Необходимо обойти все его клетки по одному разу, набрав при этом максимальное число.
Пример входных данных:
4 2 3
6 9 7
8 5 1
Ответ: 973246851

Разбор:
Ошибкой всех предложенных решений является выбор для стартовой точки – максимально числа. Обход клеток квадрата по одному разу возможен только если начинать с одой из угловых клеток или центра. В результате решения срабатывали только тогда, когда 9 располагалось в допустимых позициях, иначе возникали следующие ошибки: обход не всех клеток, выход за границы массива, зацикливание.
Возможные варианты решения:
1. Перебрать все возможные варианты. Что с учетом небольшого размера поля и условию обхода – временное выполнение не выйдет за рамки ограничений.
2. Еще более быстрого решения можно добиться, заметив, что существует только три неприводимых к друг другу способа обхода квадрата

Учитывая это, можно развернуть квадрат и при необходимости отобразить по диагонали, чтобы наибольшее из подходящих чисел было в клетке (0, 0), а следующие в (1, 0), после чего проверить три варианта обхода из угла по статическим правилам. Если наибольшее число оказалось в центре, развернуть квадрат, чтобы следующее находилось в верхней строке.

Рассадка на конференции
Последовательно расположить N возможно повторяющихся значений в одну линию, так, чтобы два одинаковых значения не располагались рядом. Если это невозможно, вывести 0. Ограничение: N <= 100
Пример: 1 1 5 3
Один из валидных ответов: 3 1 5 1

Разбор:
Причинами неправильных ответов для ряда тестов были:
Не учитывался тот факт, что на входе может быть только одно значение.
Последовательное заполнения значениями из двух максимальных множеств, дающая неправильные результаты при нечетном количестве множеств с одинаковой мощностью максимальных.
Нахлёст повторяющихся значений, при произвольном выборе начального множества значений для заполнения.
Возможное решение:
1. Привести список значений к массиву 
[a, a, .., a, b, .., b, c, .., c,…]
где a – наиболее часто встречаемое значение
b, c, .. — все остальные виды значений, идущих непрерывно (расположение по частоте встречаемости не обязательно)
2. заполнить четные индексы выходного массива первой половиной получившегося списка, нечетные – второй.
3. Перебрать массив, проверив условия различия соседних значений.
Например, пусть дан набор значений 
[‘1’, ‘1’, ‘2’, ‘3’, ‘1’, ‘1’, ‘3’, ‘3’, ‘2’]
После сортировки:
[‘1’, ‘1’, ‘1’, ‘1’, ‘2’, ‘2’, ‘3’, ‘3’, ‘3’]
После заполнения первой четных индексов выходного массива
[‘1’, , ‘1’, , ‘1’, , ‘1’, , ‘2’]
После заполнения второй:
[‘1’, ‘2’, ‘1’, ‘3’, ‘1’, ‘3’, ‘1’, ‘3’, ‘2’]

Строки
Данн набор строчек. Вывести минимальную по длинне строку, в которую будет входить каждая из них
Пример:
qwery
rysqw
ryqwe
Ответ: ryqwerysqw

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

Пример:
ab
bc
bb

Таблица:
   ab bc bb
ab 0  1   1
bc 0  0   0
bb 0  1   0

Максимальные значения:
первого столбца 0 и 0, следовательно 0-0 = 0
второго столбца 1 и 1, следовательно 1-1 = 0
третьего столбца 1 и 0, следовательно: 1-0 = 0
Таким образом первым происходит объединение ab и bb = abb. При этом таблица принимает вид
    abb bc
abb 0   1
bc  0   0
Т.е. значение строки слева меняется на результирующую строку, а части таблицы, связанные со строкой справа удаляются.
После чего операция выбора объединяемых строк повторяется.

Системы счисления
Дано основание системы счисления M (2 ≤ M ≤ 100). Необходимо найти такое минимальное натуральное число N, при котором значение 2N в десятичной системе счисления, после преобразования в систему счисления M, содержало бы все уникальные цифры системы счисления M. Если ответа не существует, вернуть «NO»
Пример: 17
Ответ: 138

Разбор:
Хранить каждый разряд числа в системе M в своем индексе массива, добавляя числа слевой стороны.
При этом необходимо реализовать собственный алгоритм возведения 2 в степень при работе в системе счисления M. Для этого достаточно сложить записанное число с самим собой и (при необходимости) вычесть основание системы счисления с переносом единицы на следующий разряд
Пример возведения 2^10 для основания 21
Степень Значения в массиве
1 [2]
2 [4]
3 [8]
4 [16]
5 [1, 11]
6 [3, 1]
7 [6, 2]
8 [12, 4]
9 [1, 3, 8]
10 [2, 6, 16]
После получения очередной степени достаточно получить число уникальных элементов в массиве, если оно равно системе счисления – необходимая степень найдена.