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

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

Всем привет!

Уже сегодня (25 октября) в 15:00 пройдет очередная командная интернет-олимпиада для школьников. На этот раз вас ждет встреча с Альфом.

Продолжительность — 3 часа в базовой номинации, 5 часов — в усложненной. Подробнее о номинациях и правилах можно прочитать здесь.

Если вы еще не регистрировали команду на интернет-олимпиады в этом сезоне, то сделать это можно тут.

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).

Олимпиаду подготовили Дмитрий Филиппов (DimaPhil), Илья Збань (izban), Евгений Замятин (Odeen), Захар Войт(zakharvoit) и Григорий Шовкопляс (GShark).

Удачи!

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

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

Спасибо авторам за хороший контест и как решать F?

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

    У нас на эту задачу написано что-то, похожее на мерджсорт.

    Чтобы в n-той очереди получить все 2n чисел в порядке возрастания:

    • получим в (n - 1)-ой очереди первые 2n - 1 числа в порядке убывания
    • эти числа передвинем на стэк
    • получим в (n - 1)-ой очереди вторые 2n - 1 числа в порядке возрастания
    • сольём стэк и очередь (поскольку на стэк мы числа клали в порядке убывания, теперь оттуда их получаем в порядке возрастания)

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

    Решение придумал и написал Alex_2oo8, который дописал идейную часть за пару минут до конца, приделал к ней аутпут, заслал, получил TLE, вспомнил, что аутпут большой, увеличил размер системного буфера и, за 37 секунд до конца соревнований, заслал решение, которое получило AC.

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

А что случилось с тестированием задачи G?

Мы её заслали где-то за полтора часа до конца, когда по ней ещё не было ни одного акцепта (или вовсе ни одного сабмита?), но в это же время появилось сообщение о реджадже D, так что мы особо не рассчитывали на быстрый фидбэк. Но время шло, другие команды получали акцепты, в том числе MishCo значительно позже нас получили плюс и по G, а у нас всё ещё было «Judging...», и так до конца контеста и осталось.

Мы об этом ещё во время соревнований сообщили жюри, но только минут через двадцать после конца получили ответ «исправлено», после чего с удивлением обнаружили, что мы-то плюс получили, а вот MishCo свой потеряли :) Как так?

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

    С тестированием задачи G случилось неправильное авторское решение :( Сначала мы не заметили ваш UD, потом, когда вы нам написали, мы начали разбираться и уже после конца контеста нашли багу в решении и исправили ее. Решение MishCo работало так же, как и неправильное авторское решение, поэтому и получило свой минус (правда уже после конца контеста, плохо довольно получилось :( )

    Кстати, можешь рассказать ваше решение? Просто есть подозрение, что у нас плохие тесты, и на самом деле ваше решение не должно получать ОК :)

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

      У нас решение такое:

      С графской стороны — у нас множество циклов. Все циклы должны быть четной длины и в каждом цикле мы выкинем ровно половину ребер (через одно). У нас есть два варианта для каждого цикла — выкинуть все четные или все нечетные ребра.

      Если в одном цикле пересекаются два ребра с одинаковой четностью, то в данном цикле ребра с этой четностью обязательно нужно выкидывать. Если в каком-то цикле нужно выкинуть и четные, и нечетные ребра — ответ NO.

      Если пересекаются два ребра из разных циклов, то это нам дает условие, что в этих циклах мы выкидываем одинаковые (или разные) по четности ребра. UPD Неверно!

      Оставшаяся задача — покраска графа в два цвета (по четности ребер, которые выкидываем), где вершины — циклы, а ребра означают одинаковые/разные цвета. Для некоторых вершин заранее задан цвет (пересечениями внутри цикла).

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

        Прикольно. Довольно просто идейно получилось, у меня решение посложнее. Предполагалось, что в этой задаче надо написать 2-SAT

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

А тесты будут?

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

    Архив олимпиады появился на сайте. Разбор задач появится позднее

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

      В задаче J тест #9 некорректен, четвертое число с конца — 0, хотя в условии 1 ≤ ai ≤ 109.

      А в G действительно нужен 2-SAT и наше решение не верно. Вот тест:

      PS В ветку выше коммент упорно не хочет отправляться.

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

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

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

        Да, действительно. Спасибо за тест, добавил его :)

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

          Дайте точный тест (можно номер в архиве). Надо и в тренировку же добавить.

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

      В задаче "Ломать — не строить" все авторские решения не проходят предложенные тесты: segments_dp.cpp, segments_zv_bipartition.cpp — падают на первом, segments_zv.cpp — на 19.

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

        Решения _dp и _zv_bipartition не должны работать, заменил их на _dp_wa, _zv_bipartition_wa. Решение _zv должно быть правильным, но я случайно залил старое решение с багой, которую мы нашли уже на контесте. Все исправил, залил заново. Теперь на сайте лежит правильный архив

        UPD. Только сейчас заметил, что авторское решение падает на тесте от Alex_2oo8. Будем разбираться. В архив положил правильный ответ на тест (тест 7).

        Слишком много баг для одной задачи :( Приношу свои извинения за такую некачественную подготовку

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

Похоже, что в задаче D не слишком сильные тесты.

Мы писали дерево отрезков и выделили под него 200000 массивов по 1230 чисел (количество простых делителей у произведения в текущем узле; порядковый номер простого числа устанавливался с помощью решета Эратосфена). Такая реализация занимает около гигабайта, и понятно, что это решение не пройдёт (ML16). Зато когда мы заменили тип данных int на short, то получили уже WA36, а когда поставили unsigned short, то получили AC. Хотя по идее оно проходить не должно, например, на таком тесте:

50000
8192 8192 ... 8192
1
1 1 50000

То есть, в верхнем узле для простого делителя 2 должно храниться число 50000×13=650000, что в 16-битную переменную никак не укладывается.

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

    Ну вообще цели отсечь такое решение не было — оно идейно правильное. Но то, что такое заходит — не очень хорошо, да. В авторском решении вместо дерева отрезков просто дерево Фенвика

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

      А авторское решение на джаве точно не получает ML? И сколько памяти тогда оно тратит?
      У меня ровно такой же расход памяти, но от ML пришлось спасаться как раз ДО для подсчёта количества простых больше 100, а это уже ведёт к таймлимиту.

      PS Считаю как 1300*50000*8 байт ~ 520Мб.
      PPS нагуглил, что int == 4 байта. Тогда почему такое решение получает ML?

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

        У меня это решение получило TL 16, использовав 509 Мб памяти. А вообще у вас при каждом запуске factorize создается новый массив cf. Если сделать его глобальным, решение тоже получает TL 16, но уже с 326 Мб

        Авторское решение на джаве работает за 1.3 секунды с 326 Мб

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

          Если с памятью проблемы, то можно написать корневую — 8487595 использует всего 1.7 мб.

          P.S. Перечитывайте лишний раз условия, которые составляете, это ведь не сложно. "кратчайшее расстояние от его дома до всех интересных мест города изменится у максимального числа интересных мест" — это еще куда не шло, но "Два сообщения не могут в данный момент по одному ребру может проходить максимум одно сообщение" напомнило мне цитату Кличко:)

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

    Можно маленькие делители (до корня из 10000) хранить в int, а остальные — в short. Но есть более изящное решение — для каждого отрезка хранить факторизацию в виде списка пар делитель/степень, отсортированного по возрастанию делителя. Слияние таких списков осуществляется как в сортировке слиянием. Так как число до 10000 может иметь максимум 5 разных простых делителей, получается серьезно сэкономить на памяти — моя реализация на C# потребяет всего 34МБ.

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

      Изначально у нас было именно такое решение: мы хранили пары делитель/степень в векторах и использовали сортировку слиянием для объединения. Но мы получали TL. Потом просто в качестве эксперимента попробовали написать без векторов, кто-то предложил "костыль" с uint16 — и зашло. :) В архиве тестов, из того, что я видел, такого теста, который я предложил, нет.

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

Вот что недавно мне пришло в личные сообщения:

Доброго времени суток! Решая тренировку (http://codeforces.com/gym/100515) долго промучался с задачей D. В итоге оказалось, что в условии n<=15, в то время, как 29 тест содержит n=17. Подумал, сообщить вам, как человеку, который подготовил эту тренировку.

Что характерно, в этой задаче был написан валидатор, содержащий строку ensureLimits(n, 1, 15, "n is out of range"); То есть он просто не был запущен. Ну правда, может вы перейдете на Полигон? Это классический пример раздолбай-бага, который невозможно допустить с Полигоном.

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

    А еще в условия http://neerc.ifmo.ru/school/io/archive/20141025/problems-20141025-basic.pdf в колонтитуле выразительно написано вторая олимпиада, 12 октября, хотя олимпиада третья и была 25-го.

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

    Приятно удивился, что подход с раздачей прав на редактирование тренерам работает — в усложненной секции некорректный тест был кем-то разумно удален. Работает система )

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

    Да, такая ошибка есть. Посмотрел пакет, выложенный сразу после олимпиады -- в нем нет этого теста. На олимпиаде так же присутствовал этот некорректный тест, и единственная команда, сабмитившая эту задачу (Progmeistars AAI) каким-то чудом после TL29 догадалась поднять константы в своем коде до нужного числа и получить OK. Хочется поздравить ребят с таким умением угадывать ошибки авторов :(

    Мы понимаем, что в наших задачах по "странным" случайностям всплывают непонятные баги, и сильно извиняемся. Честное слово, этого больше не повторится.

    PS: Данный баг, видимо, произошел из-за конфликта версий задачи на тестирующем сервере и в svn, где готовились задачи, и был вызван ошибками сразу нескольких человек. Я считаю полигон очень удобным средством для подготовки задач, но по некоторым причинам в ИТМО он непопулярен.

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

      Спасибо. Я час назад скачал файл archive-20141025-basic.zip, там этот тест есть :(

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

На сайте выложен разбор базовой и усложненной номинаций. Приносим свои извинения за столь большую задержку.

А еще у нас нововведение! Появился рейтинг ИТМО всех участников (спасибо Aksenov239 за него). Он также выложен на сайте