A long time ago there was a competition called Deadline24, which I really enjoyed! Unfortunately, the last edition of it was in 2018. In that competition, you need to write a program, which connects to the server via TCP and plays some game. Usually, the game is turn-based, so you need to read the current state, make a move, wait for the next turn, and so on.

I like this format, so as a hobby project, I decided to write a server for a game in the same format. The game itself is very simple. You are playing as a circle, which flies around the field, and need to collect as many other circles as possible. The only hard part is that you can't change your speed instantly, you can only change acceleration.

The contest is already live! You can watch the current game in real-time: https://aicontest.dev/ and read more detailed rules of the game: https://github.com/bminaiev/aicontest.dev/blob/master/README.md

Consider writing a bot for it! In two weeks top-3 players from the "Highest Scores" (the biggest score achieved in any game) tab will get 100, 50 and 25 TON from me.

Also, I am very interested in the feedback about this game:

• Do you like the format in general?
• Do you like a specific game?
• What could be improved?

UPD. The contest has finished. Congratulations to the winners:

1. al13n — 175 points
2. progiv-rust-main — 160 points
3. eulersche_Zahl — 150 points

Please send me your details in DM.

Also, the server will continue working, so if you want to participate, you still can do it.

I really like peltorator's idea to encourage people to write blog posts about interesting ideas. I don't have new and rare stuff to share, instead, I just want to share some insights about how Simulated Annealing works.

Sorry for cross-posting, but the actual blog could be found here: https://bminaiev.github.io/simulated-annealing. It contains a lot of dynamic plots, which are hard to embed inside the CodeForces blog (and I really suggest checking the blog on the desktop, not the phone).

The blog was inspired by Psyho's Twitter thread. If you haven't seen it — check it out!

Also, I don't really have a lot of real experience with SA, so some facts or ideas in the blog could be wrong. Would be really interested to hear feedback from more experienced SA users :)

In the hardest problem of Meta HackerCup 2022 Round 3 it was needed to write an algorithm for fast points locations. Basically, you were given a lot of polygons and a lot of points. For each point, you need to find the smallest polygon, which contains it. In the hardest version of the task, points are created based on previous answers, so you can't solve it offline.

I believe everybody who solved this problem during the contest used the same algorithm with sweep-line and persistent treap (or just std::set, but it doesn't work for online version of the task).

After the contest PavelKunyavskiy told me that it is possible to solve this task with just a segment tree (but the complexity is $$$O(\log^2 n)$$$ per query). I haven't seen this algorithm before, so I wrote an explanation of it here: https://teletype.in/@bminaiev/online-point-location.

Also after a discussion with izban I think it is possible to improve the complexity of the algorithm with fractional cascading, but it is not very straightforward (and will work slower in practice).

Я часто видел как в задачах кто-то сдавал простое решение за $$$O(n^2)$$$, хотя авторы этого явно не хотели. Обычно секрет в том, чтобы писать код, который хорошо векторизуется (использует всякие SIMD инструкции), но без опыта делать это получается плохо, потому что нет интуиции, что будет работать быстро, а что нет.

Когда я увидел задачу 1701F - Точки и TL=6.5с решил, что это отличный шанс с одной стороны написать решение за квадрат, которое получит AC, а с другой — записать сам процесс оптимизации кода, вдруг кому-то будет интересно.

Получилась вот такая статья. Там довольно много вещей, которые специфичны только для Rust, но я думаю, что в С++ есть аналогичные проблемы/решения.

А еще подписывайтесь на мой канал в Telegram, чтобы у меня была мотивация писать что-то еще. Там скорее всего будет не только про олимпиады, а в целом про программирование.

P.S. надеюсь на CF не банят за саморекламу :)

Привет, Codeforces!

Мы с радостью сообщаем вам, что компания ВКонтакте совместно с площадкой Codeforces вновь проводит чемпионат VK Cup. К участию в VK Cup 2018 допускаются команды до двух человек, так как практика парного программирования широко распространена во всем мире, в том числе и ВКонтакте. За призы и звание победителя приглашается побороться русскоязычным молодым специалистам, студентам, школьникам и просто любителям алгоритмов и программирования.

Лучшие 20 команд по результатам отборочных интернет-этапов будут приглашены в финал соревнования, который состоится 10 — 13 августа 2018-го года в прекрасном городе Санкт-Петербурге. Компания ВКонтакте покроет расходы на проезд и проживание финалистов, которые будут бороться не только за звание лучших из лучших, но и призовой фонд чемпионата. Как и в прошлом году призы соревнования связаны с круглыми числами в двоичной системе счисления:

• 1 место — 1048576 рублей
• 2 местo — 524288 рублей
• 3 местo — 262144 рубля
• 4-8 места — 131072 рубля

Всем привет!

Может кто-нибудь где-нибудь видел задачу, в которой нужно поддерживать лес деревьев и делать на нем какие-то операции? Например, задача в которой требуется поддерживать следующие операции:

• Подвесить одно дерево к вершине другого

• Удалить ребро

• Сказать, находятся ли две вершины в одном дереве (или какой-нибудь другой запрос)

Может кто-нибудь знает, как можно решать такую задачу, кроме как с помощью link-cut tree или хранения обходов деревьев в декартовых деревьях?

Буду очень благодарен за ссылки на задачи и мысли по поводу того, как проще всего такое решать!

Всем привет!

Приглашаю вас принять участие в Codeforces Round #253, который начнется в четверг 19 июня в 19:30 MSK. Раунд будет проходить в обоих дивизионах.

Это мой первый раунд Codeforces, и я надеюсь, что вам он очень понравится!

Большое спасибо Gerald за помощь в подготовке раунда. Также хочется поблагодарить MikeMirzayanov за создание удобной платформы для проведения соревнований. Также благодарю тестеров этого раунда: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul. А еще Delinur за перевод условий на английский.

Не пропустите шанс получить удовольствие от решения интересных задач!

UPD. Распределение баллов по задачам:

Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

UPD2. Соревнование завершено, всем спасибо за участие!

Поздравляем победителей Div1:

1) tourist

2) scott_wu

3) stevenkplus

3) gs12117

5) GlebsHP

А также победителей Div2:

1) tafit3

2) thnkndblv

3) MIT3

4) lucaslima

5) liuzhijian

Особенно хочется поздравить tourist, единственного, кто решил все пять задач, а также единственного, кто решил задачу 442E - Гена и второе расстояние!

Разбор задач уже опубликован.

Расскажите, как решается A, C, H?

Паблик ВКонтакте "типичный программист" организовал контест: объявление.

Призов пока нет, а условия не вычитаны, но все равно какие-то задачи могут показаться интересными. До конца контеста осталось меньше суток, так что желающие поучаствовать должны поторопиться:)