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

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

Всем привет!

Сегодня в полночь по Москве начнётся марафонский раунд Яндекс.Алгоритм 2017.

Вам будет доступно два дня на то, чтобы написать наиболее оптимальное решение для выбранной нами оптимизационной задачи. Вы можете отправлять свои решения на протяжении всех 48 часов соревнования.

Данный раунд является первым из четырёх отборочных раундов. Не пропустите!

UPD: Финальное тестирование произойдёт завтра. Всем спасибо за участие!

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Access to your account has been temporarily restricted as Yandex suspects it may have been hacked. This may have happened because you have entered your password on a fraudulent website or because your computer is infected with a virus.

First, check your computer for viruses (here's how). Then, answer a security question, create a new password, and request a confirmation code sent via SMS for free. Your account will be unblocked after changing your password.

Also, please check your registration information (in the personal information and email addresses sections) as hackers may have successfully changed it.

What is this, a cheap way to get my phone no.?

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

The system doesn't allow me to submit a solution I have sent before. In a contest where only the last submission counts it's a desired feature, I think.

I have managed to submit by changing a small thing in the code, but still it seems to me that it should be working properly.

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

    Also when I submit too early (less than 5 minutes after the last submit), the site tells me, that I have already submitted that code, although the submission was refused.

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

Java на Яндекс.Контесте похоже (опять) сломана. То, что локально работает 0.01-0.2 секунды, там занимает 0.1-1.1 секунды на Java 7 32 (и какой-то infinity на Java 8). В задачах подобных этой — такое критично.

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

    Ответа до конца контеста так и нет... А между тем, 2 часа "увлекательного" переписывания сабмита на C++ (с кучей memory leakов в результате) == ~+150 баллов... При ровно том же самом коде.

    Скажите хотя бы, починится ли Java к обычным раундам? Или лучше сразу на плюсах писать?

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

      Илья, ну ты же должен понимать, что мониторить комменты на кф все 48 часов у жюри в моём лице (оповещалка здесь придёт только мне) возможности нет. Такие вопросы надо задавать через тестирующую систему, за ней следит гораздо большее количество людей.

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

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

Когда будет тестирование на полном наборе тестов?

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

    Оно будет завтра. Спокойной ночи :)

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

      Когда будут известны результаты финального тестирования?

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

        Они будут завтра. Спокойной ночи :D

        Ну правда. За сутки точно справятся.

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

Мои 5 копеек комментариев: было бы здорово, если бы авторы дали свой код генератора тестов. Если мне не изменяет память, на ТС так делалось. Все равно тесты генерировать так или иначе приходится, а маленькие различия в процессе генерации могут серьезно влиять на статистику тестов (например, количество тестов с разными К может серьезно зависеть от того, перегенерируются ли все параметры теста, или только источики, и т.д.). К примеру, у меня локально есть два решения дающие разницу в 50+ баллов, которые на сервере дают абсолютно одинаковый результат:(

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

    Спасибо за отзыв, для нас это была первая проба пера, и мы с большим вниманием относимся к подобным замечаниям.

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

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

      UPD В финальном на 100 очков больше, чем в public.

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

    В генераторе должен быть код проверки существования решения. Это было бы огромным хинтом, имхо.

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

      В данном случае, его можно бы было оставить функцией-пустышкой: if (!solutionExists()) ...

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

        Это тоже хинт — что существование решения можно проверить быстро. Я когда условие прочитал изначально, не сразу это понял — теоретически, авторы могли какими-то эвристиками строить эти пути, и если не получилось, то перегенеривать. Когда подумал про поток, конечно, всё встало на свои места, но этот момент как-то скользко в условии описан.

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

          Ну так в условии написано "генерируем вот так" и если искать эвристиками, то это противоречило бы условию

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

            Ну там мутно написано, "дальнейшие действия произвести невозможно". Но вообще да, все же из условия следует, что авторы умеют за не очень долго проверять существование. Просто в марафоне обычно не ожидаешь, что существенная часть задачи имеет точное решение :)

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

      Мне кажется, это специфика конкретной задачи. Но даже в таком случае можно было просто сгенерировать 1000 тестов и положить их где-то в свободном доступе для всех участников.

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

      Думаю, что люди из топ-30 это и так все поняли очень быстро, задача-то известная.

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

        Думаю, что это неправда.

        Для меня было неожиданно, что в марафоне требуются высокоуровневые ACM-алгоритмы, поэтому первый час я даже не думал в эту сторону.

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

          Поток всё же general-purpose алгоритм, который активно используется вне ACM. Вот если бы в марафонской задаче было нужно дерево палиндромов или какое-нибудь изощрённое дерево отрезков — было бы более забавно.

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

            Уважаемые, а что вы понимаете под словом "нужно" / "требуется"? Это на то и марафонская задача, что никто из авторов не знает, каково "верное" решение. Мне кажется, что вместо этого потока можно было использовать жадное паросочетание и БФС без особых потерь...

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

              Вполне возможно, что bfs хватило бы. Лично я под словом "нужно" понимал "напрямую применимо".

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

I couldn't participate in the marathon round , will I be able to participate in later stages of the contest ? If yes , how would marathon round affect me?

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

    It is not necessary to participate in all rounds, your final result is calculated only using the rounds you have participated in.

    Refer to the Rules section of the competition.

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

      I just read the rules, in both languages, and didn't find anywhere a phrase about using the rounds you have participated in. Instead, I found that final score for any participant is the sum of the scores for all 4 rounds + the lowest place taken as a tiebreaker. Did I miss something?

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

        I suppose this just meant that the rounds are equally important and you don't drop out (or get any kind of penalty) for not taking part in some of them.

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

        ania says everything correctly, that was the informal description. When you don't participate in a round, you get the zero points and rank infinity, so it is effectively equivalent to not considering this round for you at all. You are not penalized in any manner.

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

          I am not sure what the "lowest rank" means. If lower = worse, then your lower rank becomes infinity if you do not participate, i.e., you lose the tiebreaker. The wording "A Contestant will rank higher [...] if they have higher scores [or] their lowest rank for the four rounds [...] is higher" suggests that this is the case. Also, if the worst rank matters, it would be illogical to not consider this infinity, because then not participating in a round might be a better choice than participating ("I am second in the first round, definitely tiebreaker at least, let's not participate just to not destroy my good standing with respect to the tiebreaker" -- with two rounds and 11 advancers this would seem to be the case).

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

As the round is over, here is my code, around 7500 points on the public tests. Ugly to read, not recommended.

First I generate random pairs of life and magic fountains. I try to connect these pairs along the shortest path (I also tried Hungarian method, didn't work that well). When creating pairs, close fountains have a higher probability to be grouped together. I fill the rest of the map in the following manner: when an empty field has two neighbors of the same region, that empty field gets added to that region. Next I assign fields with only one non-empty neighbor, then the remaining fields.

For the second half of the available time I try to further optimize my best solution so far: select a random border and move it. If the score gets higher, I keep that solution. I sometimes move multiple edges in the same round to exit the local optimum.

This code still times out on two of the public tests. Is anyone ranked higher willing to share his strategy?

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

    I did almost the same, but I generated matching by min-cost-flow with random edge weights. Also I didn't change color of multiple cells at once (was lazy about it :D), but did a lot of iterations. Got about ~7550 points on public testset.

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

    Here is the gist of my method (gets around 7700+, the remaining  ≤ 100 points obtained by relatively small hacks)

    Generate pairs by min-cost-max-flow with all edge costs of 1. Then fill remaining pixels greedily by adding a pixel each time such that the total score is as high as possible after that step.

    Refine this solution by trying to "grow corners" — loop through all possibilities in random order (selecting random pixel, direction, and number of layers  ≤ 10 = MAGIC to grow) and apply an update as long as it improves score or there is time left. Example of "corner growth" at the bottom. Growing corners is useful because it allows to get from a square of size N × N to the one bigger, and square is the shape with the optimal "convexity", I think.

    Hack that brings biggest improvement: when the test case is from the third group, in MCMF instead of making the cost of every edge 1, make cost of using pixels (i, j) such that i or j is divisible by MAGIC=5, equal to 0. In this way, the obtained set of paths is likely to be more disperse, rather than crammed all together around the line joining the squares from which the sources are generated.

    .........           .........
    .........           .xxxxxxx.
    ..xxxxxxy           .xxxxxxxy
    ..x                 .xx
    ..x            ->   .xx
    ..x                 .xx
    ..z                 ..z
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Around 7700 on public tests if implemented in C++ (and 7550 — if in Java).

    First, run min-cost-max-flow to match sources and targets. Add these paths to the solution, and grow them greedily, adding one cell or continuous horizontal or vertical sequence at a time (score := delta_target_function / (5 + number of cells)). Once the field is full, do a similar process of improving solution: move one cell or continuous horizontal or vertical sequence from one group to another if it increases the score (this is tricky implementation-wise, since we have to check we don't disconnect areas; I just ran full connectivity check, but maybe one can do smth smarter and faster).

    Finally, there are many places where one can add randomness here: order of edges in min-cost flow, random fluctuations in greedy & final hill-climbing scores. Add all this randomness, and repeat the procedure for 2 seconds, choosing the best answer. Locally this was giving +200 points (evaluating on 1000 testcases), but on public tests Java version didn't improve much (likely because it didn't have time to do more than O(1) iterations). I didn't have time to evaluate C++ version though.

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

    7668.32

    Generate paths by min-cost-max-flow. Expand them by bfs. Then while possible to increase score do mutations of two types: 1) Take side (edge?) of some region and paint several lines near it in the same color. 2) Take side of some region and fill it with neighbour colors.
    Some hacks like "we can take just part of side" or "let's check improvement after each painting" significantly increased the execution time but also helped to get up from ~7500 to 7670.
    BTW, on my local tests I get ~8150.

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

Потестить-то потестили, а когда монитор откроют? :)

UPD открыли

Спасибо за раунд, было интересно!

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

И в дорешку тоже хотелось бы посдавать.

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

Я правильно понимаю, что топ-128 гарантированно получают футболочки?

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

    Да

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

      То есть, при условии что я не претендую на топ-30 и, соответственно, зачетные очки, в этом раунде занял 254-е место и в последующих раундах занимаю более низкие места, я уменьшаю вероятность выигрыша футболки(так как в соответствии с правилами ранжирование при равенстве очков идет по наименьшему занятому месту, а у большинства участников скорее всего будет ноль очков)?

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

        Нет, участие только увеличивает ваши шансы. Наименьшее место == наилучшее место