11 апреля завершился 14 Открытый чемпионат Урала по спортивному программированию, который проводится в Ургу. В этом году участников стало еще больше (приехало 54 команды), в частности, вдохновленные прошлогодней победой ИТМО (которые в этот раз приехали в составе сразу двух команд), приехали СПбГУ, а также добавились МГУ и Алтайский госуниверситет.
![](/predownloaded/da/0a/da0a853726a148a4edb85cf23d702173c34068e1.jpg)
![](/predownloaded/8d/0a/8d0af97cf3fbf245912107e30657e995e06ff84e.jpg)
Пока подводились итоги игрового тура, прошел турнир что? где? когда?. Победителей я не помню. Помню только что наша команда оказалась на последнем месте. На самом деле очень сложные вопросы после прочтения ответа становились очень простыми, что очень мне напомнило аналогичную ситуацию с олимпиадными задачками. ![](/predownloaded/95/0a/950a151579cf42e9c37d1cbce21fd9eb6edd5621.jpg)
![](/predownloaded/2b/be/2bbea80f729110747845f9f2763c1c3ec83ceaf3.jpg)
Также как и в прошлый раз, чемпионат проходил три дня. Первый день - пробный тур, затем игровой, ну и на третий день - основной тур. Организаторы как всегда старались придумать что то необычное.
Перед пробным туром, на регистрации выдали буклетики и футболки, которые на этот раз были в пределах размеров программистов, и мне наконец то досталась М-ка - на прошлом ЧУ мне досталась XL, в которую может поместится 2.5 таких программиста как я. Потом в комплект добавились ручка, блокнотик, и кубик-рубика 2х2 от яндекса. Еще выдали бумажки на которых были отмечены места с Екатеренбуржской игры Бегущий человек (лично в нашем городе это называется дозор, где люди бегают по городу, и ищут нужные места, которые не всегда просто найти), и нам сказали что эти бумажки нам завтра понадобятся. Ну мы недолго думая поняли что это вполне может быть как то связано с игровым туром, ну и решили пройтись по паре мест. На листочке было написано что особо стоит найти два места: 1 - номер подъезда в котором находится заданная квартира, в заданном доме (туда мы пойти не решились), и 2 - год изготовления люка телефонного общества, который находится на перекрестке ул Малышева и Горького. Интересно, пешеходы очень удивлялись, когда видели нас, счищающими пыль с люка на дороге, чтобы посмотреть дату его изготовления?
Потом было открытие, на котором как всегда Леонид Волков толкал свою пламенную речь. Оно прошло немного скучновато, скорее всего потому что проходило оно не в актовом зале, и поэтому было очень душно. В это время в актовом зале проходила какая то встреча оксфордских студентов, на которую я посередине встречи как ни в чем не бывало ввалился, и даже успел посидеть пару секунд, пока до меня не дошло, что я оказался не в том месте, и под возмущенные взгляды покинул зал. Правда на открытии очень порадовали слова Магаза Оразкимовича Асанова про студентов ИТМО: "В этом зале сидят чемпионы Урала и мира, и каждый из вас может их побить."
На пробном туре первой задачей шла стандартно a + b. Второй задачей была викторина, которая в этот раз была посвящена спорту. Если кто-то не знает что это такое - просто даются вопросы с четырмя вариантами ответа, и нужно просто на запрос в виде номера вопроса вывести правильный вариант ответа. Вопросы в тестах идут по порядку, так что вопросы на которые не знаешь ответа можно решать перебором. На этот раз было около 20 вопросов. Интересно было посмотреть насколько программисты дружат со спортом. Таблица результатов к сожалению не сохранилось, но видеть как некоторые команды сдают викторину с +20 было весело. На самом деле по настоящему сложным оказался только один вопрос, из-за которого мы сдали задачу с +3, "в каком виде спорта Россией была завоевана первая золотая олимпийская медаль", среди ответов было фехтование, борьба, стрельба и фигурное катание. Как потом сказал Александр Ипатов на разборе пробного тура, вопрос можно было решать так: "так как зимние олимпийские игры проходят только с 24 года, а искусственного льда раньше не было, то вариант с фигурным катанием можно было отбросить и перебрать все остальные, и получить +3." Оказывается раньше летние олимпийские игры проводились около полгода поэтому успевал появляться лед. В общем правильным в оказался вариант с фигурным катанием. Третья задача была немного нестандартной. Вася написал программу которая сортировала массив, ниже приводилась программа на Java, реализующая qsort (Вася наверно настолько суров, что пишет qsort руками), на вход подавался массив, ну и необходимо было выдать вердикт, который бы выдала тестирующая система в ответ на работу Васиной программы. Хотя эту задачу сдали 3 команды я так и не понял что же там нужно было выводить. Оказывается при переполнении стека ML случается раньше чем Stack Overflow. На разборе сказали, что вроде как вердиктов TL и ML быть вообще не должно было, но прежде чем они успели исправить тесты, задачу уже сдала команда СПбГУ Drink Less. В общем java runtime не настолько предсказуема, как я раньше думал.
На второй день проходил игровой тур, параллельно с ним проходил турнир тренеров, который представлял из себя "физическую версию" игрового тура участников. В этот раз он длился 4 с половиной часа, и каждая команда вполне могла успеть написать хоть как то работающего бота. Правда на этот раз, видимо прислушавшись к критике, правила не стали выдавать заранее. Игра оказалась очень простой, называется она прорыв, и представляет из себя разновидность игр на шахматной доске. Игра мало известная, но не так давно она заняла первое место на контесте игр для шахматной доски 8х8. Играть нужно пешками которые изначально расставлены в два ряда, и могут рубить соперника, как обычные пешки, либо ходить на одну клетку вверх, вверх-влево или вверх-вправо. Цель игры - дойти до противоположного края доски, либо убить всех пешек соперника. Лично мы немного модернизировав бота для тестирования, принялись писать что то сложное, и когда до конца осталось около получаса, и наш бот падал делая неверные ходы, мы поняли что отдебажить его будет очень сложно, поэтому бросили все и начали писать бота попроще, которого дописать так и не успели. В результате наш бот даже не вышел в плейофф.
![](/predownloaded/da/0a/da0a853726a148a4edb85cf23d702173c34068e1.jpg)
Команда СПбГУ ИТМО пишет бота Eat more который займет второе место.
Наверное мало кто, увидев данную фотографию скажет "О да там же вторая команда
Магнитогорского ГТУ"
Собственно, как я уже сказал, параллельно проходил турнир тренеров, результы:
- Андрей Лопатин
- Юрий Айдаров
- Андрей Станкевич
![](/predownloaded/8d/0a/8d0af97cf3fbf245912107e30657e995e06ff84e.jpg)
Пока подводились итоги игрового тура, прошел турнир что? где? когда?. Победителей я не помню. Помню только что наша команда оказалась на последнем месте. На самом деле очень сложные вопросы после прочтения ответа становились очень простыми, что очень мне напомнило аналогичную ситуацию с олимпиадными задачками.
Дальше прошло собственно подведение итогов игрового тура. Оно получилось довольно забавным. Очень весело было смотреть как пешка доходя до предпоследней клетки вдруг останавливалась и начинали совершатся намного менее логичные ходы. Так же очень понравилось как Алексей Самсонов а-ля Дмитрий Губерниев, коментировал каждый шаг соперников. На самом деле сразу было видно финалистов. Бот СПбГУ ИТМО как танк шел строго горизонтально постепенно продвигая свои пешки к границам соперника. А бот команды СПбГУ Drink Less (как выяснилось потом использующий рекурсию на 6 ходов вперед) легко находил брешь в защите соперника. В итоге в финале, как сказал Алексей Самсонов, мы узнали, "что нужно Больше Есть или Меньше Пить". После победы Drink Less, состоялась битва лучшего игрока среди тренеров, с лучшим ботом. По случайности им оказался Андрей Лопатин, который является тренером команды Drink Less. Правда на этот раз Андрей был поставлен в равные условия с ботом и у него так же был TL 3 секунды. В итоге после двух партий, с небольшим счетом, искусственный интеллект все же превзошел человеческий.
![](/predownloaded/95/0a/950a151579cf42e9c37d1cbce21fd9eb6edd5621.jpg)
Битва учителя с учениками, человеческого интеллекта с машинным.
Судя по результатам, сценаристы терминатора и матрицы не далеки от правды.
На третий день был назначен основной тур. Задачи на ЧУ всегда отличаются своей "необычностью", но в этот раз они по моему были более необычны чем когда либо, собственно их можно посмотреть на тимусе. Как сказал на подведении итогов Алексей Самсонов: "Стандартные задачи мы обычно стараемся давать на отборочных четвертьфиналах и чемпионатах Ургу, а на ЧУ постепенно накапливаются своеобразные гробики. В этот раз не было наверное ни одной халявной задачи, т.к. столько нулей не было очень давно." На самом деле некоторые задачи мне очень понравились, хоть они и не были сложными. Вот эта, которую сдало большинство команд, понравилась больше всех. Так же понравилась, задача метро, которая изначально задумывалась как шредер. Алексей Самсонов сказал что они хотели разрезать ее и положить в конверт частями, чтобы участник прежде чем решить задачу программно, должен был решить ее физически, но все таки авторы решили не издеваться над участниками, но лично мне идея показалась очень забавной. Была и задача, которую, как и задумывалось, никто не сдал.
На самом деле для нас этот контест оказался не очень удачным. Первой я начал решать задачу F, которая оказалась не настолько простой для меня, как кажется на первый взгляд. На самом деле, я до сих пор не могу ее сдать. WA по простой задаче в начале контеста получать очень обидно, особенно когда никакой мелкий тест не помогает выявить ошибку, а для генерации больших тестов нужно писать программу, либо возится с калькулятором, теряя драгоценное время. В итоге после нескольких неудачных посылок и изрядно упавшего настроения, на втором часе мы перешли к другим задачам. Но наверное зря я поддался упадкам настроения, потому как мозг уже на втором часе отказывался подключатся к кодингу, и пришлось писать "чисто руками", если кто понимает такое состояние. Как результат только 33 место.
На самом деле видя замороженную таблицу ни у кого не оставалось сомнений в том, что победит Питер. Стоял лишь вопрос, либо ИТМО 1 либо Drink Less. Собственно говоря финалисты игрового тура, замерли в верхних строчках таблицы. Но ИТМО 1 все таки сдали на одну задачу больше и , прошлогодние чемпионы ЧУ 2009, стали победителями ЧУ 2010.
![](/predownloaded/2b/be/2bbea80f729110747845f9f2763c1c3ec83ceaf3.jpg)
2 Место - СПбГУ Drink Less
3 Место - СПбГУ ИТМО 2
В общем Питер увез все призовые места.
Дальше прошло награждение. Награждали традиционно книгами футболками и, на этот раз музыкальными инструментами. Очень забавно было видеть Капуна с бубном, который он так долго выбирал. Ну а дальше также традиционно был фуршет, правда на этот раз было очень приятно что он проходил не в тесной аудитории а в столовой, ну и на этом ЧУ 2010 завершился.
Единственное что не понравилось, это обеды за 110 рублей. Не знаю почему цены на столовую постоянно растут (видимо на этот раз это связано с оксфордскими студентами), но стандартный суп, картошка и гуляш, салат, компот, в соседнем буфете дополняется еще одним компотом и вкусной булочкой за те же деньги, но это все мелочи.
Итог: если кто еще не был на ЧУ обязательно приезжайте на следующий год, не пожалеете, правда если хотите к нему хорошенько подготовится, нужно забивать на стандартные комплекты задач, и решать побольше задач с Тимуса, так сказать Уральской направленности.
Фоторепортаж и другие материалы можно посмотреть на официальном сайте соревнования.
Из задач больше всего понравилась задача про валяющихся роботов, которых надо объезжать. Хитро запрятанное дерево отрезков, которое я по глупости попутал с ДП. Кстати, весьма интересно, как некоторые команды сдали ее при помощи STL.
непосредственно дейкстра особо ни к чему в таких ситуациях, ибо граф получается ориентированным и ациклическим, и за меньшую сложность пишется ДП.
Когда мы писали этот контест на OpenCup'е, Дима и Саша таки добили эту F, косяк был в том, что постоянно сравнения шло с нулевым элементом массива (а не с текущим), но при этом задача проходила 16 тестов!
А метро-шредер я дописал лишь на следующий день на Тимусе - плохо голова по субботам работает, аж жуть...
[url]http://en.wikipedia.org/wiki/Breakthrough_%28board_game%29[/url]
А ещё организаторы добавили фишку, которая используется при объявлении результатов финалов ACM ICPC: они вывели на экран таблицу до заморозки, и, как это и бывает, отметили задачи, по которым у команд были попытки сдачи в течение последнего часа. Потом, начиная с нижней команды, эти попытки стали превращаться в плюсы и минусы. Выглядело шикарно, особенно для тех, наверное, кто на финал не ездил. При определении победителя команда СПбГУ (они сдали 9-ю задачу за пятый час) ненадолго обошла СПбГУ ИТМО #1(они сдали 9 задач ещё до заморозки), но, как только попытка по 10-й задаче у ИТМО превратилась в "+", стало ясно, что Кубок чемпиона Урала второй раз подряд достался команде Исенбаева.
Breakthrough
да, отличная статья
к сожалению, только сейчас руки дошли прочитать :)
http://acm.usu.ru/chu/2010/game.html
Было _ОЧЕНЬ_ обидно. Оказывается, бот нашей команды, IOSIF KOBZON, в квалификации оказался сильнее в поединках со всеми 3мя победителями игрового тура - Drink Less, Eat More, Yoshka. Надо ж было в 1/8 финала попасть на неудобного соперника! :(