sharpc (sharpc) wrote,
sharpc
sharpc

Categories:
  • Music:

IPSC 2008

IPSC (International Problem Solving Contest) — ежегодный открытый чемпионат по программированию, проводимый словацким Comenius University (misof и Kº). В целом он похож на ACM ICPC: 10-15 задач (в этом году 12), система штрафов, команды до 3 человек, но есть и отличия. Есть 4 зачета: командный и личный, среди всех и среди школьников. По каждой задаче предоставляется два теста (простой — 1 балл, сложный — 2), и отправлять на сервер нужно не решение на языке программирования, а ответ к этим тестам. Большая часть задач — традиционные ACM-подобные алгоритмические задачи (в этом году 8), размер тестов к которым не позволяет решить их на бумажке, но есть и необычные, в которых надо продемонстрировать компьютерную эрудицию, разгадать зашифрованное послание и даже сыграть с сервером. (Кто-нибудь, запостите это в википедию)

Результаты IPSC 2008, в личном зачете.


A. Чья армия победит — Годзиллы или МехаГодзиллы, если на каждом такте погибает слабейший, либо (если таких несколько) слабейший из армии МехаГодзиллы?
Просто ищем максимум.

B. Найти вершины в орграфе, к которым есть пути из максимального числа вершин.
Просто DFS. В этой задаче на hard-тесте я, привыкший к тому, что TL определяется на сервере по release-версии, долго ждал ответа от debug-версии. Конечно, после перекомпиляции ответ последовал почти мгновенно :)

C. На эрудицию: найти «контрпримеры» к единственности нуля и транзитивности равенства в машинной арифметике.
Автор заверил, что примеры языконезависимые, чем и спровоцировал мое единственное бревно: я не учел, что byte апкастится к int. Мои ответы: −2147483648 == −(−2147483648); float 1000000001 == long 1000000001 (каст long → float), long 1000000001 == double (у double достаточная точность), но float 1000000001 != double 1000000001 (у float недостаточная точность).

D. Посчитать количество множеств заданного размера карт из заданного набора, где для всех свойств они либо все одинаковы, либо все разные.
Hard-тест весьма громоздкий, так что я реализовал только простой перебор для easy.

E. Посчитать стоимость минимального остовного дерева, если стоимость ребра — случайная величина, распределенная в заданном интервале.

F. Расшифровать: частотный анализ → простая замена → заглавные буквы; заменить буквы на их номера → построить множество точек с такими координатами → найти расхождение полученной фразы с канонической → найти ассоциацию с полученной фразой.
Очень жаль, что я прочитал эту задачу только после контеста, хотя именно ради таких задач и участвовал. F1 решил бы наверняка.

G. Игра с сервером: строить префиксы слов из словаря, не входящие в словарь, добавляя по одной букве, пока это возможно.

H. Расшифровать: распознать сильно заблуренную картинку и ответить на написанный вопрос.
Конечно, можно было бы размыть «образцовые» буквы, приведенные на картинке, а потом сравнивать. Но есть вариант хитрее: Photoshop → Filters → Sharpen → Smart Sharpen → Remove: Gaussian blur; Radius: указан в условии; флажок More accurate. После этого, крутя ползунок в Other → High Pass, можно рассмотреть на миниатюре сильно размытые, но все же читаемые буквы.

I. Найти минимальный вес полного графа, минимальным остовным деревом которого является заданное дерево.
Easy вполне мог быть решен простым восстановлением веса ребер, через DFS-поиск ребра максимального веса пути остовного дерева, соединяющего вершины восстанавливаемого ребра. Для hard-теста мой код работал слишком медленно (чуть ли не по 10 минут на один тест), и в попытках его оптимизации я пропустил возможность решить простые L1 и F1 (решение любого из них принесло бы мне место в top10 individual).

J. Найти минимальное число вопросов в данетке «угадай число», если один раз ведущий может соврать.

K. Найти максимальный repdigit, с количеством цифр не больше заданного, кратный какому-нибудь числу из заданного множества.
Easy может быть решен простым подсчетом модуля всех репдиджитов заданной длины по всем числам из множества.

L. Найти число расстановок N единиц по кругу, чтобы рядом было не больше K.
Стандартная задача, которую я заметил в самом конце контеста, за минуту до того, как у меня отключился интернет.


Контест ознаменовался весьма звездным составом (на финале ACM такого не встретить, разве что Petr почему-то забил) — место/баллов/штраф:

1. R+T+J 34 2240
Дримтим планеты Земля: Бартон Рейд из Гарварда, долгое время бывший таргетом и лучшим топкодером США; Томек Чайка (Польша), не нуждающийся в представлении трехкратный лидер TCO и многолетний лидер рейтинга TopCoder; Джон Детридж, таргет, сильнейший топкодер Австралии.
2. MSU MiSHa 31 2238
МГУшный дримтим: Шавлюгин, Халявин и Миняйлов.
3. SPbSU ITMO Various 28 1465
Дримтим ИТМО: Царев (чемпион ACM ICPC этого года), Исенбаев и их тренер — таргет Андрей Станкевич.
4. Three-headed Monkey 28 1974
Шведский дримтим.
5. uwr1 28 2612
Дримтим Вроцлава.
6. EigenValues 28 2645
Иранский дримтим.
7. Pointless 27 1955
Украинский дримтим (Гриненко, Симоненко и Нейтер).
8. MountainKing 27 2044
Китайский дримтим (во главе с таргетом ACRush).
9. JAM 27 2207
Команда таргетов bmerry и PaulJefferys.
10. Moo 27 2388
Дримтим МТИ во главе с Bohua Zhan (второе место на ACM ICPC этого года).
11. Moscow SU x13 26 1904
Легендарная ACM-команда МГУ последних лет.
14. MSU Unpredictable 25 2008
Самая перспективная молодая команда МГУ.

Контест показал подавляющее преимущество команд из трех человек над командами из одного человека: лидер среди индивидуалов Дмитрий Джулгаков (Украина, КПИ) набрал 24 балла и занял 20-е место в общем зачете.

Мои результаты существенно скромнее, 15 баллов, 15-е место среди индивидуалов (из 159) и 85-е в общем зачете (из 375). Однако мне удалось на 1-2 балла опередить таких сильных красных топкодеров, как Egor, asaveljevs, Ulan, rem; набрать столько же, сколько gawry; не больше, чем на 2 балла отстать от красных ardiankp, Olexiy и от ярко-желтых bjacoke001 и DmitryKlenov. В течение почти всего контеста мне удавалось быть впереди команды dfyz Dark Magic, но в конце им все-таки удалось переломить ход битвы в свою пользу и занять 77-е место :)

Thanks to misof for wonderful contest ;)

В последнее время башорг и френдлента полнится сообщениями о победах России в футболе, хоккее и на Евровидении. Мое мнение: это жалкая компенсация за второе место Пети Митричева на финале TopCoder Open.
Tags: олимпиады, программирование
Subscribe

  • Инфраструктура Python

    В ноябре 2017 я начал собирать в виде IPython Notebook сниппеты работы с разными полезными для исследовательского программирования библиотеками…

  • Теормин по STL для СП, часть 2/2

    Это продолжение части 1. <algorithm>В STL реализованы некоторые простые и часто используемые обобщенные алгоритмы. Обобщенные они потому,…

  • Теормин по STL для СП, часть 1/2

    Это теоретический минимум по STL для занимающихся спортивным программированием, подмножество возможностей стандартной библиотеки C++, полезных для…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments