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

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

Сегодня в ИТМО проходит командный чемпионат школьников Санкт-Петербурга, в котором участвует 89 команд. Монитор доступен здесь. На тех же задачах проходят: командные олимпиады в Кирове, Ижевске, Петрозаводске, Казахстане, Узбекистане, Гомеле и отборочный интернет-тур ВКОШП.

За новостями соревнований теперь можно следить в твиттере. Хештег #СПбКОШП2013

Встреча чемпионата на Google+ здесь, сюда же можно добавить свои фотографии с чемпионата.

Желаем всем участникам удачи,
Пресс-служба соревнований.

UPD: На сайте выложены материалы олимпиады.

Санкт-Петербург и Ленинградскую область на ВКОШП будут представлять:
СПб, Сборная (Амирханов, Клюев, Лапшин)
СПб, ФМЛ 239: КПСС (Подгузов, Степанов, Степанов)
СПб, ФМЛ 239: Надежда (Бугакова, Симарова, Филимохина)
СПб, Лицей ФТШ #1 (Кравченко, Лабутин, Лиференко)
Сосновый бор, ЦИТ: Crayfish_team (Мамаев, Никонов, Шандуренко)
СПб, ФМЛ 239 + Школа 450: Pentagram (Казначеев, Макаров, Янцевич)
СПб, Лицей 533 #13 (Боровков, Немилов, Монаков)
СПб, ФМЛ 239: Бёенок (Павлов, Бойкий, Пластинин)
СПб, ЮТШ при СПбГЭТУ: Просто Космос (Безбородов, Копчук, Кравченко)
СПб, ФМЛ 239: МИГ (Коротеев, Тух, Ютман)
СПб, Лицей ФТШ #2 (Иовлева, Лабутина, Никифоровская)

Поздравляем команды, прошедшие на ВКОШП, и желаем им успехов!

UPD2: Завтра (28 октября) в 15:00 на сайте интернет-олимпиад будет проходить трансляция командной олимпиады школьников Санкт-Петербурга. Участвовать смогут все команды, зарегистрированные на текущий сезон интернет-олимпиад.

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

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

Мне всё-таки немного жалко, что произошла такая глобализация отбора — я в плане общих задач для разных регионов. Уверен, многие из регионов наверняка бы смогли подготовить интересные комплекты задач. А так уменьшается количество контестов, авторское разнообразие, жюри в регионе исполняет практически только организационную роль.

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

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

    Да и многие задачи хороших авторов используются в других онлайн-контестах и раундах на CodeForces, TopCoder и прочих...

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

      Почему бы не объединить такие регионы с онлайн отбором?
      Тогда действительно в онсайт будут проходить сильнейшие команды. Сейчас же команда может не пройти через онлайн тур, но показать результат, который был бы проходным в доброй половине регионов.

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

        Потому же, почему в финале ACM не более одной команды от вуза и региональные квоты: нужно не только собрать сильные команды, но и обеспечить представительство регионам.

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

          Звучит разумно, но наверняка можно это сделать другими методами(например, теми же квотами), а не тащить одних за счёт других.

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

          Казалось бы текущая схема наоборот помогает пройти командам из eps регионов.

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

    Вот посмотрев на контест отбора школьников в Челябинске я ужаснулся. Лучше бы они Петербургский взяли :(

    4 гроба, куча команд решили по 4 задачи.. http://ipc.susu.ac.ru/standings.html?contest=458

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

По результатом интернет-тура 14 команд решили 6 задач, и только 5 команд решили 7 задач. Интересно было бы знать, какое количество команд отберётся для участия во ВКОШПе. Да и как-то не справедливо получается. Так же в Гомеле проходил очный тур по тем же задачам, и там 5-ая лучшая команда которая отобралась для участия во ВКОШПе решила только 3 задачи

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

Сделайте, пожалуйста, тренировку. Хотим досдать две оставшиеся нам задачи.

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

    Начал делать. Засекайте время.

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

      Не взлетело :(

      Ну вот каждый раз, добавляя чей-то архив я опять убеждаюсь, что архив недопустимо собирать руками, он должен автогенерироваться и быть формально машинно читаемым:

      1. В задаче D. Болезнь нет сгенерированных ответов.
      2. Решение scanner_av_wa44.java невозможно скомпилировать без правки или переименовывания.
      3. В архиве нет необходимых библиотек. За Validate.java спасибо, но как его скомпилировать?
      4. Все java-решения по злосчастной D. Болезнь падают с exception вокруг ввода на тесте 18. Некорректный тест?
      5. Ни одно авторское решение не проходит 29-й тест в A. Банк.
      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        И когда ждать тренировку с задачами данной олимпиады?

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

        Библиотку для валидаторов я тебе послал. Почему ее в архиве нет это интересно.

        29 тест решения у меня локально проходят.
        md5
        3b3bc238e060b07ce3f316193e669a83 *29
        af8b3b8609c02d8c382546744638f934 *29.a

        Может не то генерируется что-то?

        Задача D тоже собралась без проблем в svn.
        e93a3962957fd1a0b1a9ca3fda696556 *18

        То из чего я собирал задачи в svn и то что лежит в архиве совпадает.

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

          Мне интересно что находится в ru-olymp-team-spb-2013-archive.rar, а не в жюришном svn. Там для А находится тест 29 явно обрезанный. А еще ты будешь удивлен, узнав, что в этом архиве в D всего 18 тестов (и 18-й тоже неполный).

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

            Ну зачем брать архив со сгенерированными тестами? Хотя конечно лучше написать, чтобы поправили.

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

              Архив со сгенерированными тестами всегда предпочтительнее. Билд-скрипты жюри частенько не работают (например, здесь из-за отсутствия библиотек). Разница в компиляторах может привести к другим или даже неправильным тестам (мы сам написал про Python32 и Python33).

              Билдскрипты каждый раз написаны по-своему, называются не единообразно (между разными олимпиадами), даже на разных языках (обычно bat, но я видел и bash).

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

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

        Заборол. Перегенирировал тесты. Причем buildTests.cmd, конечно, не работают как задумано. Зачем их вообще выкладывать, если они работают в специфическом окружении жюри? Версию питона для генератора пришлось угадывать, т.к. шебанг отсутствует.

        Зачем в генераторы тащить логику лэйаута расположения тестов? К чему new File("../tests").mkdir();? Сложно запустить его в tests и генерировать тесты в текущей директории?

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

          Про файлы — это требование andrewzta. Про питон, я тоже считаю извращением. Особенно с учетом того, что в Python32 и Python33 разный рандом. Правильная версия — 32. А что не так с каким buildTests?

          А. Понял что с buildTests. Они считают, что testlib4j живет в ../../lib

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

        И уж прости, но собрать архив из полигона под линуксом Burunduk2 так и не смог. Как минимум потому что он распаковался не в кучу папок, а в кучу файлов с виндовыми слешами в именах. Про то, что архив из-за собранных .exe весит в 5 раз больше чем надо, и не собирается под не-виндой без wine, я даже молчу.

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

          С путями были баги, но вроде они ни на что не влияют (это касалось только bat-файлов в linux). И это уже некоторое время как исправлено.

          С wine к сожалению это единственный рабочий костыль (кстати, придуманный и поддерживаемый linux-сообществом, присутствующий для большинства популярных дистрибутивов в виде пакета) чтобы защититься от некроссплатформенного кода от разработчиков задач. На самом деле, довольно часто кто-то пишет плохой код: %I64, зависимость от \r\n, нехватка каких-то #include, неправильная работа под 64-битном g++. Это неполный список проблем. Дистрибуция готовых exe, которые гарантированно генерировали что надо хорошо решает ряд проблем. Например, в Windows это отлично работает. Вроде doall.bat хорошо собирается и о проблемах я не слышал.

          Можно сделать light-пакеты, но тогда надо внедрить самопроверку корректности тестов (пихать в пакет sha1 от них). Это чуть сложнее сделать, ведь тесты явно не генерируются при сборке неполных пакетов (а еще всякие \r\n <-> \n тонкости).

          Вот размер мне не кажется сейчас важным критерием, всё-равно сгенерированная задача наверняка будет весить значительно больше суммы всех бинарников. Интернет уже почти везде позволяет скачать в среднем пару мегабайт на задачу без особых проблем (секунды же). Хотя кое-что поджать можно, только сегодня я узнал о том, что в jar-файлики много лишнего пакуется.

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

            Ну я стараюсь класть вместе со своими задачами md5 тестов и \r\n и \n. Правда только тестов обычно. Ответ бывает не однозначен. Или вещественные числа могут на немного ошибаться или еще что-то такое.

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

        Действительно, произошли накладки, собрал в архив не совсем корректное состояние каталога с задачами.

        Перезалил архив, сейчас все должно быть ок.

        Спасибо за замечания!

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

    Я конечно понимаю, что глупо вот так вот плакаться после контеста, но ребята(!), знаете, очень обидно, когда ты такой пишешь под конец задачу I, которая обана — сразу скомпилилась и заработала почти сразу, отправляешь дрожащими руками за 20 секунд до конца и получаешь PE 52... А потом смотришь — детская ошибка — не поправил ограничения после предыдущей задачи — и всё: и боль, и страдания, и огорчения, и муки совести. А тут еще Рига делает отправку под конец и обходит на 7 штрафных минут. И эмоции — тренер матерится, все матерятся. И вообще беда.

    Спасибо, что выслушали, я всё сказал. Мне полегчало.

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

      разве, с точки зрения норм воспитания школьников, корректно ли, что тренер при школьниках матерится? это же не педагогично!

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

        Эмоции дают о себе знать

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

        Тренеры же больше нас всегда переживают. Будь у меня такая ситуация, я бы отреагировал, как эти ребята, а будь я тренером..:)

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

      Разве что-нибудь изменилось бы, если бы вы заняли первое на отборе? Я не думаю, что это фатально. Мы в прошлом году вообще все школьные командные слили кроме одной.

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

        Конечно ничего бы не было, но мне было бы очень приятно задачу сдать за 10 секунд до конца и получить тотал. Каждый наверное об этом мечтает.

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

Подскажите, пожалуйста, как решить задачу G "Осенний парк"?

Читал разбор: http://neerc.ifmo.ru/school/archive/2013-2014.html#team-spb, но что-то ничего не понял. Я понял так:

в качестве примера возьмём

2 2

X.

.E

Это 14-ый тест, и на него ответ 8.

Рисунок не из лучших, но всё же. :) Чёрные вершины — это стартовые. Цифры в них — это расстояние до них от начальной.

Потом следуем разбору:

"Добавляем для вершины v вершину v', в которой будут заканчиваться пути длиннее кратчайшего на 2". Это красные вершины(для каждой она расположена по диагонали). Расстояния в них равны расстояния отцовской + 2, т. к. " пути длиннее кратчайшего на 2".

Далее:

"Добавим ребро из v в u', если было ребро из v в u и d[v] = d[u] + 1". Эти рёбра чёрного цвета и проведены, соответственно, к красным вершинам.

Потом применяя алгоритм для нахождения количества кратчайших путей получаем массив cnt[](цифры синим цветом). Но у меня вообще не получается 8.

Объясните, пожалуйста, где ошибка или расскажите своё решение.

Заранее благодарен. ;)

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

    Во втором слое должны быть ребра. Те — которые идут по кратчайшим путям. Правда кажется кратчайшим от конца... Была написана чушь. Конечно там должны быть все те же ребра, что и в первом.

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

      С этими рёбрами всё становится на свои места:

      Большое спасибо. :)