Однако лето наступило! И я хочу напомнить о таком замечательном летнем мероприятии как Internet Problem Solving Contest или IPSC. Это очень интересный интернет-контест, в котором допускается участие как в командном, так и в личном зачёте, причём школьники могут идти также в отдельном зачёте.
Среди задачи преобладают обычные output-only алгоритмические задачки, но наравне с ними встречаются мягко говоря необычные. Например, в прошлом году одна из задач была натуральным тамогочи — за правильные ответы из штрафного времени вычиталось по 20 минут, с неправильным ответом питомец помирал/убегал :-)
Сегодня, 1 июня, с 12:00 по Москве стартанёт пробный тур, который будет продолжаться сутки. Рекомендуется всем, кто не знаком с системой его написать — там тоже есть интересные и необычные задачи
Основной тур — 2 июня с 14:00 по Москве. Участвуйте, это интересно!
Наши команды:
SPbSU4 (Dmitry_Egorov, PavelKunyavskiy, yeputons)
Endeavour to Jump Together (tatyanakov, Goshish, Malinovsky239)
Ide (yarrr, caustique, ant.ermilov)
unusual (eduardische, nvilcins, gen)
Ponyville Coders (ivan.popelyshev, halyavin, iroro)
Unacceptable Solutions Inc (cmd, mastersobg, cheshire_cat)
krasprog unpredictable (oversolver, kormyshov)
Индивидуальные участники: Scorpy (Scorpy), Gerald (Gerald), homo_sapiens (Edvard), grey_wind (grey_wind)
UPD: Доступны решения.
А как там с регистрацией? Нет ограничений типа TCO (не позже чем за день)? (в лом как то сейчас регистрироваться)
По-моему не было в прошлом году — я вроде во время пробного тура зарегистрировался. Но не гарантирую.
А что там регистрироваться? Пять минут от силы.
Там вроде по английски все поэтому для меня это 10 минут. А у меня завтра экзамен.
Deadline for the registration is 2 June 2012, 15:00 UTC (i.e. you may even register during the contest).
Давайте что-ли табличку с командами заведем? Havka-papstvo (Egor pashka Petr)
Окей.
Как обычно, Progopedia (Nickolas, kit1980). М-да, на ТопКодере наша команда смотрится лучше :-)
А как зарегистрировать личный аккаунт?
Просто заполоняешь информацию про одного человека — будешь отображаться в отдельной личной табличке.
SPbSU4(Dmitry_Egorov PavelKunyavskiy yeputons)
А что случилось с Alex-Gran?
Вобщем-то ничего. Видимо этот состав более вероятен на следующий год. С точностью до поступления yeputons. Он это понимает + у него сейчас проблемы с учебой были. Он в какой-то момент предложил нам пока писать с Егором. Все вроде согласились, что это пока лучший вариант.
MSU Unpredictable: ilyakor, ilyaraz, gusakov.
UPD. Зарегал команду. Ponyville Coders: ivan.popelyshev halyavin iroro
Endeavour to Jump Together (tatyanakov, Goshish, Malinovsky239)
Ide: yarrr caustique ant.ermilov
MIPT Ababahalamaha: Abra, riadwaw, Kostroma. Правда не факт, что будем писать, ибо экзамен.
viral (al13n, eik0u, Alex_KPR)
пока что Zlobober посчитал нужным в список добавить только свою команду и хавка-папство?
У меня сегодня последний звонок был, только вернулся. Поздравь лучше, ща всё будет :-)
что ж, поздравляю! =)
но что-то ты подозрительно рано с последнего звонка вернулся ;)
Не знаю, у меня как-то было, что сначала идёт последний звонок, где в принципе только официоз, потом все экзамены, а после выдачи табелей — выпускной. Вот с него было бы подозрительно. :D
Как-то было? Так и есть у всех, не только в Латвии выпускной всю ночь празднуют:)
Scorpy: Scorpy
unusual (eduardische nvilcins gen)
Случайно обнаружила себя в списке участников :) Kharkiv+Saratov (Seyaua, sdya, natalia)
Red-headed Leage (tunyash, Skird, fdoer)
Я так до конца и не понял как что называется в американской системе образования. Как называется просто студент университета (university undergrad или grad)? Что такое primary и secondary school? UPD: кстати я видимо лично буду писать username: homo_sapiens
Я думаю что так:
Undergrad — это еще студент, а grad — выпускник.
Но это только догадки.
Блин я написал, что я grad.
Primary school — средняя школа по-нашему, Secondary school — старшая школа. University undergrad — студент, University grad — выпускник университета. Как-то так.
undergraduate — бакалавр postgraduate — магистр, доктор
А специалисты куда попадают? Куда попадают магистры и кандидаты? И кто такие мастера?
Поправил. Master — магистр. Как я понял, postgraduate — это всё после бакалавра...
Мне казалось что graduate это человек закончивший бакалавриат, а postgraduate это закончивший магистратуру. Ну а undergraduate это не получивший ничего
---- Не заметил, что ответили уже..
Такой вопрос они всегда не дают полных ограничений в задаче или это только в практисе?
Что значит полных? Иногда дают, если нет, качаешь инпут и смотришь сам.
Ну я решал задачу Р и там не было никаких ограничений на сами числа, а также на количество инпутов. А в тестах все было маленькое. И еще инпуты можно как то скачать файлами а не копипастить?
http://ipsc.ksp.sk/contests/ipsc2012/practice
Вот тут ZIP/RAR archive
Спасибо
Можно.
То что Codeforces не сохраняет newline, это так всегда было или свежий баг?
Вроде как это особенности движка разметки.
Спасибо большое!
Они иногда частично описывают ограничения. Но в принципе инпут-то у тебя на руках, всегда можно посмотреть.
Ок
Unacceptable Solutions Inc (cmd, mastersobg, cheshire_cat)
krasprog unpredictable (oversolver, kormyshov)
Чё-то я не понял. Что это за плагиат?!11
grey_wind (grey_wind)
Но, может, и не смогу.
DDTeam (tourist, Romka)
BZFlags: maksay KADR Shtrix.
ЗЫ — у кого-нить сайт грузится?
UPD: уже ок
А у меня не грузится.
Отличное расписание на сегодня.
10:00 — 11:00 — Завтрак
11:00 — 13:00 — RCC
13:00 — 14:00 — Обед
14:00 — 19:00 — IPSC
19:00 — 20:00 — Ужин
20:00 — 22:00 — TCO
11:00 — 13:00 Завтрак: RCC
14:00 — 19:00 Обед: IPSC
20:00 — 22:00 Ужин: TCO
скорее TCO на десерт :)
Я один не могу открыть условия?
Ты смог их получить? Сайт лежит.
Ни хренища нет.
У меня вообще ничего не открывается.
Я сразу жал альтернативную (mirror) ссылку на архив контеста — скачалось моментально.
The problem set window is not opening...Anyone else facing the same problem??
Кто-нибудь объяснит что за задача Б которой вроде нет но ее сдают?
Кто ж тебе такое объяснит до конца контеста-то? :-)
Понял фишку задачи. Сдал small.
MSU Tashkent: SergeyLazarev helThazar Timur_Sitdikov
Браво команде hello из Бангладеша, сдавшей B с первой попытки. Битвы Экстрасенсов ждут вас!
в В2 какой ответ, кстати?
Badness — cумма квадратов разниц по каждой цифре
Ответ (как уже написали ниже) 578472
Неправда ошибочность это
Тогда как бы мы изначально получили ошибочность 206?
Странно я и не обратил внимание. У меня тоже сначала было что-то в районе 200. Но как тогда я ее сдал? Последние 10 субмитов я делал именно с предположением этой формулы и не ошибался.
Эта формула дает разности между соседними квадратами. То есть, например, так будет выглядеть разность между плохостями чисел, отличающихся в одной цифре на 1.
Блин точно. Чет я туплю
Теорема о бесконечных обезъянах объясняет этот факт. Ник, кстати, очень в тему :о)
Блин, я обсчитался при проверке на сумму квадратов разниц и, в итоге думал совсем непонятно в какую сторону :(
578472
Вроде такой 578472
Все настолько перенапряглись, что даже никому неохота задачки обсуждать? :-)
Как в M2 построить матрицу для последнего? То, что это определитель с точностью до
знаю.
UPD: упс, а её никто не сдал. А идеи какие есть?
Кто-нибудь может поделится хардом в J для сверки?
Это вообще веселуха. Да здравствует музыкальный слух! Я сидел и полчаса записывал все эти мелодии, сдал первый тест, на второй меня не хватило :-)
А там последние три инпута в J2 набор звуков бессмысленный. Вот если были бы мелодии известные, то было бы хоть интересно поподбирать :)
А что вообще означают эти числа(samples) во входных данных?
Ну что, делимся впечатлениями?
Лично меня искренне восхитили задачи B и I. Особенно I; пароль к роботу, который не брутфорсится, а гуглится по словам hand, long, time, took и sword (забрутфорсенным по хешам для других роботов) — это шикарно. Третьей любимой задачей могла бы стать D — данные отлично загнались в MySQL, ответы не менее отлично посчитались нехитрыми выборками, но вот с эталонами не сошлись категорически. А просто WA — слишком расплывчатый вердикт, чтобы по нему толком дебажить; часа времени и трех сабмитов нам так и не хватило, чтобы понять, что ж с ними не так.
P.S. Практической пользы от Postcard Quest не замечено: от следующего места в результатах нас и так отделяло больше 60 минут пенальти.
P.P.S. Уу, так неинтересно — я нагуглила с десяток онлайн-брутфорсеров MD5, но он расшифровали только два — lame и l33t, все остальные пароли пришлось подбирать локально. Нет, мой метод мне кажется гораздо более идейным :-)
У нас пароль к роботу 7 и сам забрутфорсился.
В I пароль брутфорсился, более того, online-брутфорсами, которые легко гуглятся :)
online получилось только легкий. Зато нашел какую-то прогу, которая на графической плате что ли перебрала. Достаточно быстро, когда нашли вид пароля.
http://www.md5decryption.com/ сразу сказал на robot7 "saltmanxome7" (и еще некоторых роботов расшифровал, так что стало понятно, откуда это), но вердикт был WA (хотя on right track). Потом еще часа два возился, перебрал сотни бредовых догадок и версий, но все тот же WA. Какой же все-таки ответ?
manxome7
Ну да, как всегда.
http://en.wikipedia.org/wiki/Salt_(cryptography)
По задаче D -- у меня в простом инпуте проблема была в том, что Collation по умолчанию был какой-то регистро-независимый, а надо было устанавливать какой-нить бинарный. Когда поменял collation, зашла сразу. По второму тесту там поинтереснее выборки, и надо уже индексы строить :о)
Аналогичная проблема. Только мне такая мысль на контесте даже в голову не пришла :(
Нам пришла, но толку все равно было не особо — то ли где-то таки пропустили регистр, то ли было что-то еще.
А как там вообще в I надо было пароль находить?
Например, Extreme GPU Bruteforcer :) Находит пароли для нескольких роботов, становится понятен вид пароля <слово><номер робота> (плюс соль). Потом запускаем брут для седьмого робота. PROFIT Думаю, что можно было и без GPU.
Прочитал booklet, но так и не понял, как решать С (карты и матожидание)?
Easy. Тут все очень просто. Пусть f(n) — мат.ожидание выигрыша при игре из не более чем n раундов. Все раунды независимые, а каждое значение от 1 до 13 выпадает равновероятно, поэтому верна формула f(n)=(max(1,f(n-1))+max(2,f(n-1))+...+max(13,f(n-1)))/13 (max соответствует выбору оставить карту при себе или же продолжить игру).
Hard. Здесь уже без хранения того, какая именно осталась колода никак не обойтись. Но всего их возможно 5^13, что около 1,2 миллиардов вариантов и без дополнительных извращений это в память и разумное время не упихать никак. Но можно заметить, что как только нам выпадает карта 13, то мы сразу прекращаем игру, а поэтому нас интересуют только те колоды, в которых присутствуют все 4 карты "13", их уже не так много и массив double размера 5^12 прекрасно влезает в 2Гб доступные для 32-х битных компиляторов. А дальше обычная динамика — каждое число от 0 до 5^12-1 записанное в 5-ой системе счисления дает нам естественное соответствие между колодами и ячейками массива, переходы осуществляются аналогично формуле из easy, только надо учесть что теперь выпадение не всех карт равновероятно и также надо всегда помнить что в каждой колоде у нас есть еще 4 явно не хранимые карты "13".