Блог пользователя Zlobober

Автор Zlobober, 12 лет назад, По-русски

Однако лето наступило! И я хочу напомнить о таком замечательном летнем мероприятии как Internet Problem Solving Contest или IPSC. Это очень интересный интернет-контест, в котором допускается участие как в командном, так и в личном зачёте, причём школьники могут идти также в отдельном зачёте.

Среди задачи преобладают обычные output-only алгоритмические задачки, но наравне с ними встречаются мягко говоря необычные. Например, в прошлом году одна из задач была натуральным тамогочи — за правильные ответы из штрафного времени вычиталось по 20 минут, с неправильным ответом питомец помирал/убегал :-)

Сегодня, 1 июня, с 12:00 по Москве стартанёт пробный тур, который будет продолжаться сутки. Рекомендуется всем, кто не знаком с системой его написать — там тоже есть интересные и необычные задачи

Основной тур — 2 июня с 14:00 по Москве. Участвуйте, это интересно!

Наши команды:

Индивидуальные участники: Scorpy (Scorpy), Gerald (Gerald), homo_sapiens (Edvard), grey_wind (grey_wind)

UPD: Доступны решения.

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

А как там с регистрацией? Нет ограничений типа TCO (не позже чем за день)? (в лом как то сейчас регистрироваться)

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    По-моему не было в прошлом году — я вроде во время пробного тура зарегистрировался. Но не гарантирую.

    А что там регистрироваться? Пять минут от силы.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Там вроде по английски все поэтому для меня это 10 минут. А у меня завтра экзамен.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Deadline for the registration is 2 June 2012, 15:00 UTC (i.e. you may even register during the contest).

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Давайте что-ли табличку с командами заведем? Havka-papstvo (Egor pashka Petr)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А как зарегистрировать личный аккаунт?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Teams with one member will also be shown in a separate ranklist for single-person teams.

    Просто заполоняешь информацию про одного человека — будешь отображаться в отдельной личной табличке.

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    А что случилось с Alex-Gran?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +26 Проголосовать: не нравится

      Вобщем-то ничего. Видимо этот состав более вероятен на следующий год. С точностью до поступления yeputons. Он это понимает + у него сейчас проблемы с учебой были. Он в какой-то момент предложил нам пока писать с Егором. Все вроде согласились, что это пока лучший вариант.

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

MSU Unpredictable: ilyakor, ilyaraz, gusakov.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

UPD. Зарегал команду. Ponyville Coders: ivan.popelyshev halyavin iroro

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Endeavour to Jump Together (tatyanakov, Goshish, Malinovsky239)

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

MIPT Ababahalamaha: Abra, riadwaw, Kostroma. Правда не факт, что будем писать, ибо экзамен.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

viral (al13n, eik0u, Alex_KPR)

пока что Zlobober посчитал нужным в список добавить только свою команду и хавка-папство?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    У меня сегодня последний звонок был, только вернулся. Поздравь лучше, ща всё будет :-)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      что ж, поздравляю! =)

      но что-то ты подозрительно рано с последнего звонка вернулся ;)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        Не знаю, у меня как-то было, что сначала идёт последний звонок, где в принципе только официоз, потом все экзамены, а после выдачи табелей — выпускной. Вот с него было бы подозрительно. :D

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Как-то было? Так и есть у всех, не только в Латвии выпускной всю ночь празднуют:)

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Scorpy: Scorpy

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Случайно обнаружила себя в списке участников :) Kharkiv+Saratov (Seyaua, sdya, natalia)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Red-headed Leage (tunyash, Skird, fdoer)

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Я так до конца и не понял как что называется в американской системе образования. Как называется просто студент университета (university undergrad или grad)? Что такое primary и secondary school? UPD: кстати я видимо лично буду писать username: homo_sapiens

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Я думаю что так:
    Undergrad — это еще студент, а grad — выпускник.
    Но это только догадки.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Primary school — средняя школа по-нашему, Secondary school — старшая школа. University undergrad — студент, University grad — выпускник университета. Как-то так.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    undergraduate — бакалавр postgraduate — магистр, доктор

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      А специалисты куда попадают? Куда попадают магистры и кандидаты? И кто такие мастера?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Поправил. Master — магистр. Как я понял, postgraduate — это всё после бакалавра...

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    Мне казалось что graduate это человек закончивший бакалавриат, а postgraduate это закончивший магистратуру. Ну а undergraduate это не получивший ничего

    ---- Не заметил, что ответили уже..

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Такой вопрос они всегда не дают полных ограничений в задаче или это только в практисе?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Что значит полных? Иногда дают, если нет, качаешь инпут и смотришь сам.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну я решал задачу Р и там не было никаких ограничений на сами числа, а также на количество инпутов. А в тестах все было маленькое. И еще инпуты можно как то скачать файлами а не копипастить?

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

        Можно.

        • Internet Explorer: правая кнопка на линке -> Save target as...
        • Firefox: правая кнопка на линке -> Save Link As...
        • Chrome: правая кнопка на линке -> Save link as...
        • Opera: правая кнопка на линке -> Save Linked Content As...
        • Safari: правая кнопка на линке -> Download Linked File As...
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          То что Codeforces не сохраняет newline, это так всегда было или свежий баг?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

            Вроде как это особенности движка разметки.

            абзацы разделяются пустой строкой, переводы строк игнорируются;

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Они иногда частично описывают ограничения. Но в принципе инпут-то у тебя на руках, всегда можно посмотреть.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Unacceptable Solutions Inc (cmd, mastersobg, cheshire_cat)

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

krasprog unpredictable (oversolver, kormyshov)

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

grey_wind (grey_wind)

Но, может, и не смогу.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

DDTeam (tourist, Romka)

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

BZFlags: maksay KADR Shtrix.

ЗЫ — у кого-нить сайт грузится?

UPD: уже ок

»
12 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Отличное расписание на сегодня.

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я один не могу открыть условия?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem set window is not opening...Anyone else facing the same problem??

»
12 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Кто-нибудь объяснит что за задача Б которой вроде нет но ее сдают?

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Браво команде hello из Бангладеша, сдавшей B с первой попытки. Битвы Экстрасенсов ждут вас!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    в В2 какой ответ, кстати?

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 19   Проголосовать: нравится +2 Проголосовать: не нравится

      Badness — cумма квадратов разниц по каждой цифре

      Ответ (как уже написали ниже) 578472

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится -29 Проголосовать: не нравится

        Неправда ошибочность это

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Тогда как бы мы изначально получили ошибочность 206?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Странно я и не обратил внимание. У меня тоже сначала было что-то в районе 200. Но как тогда я ее сдал? Последние 10 субмитов я делал именно с предположением этой формулы и не ошибался.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Эта формула дает разности между соседними квадратами. То есть, например, так будет выглядеть разность между плохостями чисел, отличающихся в одной цифре на 1.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              Теорема о бесконечных обезъянах объясняет этот факт. Ник, кстати, очень в тему :о)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Блин, я обсчитался при проверке на сумму квадратов разниц и, в итоге думал совсем непонятно в какую сторону :(

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      578472

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Вроде такой 578472

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Все настолько перенапряглись, что даже никому неохота задачки обсуждать? :-)

Как в M2 построить матрицу для последнего? То, что это определитель с точностью до знаю.

UPD: упс, а её никто не сдал. А идеи какие есть?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кто-нибудь может поделится хардом в J для сверки?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Это вообще веселуха. Да здравствует музыкальный слух! Я сидел и полчаса записывал все эти мелодии, сдал первый тест, на второй меня не хватило :-)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А там последние три инпута в J2 набор звуков бессмысленный. Вот если были бы мелодии известные, то было бы хоть интересно поподбирать :)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А что вообще означают эти числа(samples) во входных данных?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Ну что, делимся впечатлениями?

Лично меня искренне восхитили задачи B и I. Особенно I; пароль к роботу, который не брутфорсится, а гуглится по словам hand, long, time, took и sword (забрутфорсенным по хешам для других роботов) — это шикарно. Третьей любимой задачей могла бы стать D — данные отлично загнались в MySQL, ответы не менее отлично посчитались нехитрыми выборками, но вот с эталонами не сошлись категорически. А просто WA — слишком расплывчатый вердикт, чтобы по нему толком дебажить; часа времени и трех сабмитов нам так и не хватило, чтобы понять, что ж с ними не так.

P.S. Практической пользы от Postcard Quest не замечено: от следующего места в результатах нас и так отделяло больше 60 минут пенальти.

P.P.S. Уу, так неинтересно — я нагуглила с десяток онлайн-брутфорсеров MD5, но он расшифровали только два — lame и l33t, все остальные пароли пришлось подбирать локально. Нет, мой метод мне кажется гораздо более идейным :-)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У нас пароль к роботу 7 и сам забрутфорсился.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В I пароль брутфорсился, более того, online-брутфорсами, которые легко гуглятся :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      online получилось только легкий. Зато нашел какую-то прогу, которая на графической плате что ли перебрала. Достаточно быстро, когда нашли вид пароля.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    http://www.md5decryption.com/ сразу сказал на robot7 "saltmanxome7" (и еще некоторых роботов расшифровал, так что стало понятно, откуда это), но вердикт был WA (хотя on right track). Потом еще часа два возился, перебрал сотни бредовых догадок и версий, но все тот же WA. Какой же все-таки ответ?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    По задаче D -- у меня в простом инпуте проблема была в том, что Collation по умолчанию был какой-то регистро-независимый, а надо было устанавливать какой-нить бинарный. Когда поменял collation, зашла сразу. По второму тесту там поинтереснее выборки, и надо уже индексы строить :о)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Аналогичная проблема. Только мне такая мысль на контесте даже в голову не пришла :(

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Нам пришла, но толку все равно было не особо — то ли где-то таки пропустили регистр, то ли было что-то еще.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А как там вообще в I надо было пароль находить?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Например, Extreme GPU Bruteforcer :) Находит пароли для нескольких роботов, становится понятен вид пароля <слово><номер робота> (плюс соль). Потом запускаем брут для седьмого робота. PROFIT Думаю, что можно было и без GPU.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Прочитал booklet, но так и не понял, как решать С (карты и матожидание)?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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".