Привет! Меня зовут Боря, я довольно много участвую в различных соревнованиях по программированию. Иногда по ходу возникают какие-то интересные истории, которыми хочется поделиться, пока не забыл.

С форматом я пока не определился. Телеграм довольно плохо поддерживает длинные посты с картинками и форматированием, так что их буду постить в https://teletype.in/@bminaiev с небольшим описанием тут. А какие-то короткие вещи будут сразу в этом канале.

Пожелания и предложения можно писать @bminaiev.

https://teletype.in/@bminaiev/cp-simd-optimizations

10^10 операций за 6.5с это не так уж и много, если быть достаточно аккуратным.
#rust #cp #simd

https://teletype.in/@bminaiev/reproducible-benchmarks

Пытаюсь измерять скорость кода, но у меня ничего не получается.
#rust #simd

https://teletype.in/@bminaiev/local-optimizations

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

Прошло столько времени, а я все еще не умею писать бинпоиск, который не входит в вечный цикл

left, right = 0, 10
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        rigth = mid
assert check(left)

Секрет бага во вчерашнем бинпоиске в том, что в строке rigth = mid я опечатался в слове right, а python в этом месте просто создал новую локальную переменную с другим именем и продолжил работать дальше.

https://teletype.in/@bminaiev/polyomino

А вы умеете генерировать все полиминошки из 4 клеток? Я во время контеста долго не мог придумать, как это сделать проще всего, но в итоге оказывается, что это не так сложно.

https://teletype.in/@bminaiev/google-ai4code

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

https://teletype.in/@bminaiev/prefetching

Еще одна история про низкоуровневую оптимизацию кода, чтобы получить Accepted с решением с неправильной асимптотикой.

На CodeChef обновили компилятор Rust до какой-то приличной версии, так что теперь там тоже можно писать контесты!

В часть этого задача, на которой можно потренироваться сдавать решения за квадрат https://www.codechef.com/problems-old/MAXPREFFLIP

Дан массив из 10^5 чисел и число k. Нужно домножить не больше k элементов массива на -1, чтобы максимальная префиксная сумма массива была как можно больше. Нужно посчитать эту максимальную префиксную сумму для всех k от 1 до 10^5.

В ближайшую пятницу начинается трехдневный командный контест ICFPC2022. Если вы никогда его не писали — очень рекомендую. Отличительная особенность в том, что каждый год контест делают новые организаторы (так что теоретически может не повезти и будет скучно, а может и наоброт очень весело).

Чтобы проникнуться духом соревнования можно, например, почитать вот этот блог: https://dastapov.dreamwidth.org/131798.html

На прошлых выходных поучаствовали в ICFP Contest 2022. Написал про саму задачу и наше решение.

Для разнообразия эта статья на английском.

https://teletype.in/@bminaiev/icfpc-2022

Потратил две недели на участие в конкурсе от Huawei про наиболее эффективное расположение виртуальных машин по физическим, но в итоге ничего умного так и не написал, так что рассказывать особо нечего.

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

1. https://www.youtube.com/watch?v=Z8SHvJnGUCM Научно-популярный рассказ от Андрея Гейна про то, что реальный мир устроен сильно сложнее чем часто его себе представляют программисты. Там про всякие частные случаи, которые бывают в картах, датах/временах, именах и каких-то других штуках. Чем-то похоже на статьи типа "Falsehoods programmers believe about *".

2. https://www.youtube.com/watch?v=dFquxC6qTSA Доклад Алексея Салмина про то, как устроена память в линуксе. Он достаточно хардкорный и если, например, вы никогда не пытались читать What every programmer should know about memory, то скорее всего воспринимать его будет сложно. Но мне понравилось. Например, узнал из него почему стандартные размеры hugepages (в x86_64) именно 2мб и 1гб, а не какие-нибудь другие.

В субботу прошел третий раунд Meta HackerCup. Чтобы пройти в финал, нужно было попасть в топ25, что я успешно и сделал (ура!). Но пост не об этом.

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

Стандартный алгоритм — сканирующая прямая и персистентное декартово дерево. Что в целом не так сложно, но писать довольно много (я, например, не успел). После конца контеста Паша Кунявский рассказал (https://www.tgoop.com/kunyavskiy_channel/120) о другом алгоритме, который, как мне кажется, сильно проще этого, но про который я раньше не слышал.

Так что решил не держать это знание в себе, а поделиться с человечеством: https://teletype.in/@bminaiev/online-point-location

TON Hack Challenge

Поучаствовали сегодня в TON Hack Challenge. Было весело (по крайней мере мне)! Участникам дали 8 смарт-контрактов, в каждом из которых есть баг, который позволяет забрать из него все деньги. Причем контракты лежат а реальном блокчейне TONа, и на них есть реальные деньги (суммарно 30к TON = 34к$). Так что если вы поняли, как воспользоваться багом, сразу можете перевести выигрыш на свой кошелек.

Такой формат выглядит довольно прикольно, явно добавляет азарта во время соревнования. Но есть и обратная сторона — если вы решили задачу вторым, то выигрываете 0. У нас, собственно, так и получилось. Почти во всех задачах мы нашли баги и придумали нужные идеи, но не смогли их реализовать. Тут явно не хватило реального опыта взаимодействия с продакшен контрактами в реальном блокчейне (из него у нас только "я вчера за вечер научился отправлять запросы через какую-то javascript библиотеку"). А соревноваться в скорости с людьми, которые что-то делают с TON-ом каждый день, очень сложно.

Интересно, можно ли придумать схему, в которой участники, которые решили задачи медленнее, тоже что-то получают? Не понятно как это реализовать технически. Все транзакции в блокчейне публично доступны, так что когда кто-то решил задание, другие смогут понять, как он это сделал. И ничего не мешает человеку, который уже решил задание, получить выигрыш еще раз с другого аккаунта.

Расскажу еще кратко про наш прогресс по некоторым заданиям, вдруг будет интересно. Сами задания (и решения) можно посмотреть тут.

1. Mutual funds. Почти сразу поняли, что проблема в отсутствии impure у функции authorize, так что нужно только составить нужный request. Request потом кладется в c5. Что такое c5? (Этот вопрос же явно не возникает у людей, которые пишут смарт контракты каждый день?). Ага, с5 это output actions. А какой у него формат? Вроде бы какой-то связный список из действий, которые будут исполнены, но где бы найти его точное описание? У TON-а явно есть проблема с тем, что документация все разбросана по разным местам, и никогда не знаешь, где именно найдешь ответ на свой вопрос. Какой-нибудь TL-схемы с форматом output actions мы так и не нашли, поэтому просто запустили какой-то другой контракт локально, который их генерирует и смотрели, как они выглядят. Начали пытаться сформировать такие же клетки руками, но на этот момент кто-то уже успел взломать контракт, так что смысла в этом уже не было.

3. dao. Баг с отрицательным количеством голосов мы тоже нашли довольно быстро, оставалось только им воспользоваться. Естественно, пока я разбирался в каком формате что нужно отправлять, этот контракт тоже уже кто-то взломал.

4. Lottery. Из первых 5 контрактов этот не взламывали дольше всего. И тут опять же идейно все было понятно. По сути было две задачи. Нужно подобрать seed, что set_seed(seed); rand(10000) = 7777 было бы правдой. А потом понять, как предсказать cur_lt() во время транзакции. Цикл, чтобы найти нужный seed, я написал довольно быстро, осталось разобраться с cur_lt(). Для начала мы не знали, что это вообще такое. И тут происходит стандартная цепочка по поиску документации. Идешь в stdlib.fc, видишь, что интересует asm функция LTIME, идешь в tvm.pdf. Там написано, что это "logical time", а еще что это "GETPARAM 5". Отлично, а что делать с этой информацией? Как это связано с реальной жизнью и откуда он вообще берется не очень понятно. Потом мы нашли, что какой-то "LT" показывается во всяких explorer-ах с транзакциями, и что в принципе текущий lt можно узнать через javascript библиотеку. Но как он связан с тем, который будет потом, когда будет исполняться наша транзакция? Экспериментально мы установили, что с момента его получения в коде, до исполнения транзакции он увеличивается на несколько миллионов и два. Но угадать на сколько миллионов, видимо, сложно. Мы подумали, что можно было бы посылать internal сообщения не через стандартный кошелек, а через свой собственный, который бы в коде вычислил cur_lt, но деплоить свои кошельки мы не умели =/ В общем, к этому моменту уже кто-то и эту задачу решил.

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

6. Vault. Мы заметили, что vault не игнорирует bounce сообщения, и что проверка на op == op_not_winner выглядит странно. Но не придумали как заставить database отправить невалидный запрос.

7. Better bank. Поняли, что есть какая-то проблема с race conditions, когда контракт отправляет сам себе деньги, а между этими событиями ему приходит другой запрос, но не справились понять, что конкретно будет происходить.

8. Dehasher. Забавно, что когда-то давно я помогал делать систему тестов в toncli, и там тоже нужно было уметь запускать чужие функции, которым не доверяешь, и было понятно, что сделать это совсем по хорошему вряд ли получится. Но с того момента прошло кучу времени, и я уже совсем забыл как там все работает. У меня получилось сформировать запрос с функцией, которая хотя бы просто убирает int со стека и кладет пустой slice, и ничего не портит на стеке, и это уже считаю своим большим успехом. Но придумать как задачу решить мы так и не успели :)

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

Каждый раз, когда взаимодействую с миром блокчейна, меня поражает смелость людей, которые пишут для них смарт-контракты. Если в контракте есть хотя бы несколько сотен строк, то почти наверняка в нем будут баги. Скорее всего какие-то не очень важные, которые вряд ли приведут к потере всех денег. Но что если там тысяча строк? А если несколько тысяч? Чисто статистически там будут баги, сколько бы вы не написали тестов.

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

На выходных вот прошел контест от Telegram по поиску багов в их контракте для покупки красивых имен (я даже что-то выиграл). И несмотря на то, что разработчики Telegram явно имеют опыт написания надежного кода, какие-то баги в контракте все равно нашли.

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

Например, в TON есть особые bounced сообщения, которые большинство контрактов хотят просто игнорировать. Но нужно сделать это в явном виде и легко забыть написать код, который будет это делать. Почему нельзя было сделать поведение по умолчанию другим? Или заставить разработчиков писать два обработчика сообщений?

Еще, например, там нет автоматического подсчета текущего количества денег (который учитывает сообщения, которые будут отправлены). После этого в большом количестве контрактов разработчики должны по всему коду протаскивать переменную my_balance и не забывать ее правильно обновлять (что сложно).

А еще все функции по умолчанию считаются чистыми, и, если у них нет возвращаемого значения, просто игнорируются. Например, вы можете написать функцию, которая проверяет валидность данных, забыть добавить модификатор impure, и никаких проверок не будет происходить. Почему нельзя было сделать impure значением по умолчанию?

Если вы дизайните какой-то API, и хотите сделать какое-то неочевидное/ломающее поведение по умолчанию, лучше вместо этого заставьте пользователя явно сделать выбор самому.

Площадь многоугольника

Недавно вычислял площадь выпуклого многоугольника. Для этого существует очень простой алгоритм. Нужно по всем ребрам просуммировать их "ориентированную площадь".

Есть разные варианты того, что считать "ориентированной площадью". Например, можно считать площадь треугольника, у которого одна из вершин точка (0, 0), а две других — концы ребра. В зависимости от того, какая вершина видна под меньшим углом из начала координат, площадь нужно взять с плюсом или с минусом.

Получается простой код:

fn area(pts: &[Point]) -> f32 {
let mut res = 0.0;
for i in 0..pts.len() {
let p1 = pts[i];
let p2 = pts[(i + 1) % pts.len()];
res += p1.x * p2.y - p1.y * p2.x;
}
res.abs() / 2.0
}

Этот способ называют формулой Гаусса.

Иногда используют площади трапеций, но суть от этого не меняется.

Но не все так просто! Вчера я написал этот алгоритм, посчитал площадь квадрата 1х1 и получил 0.0. Проблема была в том, что хоть квадрат и был маленьким, его координаты были порядка нескольких тысяч и хранились в f32. Казалось бы у типа f32 есть 23 бита мантиссы и их должно хватать, чтобы сохранить число порядка нескольких тысяч. Но на самом деле проблема в том, что при вычислении векторного произведения нужно перемножить два числа порядка нескольких тысяч (результат уже нельзя абсолютно точно сохранить в f32), а потом вычесть такое же по порядку число. От этого накапливается погрешность, и получается 0.0 в результате.

Как исправить алгоритм? Довольно хорошо работающий способ — вместо точки (0, 0) взять первую точку многоугольника, и все векторные произведения считать от нее:

fn area(pts: &[Point]) -> f32 {
let mut res = 0.0;
for i in 0..pts.len() {
let p1 = pts[i] - pts[0];
let p2 = pts[(i + 1) % pts.len()] - pts[0];
res += p1.x * p2.y - p1.y * p2.x;
}
res.abs() / 2.0
}

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

Финал ICPC

Уже завтра пройдет финал ICPC (одно из самых престижных соревнований по программированию). Само соревнование проходит в этом году в Дакке, так что начало в 5 утра по UTC :(

На YouTube будет трансляция с комментариями (еще есть трансляция на русском). Скорее всего где-то тут будет табличка с результатами.

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