В общем, была задача на оптимизацию плана работ: есть набор заказов, и в каждом N тасков. Таски могут зависеть друг от друга или нет, имеют длительность и тип. Ещё есть M работников, каждый из которых может выполнять таски только определённых типов, причём, у каждого своя скорость.
Если все таски в заказе выполнены, фирма получает сколько-то денег. У заказа есть дедлайн, за просрочку штраф (за каждый день просрочки), который вычитается из цены заказа. И ещё фирма тратит деньги за каждый день своей работы независимо от того, как загружены её сотрудники (то есть просто платит зарплаты по сути). Ещё важен учёт праздников и выходных.
Нужно заработать на определённом наборе заказов и работников как можно больше денег. Полный текст задачи и код программы проверки есть в репозитории. Эта задача является изменённым заказом, который мы с напарником решали в реальной жизни: оптимизация работы печатных станков для типографии. Правда, тогда и мы справились так себе, и заказчик в итоге сначала захотел всё вручную сам делать, а потом и вовсе похоронил проект при смене директора.
!!! Не читайте дальше, если хотите сначала попробовать решить самостоятельно, потому что я сейчас опишу эффективные подходы и результаты.
________________________________________
Так вот. Мы с другим экспертом Андреем сразу сели и написали разные варианты, чтобы задать шкалу, по которой будем оценивать решения команд. За пару часов я собрал примитивный жадный алгоритм, который сортировал заказы по прибыльности и укладывал в сетку кое-как, это дало нам нижнюю оценку. Мой алгоритм заработал ~75 млн виртуальных рублей, мы решили для оценки поставить нижней границей 40 млн. То есть всё, что ещё ниже, оценивалось в ноль баллов за качество оптимизации.
Затем Андрей закрылся дома на три дня и вышел на свет со сложным жадным алгоритмом, который очень хитро сортировал заказы и очень хитро укладывал их в сетку, попутно выбирая разные способы этой укладки в зависимости от конкретного заказа. Это позволило заработать ~275 млн рублей. Мы сделали верхней границей для оценки 280 млн.
К сожалению, в итоге только две команды из десяти прошли нижнюю границу, заработав, соответственно, ~91 и ~105 млн. К верхней границе не приблизился никто. И у четырёх команд алгоритм вообще не смог уложить без нарушений задачи в сетку (то есть, например, произвольно менял длительности, накладывал задачи друг на друга, давал одному работнику две задачи в один момент и так далее). Важной ошибкой команд, на мой взгляд, являлся тот факт, что никто не воспользовался возможностью запустить алгоритм на несколько минут и дать ему поработать. По условиям задания, можно было тянуть до 5 минут на одну оптимизацию, но по факту решения команд отрабатывали за единицы и десятки секунд.
На самом конкурсе, пока команды работали, я решил попробовать сделать быстрое (по времени написания) но эффективное решение. Сначала попробовал жадную сортировку + доведение до лучшего варианта методом имитации отжига. В качестве нового состояния я просто менял местами заказы целиком. Этот вариант работал пару минут и дал мне около ~200 млн дохода. К слову, команда-лидер использовала такой же подход, просто не докрутила число итераций и температуру.
Ну и потом я взял готовую либу по реализации классической генетики с особями и скрещиванием. Особью был массив с приоритетами заказов (которые конечно же нужно было аккуратно уложить чистым алгоритмом). Тип скрещивания: scattered. Всего 15 поколений по 20 особей, и это за минуту-полторы давало ~230-240 млн. Считаю, что для конкурса это самый лучший выбор: пишется одним человеком за день и даёт почти максимум, при этом легко настраивается на нужную длительность работы, легко параллелится.
Ну а потом уже дома я посидел и накодил свой вариант сложного жадного с плавающим окном перебора отсортированных заказов и плавающей же укладкой по работникам. Такая штука за две минуты зарабатывает ~281 млн. Но за три дня в условиях стресса я бы такое не сделал, скорее всего.
#dev
💰#DеньгиDревних
| Веспасиан: как спасти империю от банкротства — и ввести налог на мочу
Когда в 69 году н.э. Веспасиан стал императором, Римская империя была на грани финансового коллапса. Гражданские войны, расточительство Нерона и разгул коррупции опустошили казну. По словам историка Светония, в государственной сокровищнице оставалось менее 1 000 золотых монет — сумма, смехотворная для державы, управлявшей 60 миллионами человек.
Веспасиан, выходец из плебейской семьи (его отец был сборщиком податей), подошёл к кризису не как политик, а как практик и финансист. Он понимал: чтобы восстановить порядок, нужно не только сократить расходы, но и найти новые источники дохода — даже самые неожиданные.
🔸 Налог на всё: от проституции до… мочи
Одним из самых известных решений Веспасиана стало введение vectigal urinae — налога на сбор мочи. В Древнем Риме урина использовалась повсеместно:
— в прачечных ( fullonicae ) — как отбеливатель благодаря аммиаку,
— в кожевенных мастерских — для дубления,
— даже в стоматологии — как антисептик.
Сборщики выкупали право на установку общественных писсуаров ( latrinae ), а затем продавали содержимое ремесленникам. Веспасиан обложил эту цепочку государственным налогом.
Когда его сын Тит возмутился: «Разве можно брать деньги за такую мерзость?» — император поднёс ему монету и спросил: «Пахнет ли она?» Получив ответ «нет», произнёс фразу, ставшую крылатой:
«Pecunia non olet» — «Деньги не пахнут».
🔸 Финансовая реформа как стратегия выживания
Помимо «налога на мочу», Веспасиан:
— вернул в казну конфискованные при Нероне земли,
— ввёл плату за использование дорог и портов,
— наладил систему аренды государственных шахт и карьеров,
— отказался от дорогостоящих зрелищ, заменив их полезными проектами — например, начал строительство Колизея на доходы от добычи в Иудее.
Его подход был прост: каждый актив должен приносить доход. Даже отходы.
🔸 Результат: от банкротства — к процветанию
К моменту смерти в 79 г. н.э. Веспасиан оставил сыну полную казну, стабильную налоговую систему и империю, в которой снова работала экономика. Его реформы стали основой для «золотого века» Антонинов.
Мораль:
Сегодня вы платите за подписку на стриминг, доставку еды и облачное хранилище.
Веспасиан бы просто ввёл налог на ваш Wi-Fi — и сказал: «Деньги не пахнут. Особенно если они спасают цивилизацию».
#DD