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

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

2-го декабря состоится очередной (17-й) полуфинал Чемпионата Мира — Northeastern European Regional Contest 2012!

Желаем удачи командам, а болельщикам — побольше радостных моментов!

Полезные ссылки:

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

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

А только награждение будут транслировать? Во время контеста ничего не будет?

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

    Мне кажется, что нет. Аппаратуру я не видел, разговоров об этом не слышал.

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

Буду болеть за однофакультетовцев (ВГУ), желаю им удачи!!

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

tourist so powerful!!

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

Интересная картина: из саратовских команд, на данный момент лидирует команда JKeeJ1e30 с 5ю решенными задачами.

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

    JKeeJ1e30 на финал!

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

      Уже результаты есть?

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

      Я очень рад, что меня поддерживали столько людей:) К сожалению, мы не прошли в финал — неправильно прочитали условие по задаче B, а решение J я придумал только за 15 минут до конца. Кроме того, нас обогнала по штрафному времени команда SU2. Для меня такое выступление, если честно, было несколько неожиданным — в ТОП50 по заданию тренеров мы должны были попадать, но то, что мы весь контест будем обгонять намного более сильные саратовские команды, было очень неожиданно.

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

Интересно, а трансляция у всех нормально идет? У меня постоянно тормозит и срывается.
На свой канал не жалуюсь. Причем, замечено, что, если, по-идее, просматривающих мало, то и проблем нет. Так пока шел ВКОШП, показывали актовый зал с затылками тренеров, и все шло прекрасно. А закрытие ВКОШП уже было с проблеммами.
Открытие NEERC вчера нормально шло. Сегодня, пока народ в зале собирался, было нормально. А вот разбор уже смотреть было нельзя, думаю и закрытие также не посмотрю.
Это проблема чего-то узкого со стороны ИТМО, или дело в чём-то другом?

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

    Абсолютно аналогичная ситуация.

    Скорее всего для видео нет отдельного выделенного канала с ИТМО, а массовое присутствие программистов со своей техникой и наличием вай-фай перегружает всю местную сеть и обрывает видео, которое на может уже идти с нормальной скоростью.

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

Постоянно обрывающаяся трансляция без звука — это нормально?

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

Oh, they skrewed up the online broadcast. What a shame for ITMO.

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

У меня одного на топ-10 not found начало писать? :/

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

Ребят, расскажите вкратце, что было... кто победил... Не могу подключиться к трансляции.. Спасибо!

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

    Просто скопирую из твиттера: Победители #neerc2012: 1 — ИТМО-1, 2 — МГУ-1, 3 — БГУ-1, 4 — СПбГУ-4. В общем-то, вполне ожидаемый набор.

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

Сколько всего финалистов?

И, если кто-нибудь может написать, кто в финал прошёл?

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

Финалисты от NEERC:

  • 1 SPb NRU ITMO 1 (Kever, Korotkevich, Nigmatullin)
  • 2 Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko)
  • 3 Belarusian SU 1 (Malevich, Udavichenka, Zhgirovski)
  • 4 SPb SU 4 (Egorov, Kunyavskiy, Suvorov)
  • 5 Ural FU 2 (Dolgorukov, Shchelkonogov, Soboleva)
  • 6 Almaty Intl IT U (Bolshakov, Kovalenko, Kutybaev)
  • 7 Kazakh-British TU 1 (Aitbayev, Almakhan, Satylkhanov)
  • 8 Moscow IPT 4 (Alsarmini, Gorshenin, Pimenov)
  • 9 Izhevsk STU 1 (Burlakov, Gatin, Smirnov)
  • 10 SPb AU 1 (Chadnov, Krasko, Lazarev)
  • 11 Samara S Aerospace U 1 (Dergunov, Glashenko, Semushin)
  • 12 Ufa S Aviation TU (Lezhankin, Mazgarov, Ripatti)
  • 13 Altai STU 1 (Esipenko, Silin, Uvarov)
  • 14 Kaunas TU (Ciakas, Kusas, Mulevicius)
  • 15 Moscow Aviation I 1 (Belousov, Safronov, Zhuravlev)
  • 16 Saratov SU 2 (Davtyan, Gusarov, Kudryashov)
  • 17 Moscow I of Steel and Alloys 1 (Bulatov, Kofman, Krohina)
  • 18 Perm SU 1 (Akimov, Osherov, Zayakin)
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Есть ли где-то борд с командами вне конкурса?

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

    Странно. А на снарке еще команда Novosibirsk SU 1 (Beloshapko, Scherbina, Stenenko) выделена, как прошедшая в финал. Вот (смотреть 35 место) http://neerc.snarknews.info/index.cgi?data=macros/standings&qf=neerc&class=neerc2012&year=2012

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

      Это не странно. Жюри изначально решило пустить первые 19 команд. Но для Новосибирска это должно было быть секретом, так как в Барнауле награждение проходило на следующий день.

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

      NEERC выделена квота в 19 мест. Соответственно, команда НГУ1 в финал проходит.

      В Барнауле закрытие было в 12-00 3 декабря. Соответственно, для сохранения интриги закрытия в Барнауле в СПб объявляли только присутствующие лично команды, которые в финал прошли (ну и те, что были выше хотя бы одного СПб-финалиста — КБТУ и Алтай). Отметим, что число мест в финале от NEERC на церемонии закрытия явно объявлено не было.

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

Команда Saratov SU#2(Давтян, Кудряшов, Гусаров) вышла в финал. Поздравляю,я думал, что ни одна из саратовских не прошла.

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

Разморозили таблицу. Интересные факты:
1) СПб ГУ 4 за последний час сдала 4 задачи;
2) БГУ 1 последнюю задачу сдала за 24сек. до конца и вышла на 2-е место, но МГУ 1 сдала за 3 сек. до конца и всё-таки их обошла!

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

    Хочется добавить что БГУ и МГУ не знали результатов (компы перезагрузили всем сразу после конца). Так что закрытие было нервным.

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

      У нас была аналогичная ситуация — не видели вердикта на последний сабмит, так как комп сразу перезагрузился. Тупо включили комп и посмотрели. Но там ничего интересного не было.

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

        Хитрые жюри не разрешили БГУ и МГУ ничего смотреть.

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

          Может и дали бы. Но все дотестировалось сильно после конца контеста.

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

А как скоро и появится ли вообще этот контест в тренировках?

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

    Готово. Решайте на здоровье!

    P.S. Интерактивной задачи B нет, поэтому таблица с результатами онсайт-участников немного отличается от настоящей.

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

      Лучше бы дал Майку залить эту тренировку — ведь он умеет добавлять интерактивные задачи.

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

        А я и не знал, что интерактивные задачи уже поддерживаются. Покажи, пожалуйста, пример тренировки с интерактивной задачей.

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

          Саратовский четвертьфинал

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

            Спасибо, буду знать. Спрятал тренировку.

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

              Будет ли дорешивание? на openCup нет microsoft c++ компилятора, а в H с кучей stl это немного мешает.

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

                Тренировка на CF уже есть, но открытой она станет, когда MikeMirzayanov добавит в нее интерактивную задачу.

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

                  Интерактивную задачу, кстати, добавили.

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

    Есть рабочая виртуалка на Open Cup Trainings (старые Яндекс-тренировки).

    Вход по логинам текущего OpenCup.

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

А что, мы единственные, кто сдал задачу C с помощью нахождения касательной к выпуклой оболочке? :) Петр пишет, что у SPb SU 4 в целых числах решение, как делали? Кстати, кодить наше решение совсем недолго, оно довольно короткое.

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

    я вот на разборе прослушал и не понял, о какой выпуклой оболочке идёт речь

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

      Я позже расскажу, если до меня этого никто не сделает

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

      Смотрите, ответ — это min ( (b_i — l_j) / (i + 1 — j)) Будем искать этот минимум при фиксированном j: получаем min ( (b_i — c_1) / (i — c_2) ) По сути это касательная к выпуклой оболочке точек {(j — 1, l_j)}

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

    Сделаем бин.поиск по ответу где границы полуинтервала — рациональные числа (изначально [0/1,(10^6+1)/1), если обозначить текущий полуинтервал за [a/c,b/c), то в качестве средней точки выбираем ((int)((a+b)/2)))/c при b-a>1, и (a+b)/(2*c) иначе), внутри бин.поиска обычный жадник. Остановим бин.поиск, когда знаменатель дробей будет больше 10^10 (к этому моменту числители уже будут различаться на 1). Теперь мы получили полуинтервал длины менее 10^-10, в котором лежит ответ. Заметим, что ответ на задачу — минимум по всем i>=j (ri-lj)/(i-j+1), где ri и lj — правая граница i-ого и левая граница j-ого отрезков соответственно. Т.е. знаменатель этой дроби не больше 10^5, но в нашем промежутке от бин.поиска могло поместиться не более одной дроби с таким маленьким знаменателем. Осталось перебрать знаменатель дроби от 1 до n и проверить нет ли в указанном полуинтервале дроби с таким знаменателем (это выражается простыми неравенствами, которые надо честно написать), как только нашли такую дробь — выводим, это ответ.

    P.s. Еще при проверки рационального числа в бин.поиски лучше всего сразу домножить все числа на знаменатель проверяемой дроби и получить уже чисто целочисленную задачу, т.к. знаменатель дроби около 10^10 все более чем прекрасно умещается в long long.

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

А Капун сдал бы 12-ую.

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

    12-ю или все 12?

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

      Не в обиду Гене, но, по-моему, сдача одиннадцати задач была для ИТМО 1 делом самим собой разумеющимся хоть с ним, хоть с Капуном.

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

        Не в обиду никому, но на прошлом полуфинале победители решили по 9 задач из 12. Хотя, возможно, в этом году задачи были значительно проще.

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

          Ну откуда Вам знать?

          Тут вот казахстанские эксперты уже все давно просчитали.

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

        ...хоть с Большаковым)

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

    По-моему, сравнивать эти 2 команды вообще некорректно.
    Гене очень далеко до Капуна в плане математической подготовки, но у него есть свои достоинства. Так что в новой команде и роли поменялись, и, видимо, тактика. Так что прошлогодняя команда, может сдала бы 12-ю, а может и не добралась бы до неё.
    А фраза мне не понравилась, показалась мелкой подколкой. Хотя фразы выше о том, как силен турист, мне не понравились значительно больше.

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

    кажется, как раз в прошлом году выяснилось, что какая-то из задач NEERC чрезмерно похожа на задачу с какого-то белорусского опенкапа?

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

    Мы знали про ту задачу, но никто из нас на тимусе ее не решил. Она сильно похожа, если знать ее, не приходится с нуля догадываться, что там перебор.
    В итоге у нас за 10 минут до конца было решение, отличающееся от верного на 3 символа, и багу мы так и не нашли, а она такая глупая была...

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

    А еще эта задача была на летних сборах школьников в 2008 году (задача C) и на Питерских школьных сборах этого года. Правда, в усложнённом варианте — кубик до 4x4x4 и может не существовать решения — надо еще добавлять отсечение по времени

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

Я бы с радостью посмотрел на списки финалистов (а в идеале — на итоговую таблицу вообще), в которых для каждого участника были бы указаны его ники на CF/TC.

Ни у кого такой нету случайно? :)

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

А когда будет дорешевание задач полуфинала ?

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

    Чтоб команды использую свои логины могли скачать свои посылки

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

      Такого вроде вообще не бывает :) На neerc.ifmo.ru обычно выкладывают архив сабмитов с четвертьфинала, а вот с NEERC не видел. А просто дорешивание можно на snarknews.

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

        Я после контеста спросил одного из организаторов, как скачать свое решение. Он ответил, что никак , но потом будут все сабмиты и используя свой логин можно будет скачать свои посылки.