Solving Jigsaw Puzzle with bare Rust
I participate in a lot of programming competitions and usually, if you show good results, organizers send you some prizes. Typically it is just t-shirts, but at some point, you have too many of them, so you had to make a bed cover from them. But sometimes prizes are more interesting. This time Google HashCode organizers sent a jigsaw puzzle if you advanced to the finals. That was cool, so I decided to solve it.
Online Point Location Algorithm
Round 3 of Meta Hacker Cup 2022 finished a couple of days ago. Today I'll talk about the hardest problem from that round, which was solved only by 3 people. The problem is quite classical, so basically after reading the problem statement, experienced competitive programmers already know what they need to write, but the amount of the code is pretty big, and almost nobody likes geometry problems, so this probably explains why there are so few accepted solutions.
ICFPC 2022
For the third year in a row, I participated in the ICFP Contest as a member of RGBTeam with Roman Udovichenko and Gennady Korotkevich. We won it last year and hopefully did a good job this year as well. The final results are not published yet, but we were in the first place when the scoreboard was frozen (2 hours before the end of the contest). Obviously, some teams could have submitted better solutions during the freeze, so the final results could be a little different.
O(N^2). Часть 2: prefetching
Продолжаю рассказывать о том, как получать AC с простыми решениями, у которых асимптотика сильно хуже чем хотели авторы задачи.
Google AI4Code или мой первый раз на Kaggle
Вчера наконец-то закончилось трехмесячное соревнование от гугла по машинному обучению, где нужно было написать программу, которая умеет понимать взаимосвязь между питоновским кодом и комментариями к нему. На вход вашей программе давался Python ноутбук, который состоит из клеток с кодом и клеток с текстом. Клетки с кодом даны в том же порядке, в котором они были в исходном ноутбуке. А клетки с текстом случайно перемешаны. Цель вашей программы — как можно точнее восстановить исходный порядок.
Генерируем полимино
В недавнем открытом кубке в задаче J в качестве подзадачи нужно было сгенерировать все возможные связные по стороне клеточные фигуры из не более чем четырех клеток. Во время контеста я так и не придумал, как написать код, который это делает, так, чтобы этот код вообще хотелось писать (и чтобы успеть это сделать минут за 5-10).
Local Optimizations Is All You Need
Недавно maroonrk сказал, что задачу ARC142E не взяли в AtCoder Grand Contest (а взяли только в Regular), потому что боялись, что какие-то эвристические решения могут зайти. Мимо такого заявления нельзя было пройти спокойно, и надо было срочно загнать какую-то лажу в эту задачу.
Воспроизводимые бенчмарки
Недавно хотел понять, как лучше написать функцию, которая принимает два массива типа u8 и возвращает первую позицию, в которой они отличаются.
O(N^2)
Каждый раз, когда вижу в олимпиадных задачах ограничение N≤10^5, хочется проверить, стали ли компьютеры достаточно быстрыми, чтобы O(N^2) успел по времени.