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

Всем привет!

В ближайшую субботу, 24 мая 2014 года, в 19-00 по московскому времени, состоится третий квалификационный раунд Russian Code Cup 2014.

Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru

Участвовать могут все, кроме 401 участника, которые уже квалифицировались в первом и втором раундах.

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

И немного приятных новостей: мы обновили версии компиляторов почти всех языков, добавили возможность отправлять на C++11 под GNU C++ (а Visual C++ 2013 и так поддерживает C++11) и добавили Java 8 (Java 7 тоже пока остается). Актуальные версии компиляторов и строки компиляции на странице с правилами чемпионата http://www.russiancodecup.ru/rules

Всем удачи!

[UPD] Всем спасибо за участие, раунд завершен. У нас снова 201 прошедший, поздравляем! Разбор будет опубликован в ближайшее время.

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

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

надеюсь задачи будут не хуже тех, что были в прошлом квалификационном раунде.

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

Не будет ли проблем с Java 8, связанных с крашем VM из-за политик безопасности вашей песочницы?

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

    Ну, на наших тестах проблем нет, спасибо, что напомнили, потестирую nextProbablePrime

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

      Протестировал, не падает.

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

      Недавно было ещё сообщение, что источником подобных проблем могут быть вызовы параллельной обработки стримов и прочего параллелизма, который добавили в Java8 (Arrays.parallelPrefix).

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

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

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

Возможность скачивать свои посылки так и не появится?

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

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

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

Еще не очень удобно, что таблица результатов так часто обновляется, например, при поиске участника

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

Спасибо, ни одна просьба не остается без внимания :)

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

Как решать D?
Ну и скажите решение C c док-вом, пожалуйста.

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

    Задача С: Для начала нужно понять что два простых нечетных циклах, пересекающиеся по ребру создадут четный цикл ("логическая" сумма циклов) Тогда ясно, что два цикла могут пересекаться только по вершине, а далее рисуем ромашку циклами по три.

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

      У меня в D динамика true/false [position][candies]. Перейдем от массива к частичным суммам на префиксах, и будем раздавать по одной конфете сразу всем участникам каждой из первых х команд. Начнем с всего набора команд и всех конфет, заранее раздадим каждому участнику по конфете. Далее возможные переходы в динамике:

      • раздать по 1 конфете всему префиксу длины x и не уменьшать длину префикса
      • раздать по 1 конфете всему префиксу длины х-1 и уменьшить длину префикса
      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        Сложность получается О(d*n), где d-кл-во конфет и n-кл-во команд. Верно? Я подумал, что 10^8 может не хватить=(

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

          Да, именно. O(d*n) по времени и по памяти. Хватает с запасом. Там целых 2 секунды, а такое решение, подозреваю, и в 0.5с зайдет.

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

        То же самое, только динамика одномерная. Можно действия, которые у вас в динамике, провернуть в начале, перейдя к задаче, аналогичной из условия, но где все ai могут быть любыми неотрицательными числами. И такая задача уже решается простым рюкзаком. upd. Не утверждаю, что так лучше, просто поделился.

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

    C. понятно что граф реберный кактус, если нет тогда один из простых циклов четный.

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

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

    Сначала говорим, что первая команда получает по N конфет, вторая — по N - 1, ...

    Если после такой раздачи конфеты ещё остались, то считаем префиксную сумму по количеству человек в команде (т.е. для третьей команды эта сумма будет равна x[1] + x[2] + x[3]).

    Потом раскладываем оставшееся число конфет на слагаемые, а слагаемые — это префиксные суммы, посчитанные на предыдущем шаге.

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

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

    В задаче D, из условия на неравенства, если s = n * a1 + ... + an > d, то NO. Далее задача сводится к такой: получить из s путем прибавления к х-ксам на префиксе число d. Заведем массив p[d] и будем считать для каждого d >= i > s — p[i] = j, где j — конец какого-то префикса, изначально делаем p[i] = -1 (что получить пока нельзя). Если p[d] = -1, то NO. Иначе легко восстановить ответ по массиву p. Могу дать общие соображения по С. Явно, что если есть нечетный цикл, то в нем ребер других нет. Поэтому лучше брать совокупность циклов, пересекающихся по вершинам. Для максимальности количества ребер надо использовать циклы длины 3 и сцеплять их по одной вершине. И да, если вершин четно, то нужно еще ребро добавить.

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

    D. Перейдем в другие координаты, x → y, a → b, где , . Для понимания картинка:

    Тогда там надо решить , где bi > 0. Уменьшим d на и перейдем к , где b'i ≥ 0. b'i ищутся тупым рюкзаком, потом из них восстанавливаются bi и ai.

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

Как решать E?

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

По кд прыгает страница с задачами. Поправьте, пожалуйста. Firefox 25.0.

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

Добавил контест в тренировки: 2014 Russian Code Cup, квалификация 3

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

А куда пропал питон 2.7??? Набрал первую задачу и только потом с ужасом обнаружил, что питон 2.7 в принципе отсутствует в списке. Предупреждать же хотя бы надо! Опять же, на втором десятке 21-го века не иметь питона 2.x в списке языков... Это за гранью добра и зла.