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

Автор tourist, 4 недели назад, По-русски
logo

Всем привет!

Мы, команда RGBTeam (qwerty787788, Romka и tourist) очень любим эвристические соревнования по программированию и очень грустим из-за того, что с каждым годом их становится всё меньше и меньше. И вот, как-то однажды мы подумали, что хватит это терпеть, и решили организовать своё соревнование :) Несмотря на то, что часто такие идеи остаются лишь идеями, в этот раз мы были полны решимости довести дело до конца и сейчас хотим пригласить вас всех поучаствовать в первом и, хочется надеяться, не последнем Code Weekend #1!

Соревнование пройдёт в формате, довольно близком к ICFPC/Hashcode — будет дана одна задача и несколько десятков тестов к ней. Участникам нужно будет отправить на каждый тест наилучшее (согласно правилам задачи) решение данного теста, которое может быть получено любыми алгоритмами, написанными на любом языке и работающими любое время. В середине соревнования условие задачи будет расширено, а также добавлены новые тесты.

Соревнование начнётся 7 июня в 21:00 UTC и продлится 48 часов. Через сутки после начала, 8 июня в 21:00 UTC будет выложена вторая, расширенная версия условия вместе с набором тестов для неё. Соревнование заканчивается ещё через сутки после опубликования второй версии условия, 9 июня в 21:00 UTC. Расширенная версия условия будет надмножеством базовой версии. То есть, если предположить, что задача звучит как "дана шахматная позиция, найдите лучший ход", то в базовой версии условия могут быть только пешки, слоны и кони, а в расширенной версии появятся ладьи и ферзи.

Участие в соревновании подразумевается командное, размер команды не ограничен, но мы постарались сбалансировать задачу так, чтобы у больших команд не было сильного преимущества над маленькими командами, поэтому рекомендованный размер команды — 1-4 человека.

В отличие от ICFPC, упор в соревновании будет сделан на эвристические алгоритмы, а не на функциональное программирование (хотя в последние годы и на ICFPC не было ничего про ФП).

Внимание! Соревнование пройдет на отдельном сайте https://codeweekend.dev, на котором нужно зарегистрироваться (один раз на команду). Все объявления во время контеста будут делаться в дискорд-чате, так что вступайте в него по ссылке https://discord.gg/M6pG5zp3DF. Обязательно зовите поучаствовать друзей, подруг, друзей подруг и всех остальных, кому это может быть интересно :)

UPD. Наш контест любезно согласились проспонсировать TON Foundation, за что им огромное спасибо!

В связи с этим, в соревновании будут разыграны следующие призы.

  • 1-е место — 400 TON
  • 2-е место — 300 TON
  • 3-е место — 200 TON
  • 4-е место — 100 TON

Дополнительно:

  • 1-е место по итогам первого дня соревнования — 111 TON
  • В конце каждой минуты соревнования текущий лидер (если есть хотя бы одна команда с ненулевым результатом) получает 0.1 TON.
  • 300 TON будут распределены поровну за лучшее решение каждого теста по итогам соревнования. Например, если всего будет 10 тестов, по первым трём лучший результат будет у команды А, а по остальным семи у команды В, то команда А получит 300/10*3 = 90 TON, а команда В — 300/10*7 = 210 TON.

В случае равенства баллов выше располагается команда, набравшая свои очки ранее.

Таким образом, суммарный призовой фонд соревнования составит более $10000 по текущему курсу.

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

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

omg! tourist blog!

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

My pet wanted this contest badly. Thanks tourist.

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

i want a postcard written by tourist as prize although i absolutely can't get it :)

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

This is really neat. I really enjoy the heuristic contests as well!

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

Cool. It would be nice to save the leaderboard after the first 24 hours (and announce winners of day 1).

Prizes attract strong participants, which makes the competition more interesting for everybody. An incentive to participate is even more important for a long competition. So I hope that you do find a sponsor (at least for future editions). Just ask Huawei.

Possible prizes without sponsors: playing an online (board?) game with the organizers; appearing in the problem statement of Code Weekend #2.

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

I showed this to my pet racoon and he is very excited

Look how happy Pedro is
»
3 недели назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Olala! My pet codehorses will enjoy that.

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

thanks tourist

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

Discord invite has expired

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

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

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

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

Is it rated?

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

What’s the maximum team size??

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

What’s the maximum participation limit??

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

    Technically, there is no limit, but we believe that participating with more than 4-5 participants per team does not make much sense.

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

    I am also from India, A NIT student, you IIT people only create monopoly in Indian society, you never make our country to win first rank in any Codeforces round, curse on all you. Our Indian Cricket team making all of us proud but you people are curse, donot know when my country will win first prize

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

I am looking for a teammate to participate in this competition. I have participated in other heuristic contests before, but I would like to learn more and improve.

Ideally, we would have similar rating so that both of us can enjoy the contest. My timezone is GMT+2. Contact via DM if you are interested.

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

RGBTeam has 3/4 participants. I can be the 4th.

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

Cool.

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

The contest starts in 4 hours!

Also, note that after every minute of the contest, we award the current top-1 team with 0.1 TON. So, if you have good prototyping skills and code simple solutions quickly, you could earn some easy money :)

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

Thank you for the contest, it was really interesting. Is it going to be hosted so that we can submit after the contest ends?

On another note, could someone share their top 10 approaches for the contest (especially part 2)? We tried a greedy heuristic with a little bit of ‘poor man’s RL’, but we had a hard time tuning it to task 2.

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

I applaud the organizers. I don't remember an optimization competition that was so well prepared. Smooth platform and visualization, efficient judging, reasonably small tests (no N=1e6), good variety of tests. At any moment of the competition, no one person was winning by holding maximum on all tests. I'm not aware of any bugs or issues (maybe because I slept for the first 8 hours of the competition). The problem was fine too.

I participated with mareksom and we got 8th place. We did well with the harder version so here's the solution.

Greedy solution, no annealing etc.

  1. Run BFS from your current position. For every point on the grid, find the smallest number of steps to get there, in case of ties minimize the total fatigue. (I didn't have time to implement allowing for a few more steps to get smaller fatigue.) For efficiency, only consider moving with the full speed to the border of the circle of radius SPEED. Exception: from the starting BFS position, consider all O(SPEED^2) moves to all points inside of the circle. This way, you will reach everything in the grid in an almost optimal way.
  2. For every point on the grid, see what monsters you could attack from there. Try different subsets and order to attack.
  3. Among all possibilities (where to move, subset&order of monsters to attack from there), choose the one that maximizes some heuristic function, e.g. minimize fatigue, then maximize gold/turn, then maximize exp/turn.
  4. Try different heuristic functions. Choose a random turn (or level) when you switch from maximizing exp to maximizing gold. If there are ties of where to go (in order to attack the same monsters anyway), choose a random option.
  5. Move back to step 1 unless you run out of turns.
  • »
    »
    6 дней назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Thank you for sharing your solution!

    One thing that has been a little sad in my optinion about optimization contests is that the source code of the solutions never gets released, so if one wants to get better at it there's virtually no way. Sadly, it has been the same for this contest (as no source codes would get uploaded anywhere to start with), but I personally hope to see a more open-sourced environment for optimization contests in the future.

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

      I think it's worth asking on Discord whether anyone would be willing to share their code on GitHub or another platform — maybe some people won’t mind.

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

Thank you! It was fun =)