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

Всем привет!

4 марта в 15:00 начнется первый квалификационный раунд чемпионата VK Cup 2017!

Раунд продлится 24 часа, такая продолжительность выбрана для того, чтобы все нашли себе удобное время для участия. Квалификационный раунд, как и все предстоящие раунды, требует отдельной регистрации. Регистрация уже открыта и будет открыта на протяжении всего раунда.

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

Если вы пока не уверены в текущем составе команды, то не регистрируйтесь на предстоящий раунд. Если вы не будете участвовать в первой квалификации или не пройдете по ее результатам в Раунд 1, то вы сможете попробовать свои силы во второй квалификации.

Чтобы пройти в Раунд 1, вам надо принять участие хотя бы в одной из квалификаций. Из каждой квалификации в Раунд 1 проходят все команды с положительным числом баллов, которые набрали не меньше баллов, чем команда на 500-м месте.

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

Категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них до окончания раунда. Запрещено обсуждать задачи с кем-либо кроме вашего сокомандника. Будьте честны, пусть в Раунд 1 пройдут сильнейшие!

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

Если вы впервые участвуете в соревнованиях подобного рода, ознакомьтесь с одной из задач 158A - Next Round квалификационного раунда чемпионата VK Cup 2012, а также примерами ее решения на разных языках программирования:

Желаем удачи и удовольствия от решения задач!

UPD 1: Ваши решения будут протестированы после раунда 403.

UPD 2: Решения протестированы! Поздравляем всех тех, кто набрал баллов не менее чем 500 место.

UPD 3: Разбор

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

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

Ждём с нетерпением!

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

Добавьте пример на Kotlin! 25204556

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

Registration for non Russians is not allowed?

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

    I think it is not prohibited, but contest will be only on russian language

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

    Sorry, this round is only for Russians. We have plans to open other rounds of VK Cup for everyone as rated rounds.

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

Почему я не могу зарегистрироваться?

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

    Это этап чемпионата. Сначала зарегистрируйтесь на чемпионат VK Cup (если удовлетворяете правилам участия).

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

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

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

Мне одному кажется странным делать time discount в суточном раунде?

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

почему стоимость задач падает?

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

Парочка багов с регистрацией:

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

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

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

    на главном сайте есть регистрация(справа)

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

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

Есть кто-нибудь без сокомандника? Не хочется в одиночку писать.

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

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

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

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

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

    Есть же еще вторая квалификация, в которой пройти значительно проще по опыту прошлых лет. И согласен, что задачу можно протестить от и до

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

    4 задачи с почти любыми штрафами, наверняка, будет <= 500 место. Много решений упадет на системных тестах.

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

      Ну не знаю, немного идей приходит, на которых бы могло упасть на систестах.

      B — когда сумма массива меньше, чем n - 1

      C — когда k%2=1

      D — когда не подсчитаны xor-ы больше 10к, или лонг-лонг в ответе, но судя по претестах, лонг-лонг в ответе есть.

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

        На переполнение не было претестов

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

        xor-ы больше 10к на претестах падает. :) Из-за этого у меня 2 отправки

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

    Теперь даже решившие АБС с штрафом 1 проходят.

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

Systesting?

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

D можно решать и в бОльших ограничениях, если воспользоваться преобразование Фурье над двоичным кубиком: аналогичная задача, описание похожего подхода (отличие: считаем (A + B)(C + D) и (A - B)(C - D), и выражаем AC + BD и AD + BC как полусумму и полуразность).

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

Когда закончится системное тестирование?

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

Странно. Моё решение 25213245 по задаче D использует достаточно много памяти, однако тем не менее O(1).

И вердикт оно получило ML38.

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

    решение еще закрытое — нельзя посмотреть((

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится
    for (int i = 0; i != (1 << 14); ++i)
            for (int j = i; j != (1 << 14); ++j)
                if (popcnt[i ^ j] == k) {
                    lists[i].push_back(j);
                    lists[j].push_back(i);
                }
    

    Не похоже на О(1)

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

      Спасибо, я неправ.

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

      Ну так-то это и правда O(1), т.к. все циклы до констант. Правда не знаю тогда, что удивляет автора)))))

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

        Да, тем не менее это именно тот ответ, который мне был нужен, потому что он объясняет ML.

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

С чем связан TL в 15 секунд в задаче C? Есть идеи, какое решение предполагалось [с таким большим временем исполнения] ?

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

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

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

    Возможно, чтоб решения на python'e и других медленных ЯП заходили

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

D за квадрат все решали?

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

Расскажите контример к такому решению C:

  1. K / 2 идем лучшим вариантом, куда можем идти
  2. возвращаемся тем же путем обратно
  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +56 Проголосовать: не нравится
    6 5 30
    ...X.
    .***.
    ..**.
    *..*.
    **...
    ***..
    

    Лексикографически минимальный путь: LLLDDRDRDRDRLRLRLRLRLRLRUUUUUL

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

      Спасибо!

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

      Чёрт. Я придумал полное решение учитывающее такие случаи, но потом успешно убедил себя в том, что их не бывает и отправил более простой вариант.

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

    Вот пример поменьше:

    Ваш алгоритм выдаст: LDDRDULUUR
    А правильно: LDDRDRUUUL

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

    Все-таки, как нормально решать C?

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

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

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

      А я сначала обходом в ширину строил матрицу расстояний w, чтобы для каждой клетки знать значение wij — за какое минимальное количество шагов я могу вернуться из неё в начало. Потом строю лексикографически минимальную строку, на каждом ходу проверяя для данной клетки (i, j), не равно ли количество оставшихся шагов значению wij. Если в какой-то момент это равенство выполняется — восстанавливаю путь назад по матрице расстояний w.

      Сложность получается O(n·m + k), где n·m даёт первый обход, а k — построение пути.

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

Почему в VK можно посылать сообщения самому себе, а в задаче B VK Cup-a — нельзя? :(

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

Можно узнать 49 тест для задачи С?

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

Я не могу понять в чём ошибка?

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

Будет ли разбор, и если уже есть, то скиньте пожалуйста ссылку.