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

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

Добрый день!
Я хотел бы представить вам олимпиаду по программированию Advancement, которая уже третий год собирает в стенах Филиала МГУ в г. Севастополе молодые и перспективные команды из разных городов Украины. Наша олимпиада расчитана на начинающих программистов, которые еще не попали на первенство Украины в г. Виннице. 

В этом году мы немного изменили формат соревнований и добавили отборочный онлайн тур, в котором смогут принять участие все желающие, а первые пятнадцать команд по результатам отборочного тура получат приглашение в Севастополь на основное соревнование.

Отборочный тур пройдет 19 ноября с 17-00 до 19-00 по киевскому времени, а основной будет проходить 3 декабря.

Информация об олимпиаде доступна на странице http://gw4.msusevastopol.net:43434/ 

Приглашаем команды младшей лиги принять участие в соревнованиях, набраться ценного опыта и подготовиться к финалу Украины.

UPD.

Турнир завершен, результаты и новости можно увидеть на официальном сайте олимпиады. Также на этом контесте запущено дорешивание. Всем спасибо за участие.

UUPD.


Во время основного тура будет работать зеркало контеста по ссылке. Для участия нужно быть зарегистрированным в системе SPOJ.
Болельщикам турнирная таблица соревнования доступна по адресу.
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Хорошее мероприятие. Жаль, сообщение поздновато - не успеем все команды универа организовать.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    После субботнего отборочного тура будет две недели до основного. Мы были бы рады вас видеть.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Просто одно дело, если участие в отборе примут 2-3 проверенные команды, которые уже кое-куда поездили (кроме Винницы :) ). А другое - ещё подтянуть команд 8 из перво-второкурсников, которые только-только образуются. Вот со вторым пунктом постараемся справиться, но обещать не можем.
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Должно быть интересно. Ждём)
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
помню, помню... круто было!!!
Долго ждали когда инфа появится, обязательно постораемся приехать)
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
А зеркало основного тура какое-то параллельно будет? На сподже, например.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Скорее всего да. Информация об этом появится на официальном сайте после окончания отборочного тура.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
почему неначинающие команды не могут приехать и поучавствовать вне конкурса, как это было в прошлые года?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Из-за ограниченности мест в компьютерном классе. В этот раз у нас зарегистрировалось много начинающих команд, в связи с чем мы не можем предоставить компьютеры командам вне зачета.

    Зеркало контеста на спожде частично решит эту проблему.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится
      Очень жаль, что в этом году так, ведь в прошлые годы компьютеров хватало на многих. Надеюсь что-то ещё можно сделать, так как думаю что участие было бы не только интересно, но и полезно. Даже для команд, ездивших в Винницу в этом году, вне конкурса разумеется. 


      Спасибо во всяком случае за проведение такого соревнования, на которое могут поехать начинающие команды, попробовать себя и получить опыт. Желаю успехов командам своего университета, которые поедут к Вам. :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      С зеркалом уже всё решено? А то я на сподже не могу найти никаких анонсов.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
И ещё, на всякий случай, приказа Министерства о том, что это настолько круто, что "ректорам ВУЗов командировать", нет? Я понимаю, что шансов немного, но вдруг... ;)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Приказа Министерства к сожалению не будет. Я административной частью не занимаюсь, но насколько мне известно, в случае прохождения в основной тур вам будет выслано письмо-приглашение, с которым ваша бухгалтерия может оплатить командировку. Это еще от университета будет зависеть.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Есть возможность пописать отборочный раунд вне конукрса?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Нет, в этом немного смысла из-за уровня задач. А вот основной тур мы постараемся сделать интересным и для участников вне зачета.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  За "Compilation error" штраф начисляется? Просто в таблице стоит +2.  
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Как решать Е?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Можно делать перебор по количеству шагов по координате x и y. Из количества шагов по каждой координате и координаты цели мы можем однозначно определить сможем ли мы добраться до цели и если да, то сколько шагов понадобится в положительную сторону и сколько в отрицательную. Остается только вычислить количество способов путем перемножения биномиальных коэфициентов (или сразу выписывать мультиномиальные). В задаче можно было предподсчитать все биномиальные коэфициенты или все факториалы и их обратные по модулю (из малой теоремы Ферма). Получается O(n^2).
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
"Турнир завершен, результаты и новости можно увидеть на официальном сайте олимпиады."

можно ссылку, пожалуйста?
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Будет ли где нибудь зеркало основного тура для online-болельщиков? Было бы неплохо!
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Болельщикам турнирная таблица соревнования доступна по адресу.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Спасибо! Будем надеяться, что таблица будет обновляться более-менее оперативно (хотя бы раз в 15 минут) Или она будет актуальным зеркалом реальной таблицы? 
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Скажите, пожалуйста, какой 51-й и 52-й тест в задаче G. Где-то в этом районе мы постоянно ловили ВА.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    На сподже выполняются все тесты, а потом выдается вердикт, т.е. если у вас на первом тесте WA, он прогонит все 50 и выдаст WA.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Хм, спасибо за информацию. А можно будет где-то найти тесты по этой задаче? А то не можем найти косяк в коде, все наши тесты проходит.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Спасибо. Тогда всё ещё более запутанно, чем я думал.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Где можно дорешать задачи, на spoj не получается?

+Хотелось бы узнать как решаются задачи A,I?

  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    А - динамика.
    Т.к. каждое число 1, 2, ... 2^(k-1) можно использовать ровно один раз, то по длине подотрезка можно однозначно восстановить, какие числа были использованы для его формирования. А значит, использовать можно только другие числа. Дальше всё стандартно: для каждого i допустимыми шагами являются такие 2^r, что (2^r)|i != i. Стараемся минимизировать текущую сумму для каждого i. Максимум на отрезке ищем с помощью дерева отрезков.

    I - компоненты связности.
    Пихнём из истока во все вершины максимально возможный поток и удалим рёбра, ведущие из истока и в сток (но запомним, сколько потока из каждой вершины, связанной со стоком можно слить). Теперь я утверждаю, что для любой компоненты связности верно: весь поток из первой доли можно в любых пропорциях пихнуть во вторую долю. Действительно, наши рёбра имеют бесконечную пропускную способность, а значит из любой вершины в любую можно пустить сколько угодно. А значит, что ответом для компоненты связности будет минимум из того, что может притечь в первую долю и того, что может утечь из второй доли.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      По задаче А можно было и не писать дерево отрезков, а просто рассчитать m[i][j] - максимум на отрезке [j,j+(1<<i)-1].
      Просчитывается очень просто
      m[0][j] =a[j]
      m[i][j]=max(m[i-1][j],m[i-1][j+(1<<(i-1))])
      И асимптотика решения лучше становится :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Логично. Но не стали лишний раз задумываться, когда есть стандартный приём.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну для меня то тоже было стандартным приемом, который я, правда, нигде не использовал еще. Мне его рассказывали как часть алгоритма RMQ с ответом на запрос за O(1). Правда есть некоторая сложность с нахождением степени двойки, меньше или равной длине интервала :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится
            А в чем сложность? завести массив f;
            f[i]=f[i/2]+1;
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Хм. И правда ни в чем. Наверное просто я забыл про такую очевидную вещь.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    присоединяюсь, можно ли где то открыть добивание (а то задачи на добить - есть, а добить негде =( )
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
На сподже контест теперь не ограничен во времени.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А будут ли доступны фотографии/видео с события?