Русский
English Олимпиады
Разбор задач 3-го этапа Республиканской олимпиады школьников
17 May
Олимпиада прошла давно, но немного времени для разбора нашлось только сейчас. Архив олимпиады (задачи, тесты и решения) можно найти где обычно.
Задача А. Мухи
Задача является вариацией довольно известной математической задачи. Главное – понять, что каждая муха всегда будет двигаться строго к соседке. В этом случае скорости мух всегда будут направлены друг к другу под одним углом, а рассматривая движение с точки зрения какой-то из мух, можно заметить, что на расстояние между ней и соседкой влияет ее скорость и проекция скорости соседки на прямую, содержащую скорость этой мухи. В результате получим, что время, через которое мухи встретятся равно T = D / (V + V cos(? – 2 ? / N)). Ну а расстояние, которое пройдет каждая из мух, легко вычисляется по магической формуле: S = VT = D / (1 + cos(? – 2 ? / N)).
Задача B. Числа
Из-за небольших ограничений задачу можно было решать множеством разных способов. Один из них – воспользоваться довольно стандартным приемом в таких задачах. Сначала немного преобразуем задачу: посчитаем, сколько раз будет выписана каждая цифра от 1 до 9, а затем посчитаем сумму. Заметим, что F(A, B, Y) = F(1, B, Y) – F(1, A – 1, Y), где A, B – границы интервала, а Y – цифра, количество которой считается. Теперь научимся считать F(1, X, Y). Для этого сначала предподсчитаем D[N] = F(1, 10^N – 1, 1). Это несложно делается по рекуррентному соотношению D[N] = D[N - 1] * 10 + 10 ^ (N – 1). Далее нужно разложить X на цифры и считать количество чисел с заданным префиксом, который нужно перебирать. Здесь проще привести код:
i64 count(i64 x, int y) { i64 result = 0; int a[20]; int n = 0; if (x == 0) return 0; do { a[n++] = x % 10; x /= 10; } while (x > 0); int t = 0; for (int i = n - 1; i >= 0; --i) { for (int j = 0; j < a[i]; ++j) { if (j == y) { ++t; } result += D[i] + t * B[i]; if (j == y) { --t; } } if (a[i] == y) { ++t; } } result += t; return result; }
Разбор задач 2-го этапа Республиканской олимпиады школьников
22 January
На прошлой неделе буквально одновременно с V Международной Жаутыковской олимпиадой прошел 2-й этап Республиканской олимпиады школьников, для Алматы являющийся районным. Задачи были довольно несложные, но для полного решения требовалась некоторая сообразительность. Условия задач, тесты к ним и решения как всегда можно найти в правильном месте.
Задача A. Окружность
Во-первых, будем считать, что A1 < B1 и A2 < B2 (если это не так, то добьемся этого поменяв числа в соответствующей паре местами). Далее, нарисовав один-два случая можно заметить, что хорды будут пересекаться или касаться только в трех случаях:
- они совпадают, то есть обе вершины общие:
((A1 == A2) && (B1 == B2))
- одна вершина общая:
((A1 == A2) || (A1 == B2) || (A2 == B1) || (A2 == B2))
- вершины разные, и для каждой хорды выполняется следующее условие: если окружность разрезать по этой хорде, то вершины другой хорды должны быть в разных частях окружности:
((A1 < A2) && (A2 < B1) != (A1 < B2) && (B2 < B1))
Все решение заключается в проверке этих трех условий.
Screencast: TopCoder SRM 430
7 January
Очередной screencast – TopCoder Single Round Match 430. Не очень удачный, но демонстрирует терпение и настойчивость 
Залито на RuTube по причине временного запрета загрузки на Kiwi.
Музыка для фона отсюда: http://www.penmachine.com/podcast/.
Screencast: TopCoder SRM 425
7 December
Некоторое время назад меня попросили записать то, как я пишу SRM. Оказалось, что они забрели на блог Пети Митричева и посмотрели на его скринкасты. Но видимо его гениальные коды слишком гениальны для начинающих, и вот мне пришлось тоже заняться этим. Эта идея мне показалась интересной – предлагаю Вам тоже попробовать записать скринкаст и выложить его. Так можно хорошо посмеяться над самим собой и дать возможность другим поднабраться чуть-чуть опыта.
Встречаем 425-й SRM (смотреть лучше, развернув на весь экран):
Скачать mp4 (512×320) ~140 Mb
P.S. Кому интересно, выложил архив республиканской олимпиады школьников 2008. Читать дальше >
NEERC 2008
2 December
Долго я не писал – сначала был занят подготовкой к сабжу, затем доделываением того, что не получилось сделать из-за подготовки и вот выдалась свободная минутка.
NEERC 2008 – событие года для сотен студентов по всему СНГ. Именно к нему в течение года готовятся сильнейшие команды ВУЗов России, Беларусии, Грузии, Казахстана, Кыргызстана, Прибалтики, Армении, Азербайджана, Узбекистана и, как выяснилось в этом году, Украины. Именно здесь рождаются легенды и умирают мечты. И именно здесь меня больше не будет в качестве участника.
Этот год по правилам соревнований последний, когда я могу участвовать в ACM ICPC, и я, соответсвенно старался использовать этот шанс по полной, собрал довольно сильную команду, но, увы, не получилось. Как всегда оказалась одна задача, решение которой было понятно, но по неизвестным причинам проходить все тесты оно не хотело. Итог – 7 задач и 20 место.
Вообще, складывается такое ощущение, что насколько 2008 год удачен для России (ACM ICPC, футбол, хоккей, Евровидение), настолько же он неудачен для Казахстана и в частности для меня. Сначала совершенно глупое непрохождение отборочных раундов TCO, затем бредовый случай с визой для GCJ, теперь вот NEERC… Ну что, не будем отчаиваться, как говорится, не везет мне в картах, повезет в любви.
Далее – краткий обзор некоторых задач.
IX Всесибирская олимпиада
15 November
В этом году я в первый (и, к сожалению, последний, по крайней мере, в роли участника) раз побывал на очном туре IX Открытой Всесибирской олимпиады по программированию имени И.В.Поттосина. В прошлом году по результатам интернет-тура моя команда тоже проходила, но из-за отсутствия финансирования и времени поехать не удалось. В этом году, благодаря КБТУ и, в частности, Фуад-бею мы смогли поехать. Правда неполным составом, что сказалось на результатах.
Сначала немного об организации. По моим ощущениям, организаторам удалось одновременно сохранить “домашнюю” обстановку и провести все практически безупречно, что бывает редко. Приветливые организаторы, хорошая гостиница в двух минутах ходьбы от главного корпуса НГУ, где проходило все действие, нулевая задержка начала туров, правильно настроенные рабочие места, хорошие задачи, а также куча именитых спонсоров, быстрый бесплатный Wi-Fi ( ) и два (!!) бесплатных обеда – все это говорит само за себя.
KBTU Open, Fall 2008
22 October
19 октября в КБТУ прошел неофициальный чемпионат Алматы – KBTU Open, Fall 2008. На удивление он оказался довольно популярным – участие приняли около 50 команд ВУЗов и школ Алматы и Талдыкоргана. Неожиданной сенсацией стало то, что второе место занял ученик 11-го класса 165-го лицея Алматы Амир Тулегенов, писавший контест в одиночку, с чем его и поздравляю.
Кому интересно, выложены полные результаты, задачи и тесты олимпиады. Задачи были частично собраны из разных источников, частично составлены организаторами. Ниже представлен краткий разбор.
arti's TopCoder Tools
15 October
С самого первого контеста на TopCoder мне показалось очень неудобным полностью писать вручную класс решения. Я попробовал пару плагинов, которые можно найти на сайте, но они мне не понравились. Минусом многих плагинов (для меня) является интеграция в какую-то IDE или арену – я обычно использую только какой-нибудь редактор кода и файловый менеджер (обычно Kate + Midnight Commander, а в плохие дни Far Manager + Notepad++). Также, для тестирования решения на разных тестах с помощью обычных плагинов нужно перекомпилировать решение, что, согласитесь, в корне неправильно.
В итоге я написал свою небольшую систему скриптов, которой и делюсь с Вами. Возможности:
- генерация класса решения на основе прототипа;
- удаление unused code;
- каждый тест – отдельный файл;
- автоматическая генерация тестов из условия;
- проверка на отдельном тесте или всех тестах по очереди с проверкой правильности ответа и времени выполнения и красивой подсветкой результатов тестирования;
- копирование ваших библиотек (prewritten code) для удобства непосредственно в каталог задачи;
- скрипты написаны с использованием C++ и Bash (для Windows – bat) кроме одного на Java, так что все работает очень быстро.
Книги по олимпиадному программированию
23 September
На днях со мной связался экс-тренер казахстанской сборной IOI Алдияр Даулеткулов и предложил выложить свои книги на http://olympiads.kz, что я, собственно, и сделал: Олимпиады по информатике, Основы программирования на языке Паскаль.
От себя добавлю, что “Олимпиады по информатике” – первая книга по олимпиадному программированию, которую я прочитал. В ней достаточно понятно разобраны многие задачи, и, хотя в настоящее время они являются достаточно простыми, книга с успехом может использоваться теми, кто только начинает этот долгий и тернистый путь. Про вторую книгу ничего сказать не могу, так как с Паскалем у нас довольно натянутые отношения
P.S. Вчера решал одну задачку и написал такую вот функцию:
bool sign(int x) {
if (x) return x / abs(x);
return 0;
}
Долго не мог понять, почему у меня не работала программа. Проблема оказалась в том, что даже в этом простом коде есть два бага (хотя мне был важен только один) – попробуйте их найти
ACM ICPC: тяжело в учении – легко в бою
19 September
Предупреждение. Данная статья отражает исключительно мнение автора. Автор не претендует на верность всех утверждений. Статья предоставляется “как есть”, и автор не несет ответственности за какие бы то ни было отрицательные последствия ее прочтения и использования
Многие студенты, начав участвовать в олимпиадах, задаются вопросом: “Как добиться каких-либо значительных результатов?“. Здесь есть два варианта:
- вы – гений, в этом случае, скорее всего, вам не надо читать дальше
- вы – обычный студент, тогда единственный ответ – тренироваться, об этом и пойдет речь.
В последнее время меня несколько раз спрашивали “как надо готовиться к ACM ICPC“? В свое время и я задавал его некоторым личностям, но так и не получил вразумительного ответа. Поиск в Интернет также практически ничего не дал – видимо, известные корифеи спортивного программирования не очень любят писать. В общем пришлось, как всегда, доходить практически до всего самому, и здесь мне пригодился 7-летний опыт занятий некоторым, довольно специфическим видом спорта. Так или иначе, не без помощи руководителя и товарищей, я получил некоторый опыт, которым и постараюсь поделиться с вами – может кому-нибудь и пригодится.
