19 октября в КБТУ прошел неофициальный чемпионат Алматы – KBTU Open, Fall 2008. На удивление он оказался довольно популярным – участие приняли около 50 команд ВУЗов и школ Алматы и Талдыкоргана. Неожиданной сенсацией стало то, что второе место занял ученик 11-го класса 165-го лицея Алматы Амир Тулегенов, писавший контест в одиночку, с чем его и поздравляю.

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

Задачи A, I, J

Решаются одинаково – just do it :)

Задача B. B-Matrix

К сожалению, эта задача не была решена никем. У нас было решение за O(n ^ 4), но написать его мы так и не решились – слишком уж долгим оно нам показалось. Если кто знает как решить меньше чем за 4-ю степень – буду рад, если поделитесь.

Задача C. Calendar

Стандартная игровая задача. Пусть каждая возможная дата – вершина графа. Если мы можем перейти от одной даты к другой, то делаем ориентированную дугу между соответствующими вершинами. Далее, вершину, соответствующую 2001-10-04 обозначаем проигрышной (так как, если игрок начинает ходить с этой даты, то другой игрок перед этим пришел в нее и, следовательно, выиграл). Теперь переберем все даты от 2001-10-03 до 1900-01-01 и обозначим соответствующую вершину выигрышной, если из нее есть ход хотя бы в одну проигрышную, и проигрышной, если такого хода нет. Далее просто выводим значение в соответствующей вершине.

Задача D. Different Digits

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

Составим граф, вершины которого соответствуют парам (x, y), где x – все целые числа от 0 до n – 1, а y – все подмножества цифр от 0-9, включающие не более 4 цифр (так как ответ с не более 5 цифрами нам уже известен – это само n). Из каждой вершины будет исходит 10 направленных ребер: (x, y) -> ((x * 10 + i) % n, y + {i}), где 0 <= i <= 9. Путь в этом графе от какой-то из вершин (i % n, {i}) (1 <= i <= 9) до (0, z) и будет являться искомым числом. Теперь просто надо выбрать минимальное из этих чисел.

Чтобы уменьшить количество используемой памяти с n * C(n, 4) до O(n), можно задавать подмножество разрешенных цифр и ходить в графе только по ребрам, соответствующим этим цифрам. При этом перебирать подмножества лучше всего в порядке увеличения количества задействованных цифр.

Задача E. Easy work

Тоже задача из серии «just do it», но здесь (по крайней мере по условию) может быть такой прикол, что офис изначально не пустой, и кто-то выйдет не заходя, поэтому для сбережения нервов лучше это учесть.

Задача F. Find the Sum

Научимся считать сумму от 0 до X, а затем воспользуемся тем фактом, что f(l, r) = f(r) – f(l – 1).

Пусть X состоит из n разрядов (s[0] … s[n - 1]). Пройдем по ним со старшего до младшего. Пусть:

  • i – номер текущего разряда (нумеруем с младшего);
  • t(i) = s[n - 1] + s[n - 2] + … + s[i + 1].

Тогда f(X) = sum(sum((t(i) + j) * 10 ^ i + g(i), j = 0..s[i] – 1), i = n – 1..0), где g(i) = f(10 ^ i – 1) = g(i – 1) * 10 + 45 * 10 ^ (i – 1). Вроде так, но если и не совсем так, то очень похоже :)

Задача G. Game

Все довольно просто: пусть r <= g (если это не так, поменяем r и g местами). Тогда состояние (r, g) проигрышное, если r = g = 0 или (g – r) делится на максимальную степень двойки, на которую делится r, и выигрышное в противном случае или когда r = 0. Другой вопрос, как к этому прийти :) В условиях контеста проще всего написать несложную квадратичную динамику и посмотреть на значения функции при 1 <= r, g <= 100 – закономерность видна сразу.

Задача H. Hallway

Будем перебирать радиус шара двоичным поиском.

Пусть радиус шара – R. Как определить, можно ли его протащить по этому корридору? Уменьшим окружность, соответствующую шару до точки, одновременно превратив заданные точки в окружности радиуса R и сдвинув верхнюю и нижнюю стороны корридора друг к другу, каждую на R. Можно доказать, что задача протаскивания точки здесь эквивалентна протаскиванию шара в исходной задаче.

Теперь построим граф (да, опять :) ). Вершинами будут верхняя и нижняя стороны корридора и каждый столб. Соединим вершины ребрами, если в новом рисунке они строго пересекаются (не касаются). Тогда, если существует путь в этом графе от одной стороны корридора до другой, то точку протащить нельзя.

Задача K. KBTU party

Решать задачу можно двумя способами:

  • найти хорошего математика;
  • подобрать формулу.

За отсутствием математика нам пришлось подбирать формулу, которая оказалась не такой уж и сложной. Достаточно было сгенерить значения для n, r <= 10 по очевидной формуле динамики: d[n, r] = d[n - 1, r] + (2 * n – r) * d[n - 1, r - 1]. Для n = r получим d[n, r] = n!. Для r = 1, d[n, r] = n ^ 2. Для n > r: d[n, r] = d[n - 1, r] * (n ^ 2) / ((n – r) ^ 2), или что-то вроде :) Далее надо лишь аккуратно запрограммировать последовательное вычисление d[n, r], вспомнив, как вычислять обратное число по модулю. К счастью, «совершенно случайно» число 2946859 оказалось простым :)

Постовой:

фотограф