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

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

Привет!

Сегодня в полночь по Москве начнётся квалификационный раунд Яндекс.Алгоритм 2017. Раунд длится двое суток и является виртуальным, продолжительность самого контеста составляет 100 минут. Вы можете начать участие в любой момент времени между 00:00 субботы и 23:59 воскресенья.

Напоминаем, что для участия в турнире нужно зарегистрироваться, это ещё можно будет сделать в течение всего квалификационного раунда.

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

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

Войти в контест!

Напоминаем, что обсуждать условия и решения задач нельзя вплоть до 01:40 понедельника (самое позднее возможное время окончания раунда для участника). После этого можно обсудить задачи и их решения, например, в комментариях к этому посту или к разбору, который мы обязательно опубликуем.

Всем удачи!

UPD: У вас есть ещё около шести часов на то, чтобы принять участие. Не пропустите!

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

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

Why someone submits more than one problem? It is not necessarily!

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

    Why are you doing CP? It is not necessary!

    I like doing contests. That is why I submit more than one problem.

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

      I find CP really fun when doing it in light-mode. But doing it serious -- like five hours contests and multiple consecutive submissions without resting -- is not worthing. Of course it is right for me, not necessarily for other people. And I am curious to know, where lies the source of such a great motivation. How are you not losing your passion during years?

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

    Putting yourself up for the challenge even when there's no reward for it, is what makes you a better Competitive Programmer!

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

      I agree that putting yourself to a CHALLENGE makes better. But I do not agree that EVERYONE who submitted two or more problems was challenged by those problems. Probably those problems were easy for them and there was NO challenge. Yeah I want to made my contribution counter minus infinity.

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

        Not really, some problems were interesting to me and I found some cool ideas in some of the problems. Even solving problems that aren't much hard for you is good to get you used for solving problems fast.

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

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

      When I saw that all of my posts have really negative rating I thought maybe I need change some of my opinions. Then I reflexied for several hours about sport, about technologies, about learning and about why people so differ in their interests. I have slightly changed. But I can't say I know the answers. Too complex questions.

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

1- Can I register not virtually ?

2- How many problems I must solve to be qualified to the next round ?

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

    1- No. Virtual participation is official participation. It just means you can start your contest window of 1 hour and 40 minutes whenever you want before Sunday 20:59 UTC.
    2- One.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. меньше минимальное занятое место за четыре раунда отборочного этапа при равенстве зачетных очков.

Если я не смогу участвовать в каком-то из отборочных раундов, минимальное место будет выбираться из тех раундов, в которых я участвовал?

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

Опять проблема с отправкой файлов из Visual C++. Выдает ошибку компиляции. Только на этой платформе такая проблема и все еще не исправлено.

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

Задачи огонь ;)

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

any hint for problem E Cluster Connection? I tried brute force, and found this sequence: 6, 85, 900, 9450, .. but couldn't find any relation.

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

What's the difference between + and tick in the standings? Also can someone explain the difference between open and blind submission? Why would I resubmit after passing anyway?

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

    Rules say:

    Before submitting a solution to each problem for the first time, the contestant has to choose whether he or she wants to make the submission “open” or “blind”. This decision cannot be changed later. Results will be shown to the contestant immediately after a submitted solution has been tested.

    After making an “open” submission, the contestant is informed whether his or her solution is accepted. If it is not, the contestant is also told the type of error and the index number of the failed test case.

    Solutions that are “blind” submissions are tested on the sample test cases only (from the problem statement). If a solution doesn’t pass these test cases correctly, the contestant is told the type of error and the number of failed test case. If it does pass, the problem is considered to be preliminarily solved. Submitting further solutions to this problem becomes impossible. The final result of testing is announced after the end of the contest.

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

    Tick — successful blind submission, plus — open one. Blind submission is more profitable, because penalty is another. There are formulas in "Rules".

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

Please give some hints (only hints) for Artihmetic Mean Encoding (D) and Cluster Connection (E).

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

как решить F?

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

Как по мне, задача А была сложнее чем B и C. Я что-то упустил в решении, решая ее через хитрый подсчет инверсий сортировкой слиянием? Может есть простой способ

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

    Опубликован разбор

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

    Я решал задачу следующим образом. При поступлении очередного числа v[i] я из set удалял v[i]-1 и добавлял v[i]. Таким образом в конце работы количество элементов в set и было ответом.

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

    Надо создать массив b, где b[a[i]] = i, после этого решается одним тривиальным проходом: если следующее число меньше предыдущего, ans++

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

    У меня прошел такой линейный способ: 1)Заводим массив boolean. 2)Считывая каждое число записываем в ячейку с индексом равным числу true и проверяем равна ли true предыдущая ячейка, если нет ans++.

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

А можно ли дорешивать соревнование?

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

Извините, если слишком банальный вопрос, но как решать задачу B? Я даже написал свой класс City с интерфейсом Comparable, чтобы вызвать Arrays.sort() и потом находить через Arrays.binarySearch() города в массиве и как-то трёхмерные массивы точек и иксов прочёсывать с логикой внутри одного города ИЛИ, а между заданными городами И — если срабатывает, вывести (как-то) в ответ. Но это что-то слишком сложно для второй задачи. Кто сделал проще? Интересует Java. Спасибо!

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

    Ограничения очень маленькие поэтому в бинарном поиске и сортировке нет необходимости. Задача не сложная, но написать надо немало. Создаете HashMap, в который помещаете название городов, массивы с доступными переговорными(индекс — час, если в один час доступно несколько надо написать любую). Например: {null,"First","Second","First",...,"Third"}. null — нет доступной переговорной. На каждом запросе циклом по времени проверяете все нужные города. Если находиться час, в ячейке которого все нужные города имеют не null, то выводим эти ячейки. Вот пример кода, пытался называть переменные "говорящими" именами:

    Code