This media is not supported in your browser
VIEW IN TELEGRAM
Шестой делает подобное в больших масштабах. Он ищет некоторые участки фигуры, которые можно отразить не влияя на растяжение, и также пытается использовать это для решения задачи.
Простейший вариант такого участка — точка, соединенная только с двумя другими точками
Простейший вариант такого участка — точка, соединенная только с двумя другими точками
This media is not supported in your browser
VIEW IN TELEGRAM
А вот так выглядит совместная работа всех перечисленных мутаторов на примере решения первой задачи
Бонусы — это сложно.
Нет, у нас определенно есть некоторый прогресс. Например, мы переписали нашу решалку, чтобы она научилась находить решения с бонусами. Мы слегка оптимизировали ее под такие задачи. Мы даже нашли сколько-то приличных решений с бонусами!
Вот только пользоваться этими бонусами мы пока не умеем.
С Глобалистом все более-менее понятно. Небольшие изменения в алгоритме и вот мы уже учитываем растяжение глобально, что дает нам кучу новых возможностей для решения. А вот Сломанная Нога напрочь сломала нам мозги и всю существующую структуру кода.
Как промышленные программисты, мы написали хорошую инфраструктуру. Система типов, удобное хранение всех возможных решений, их автоматическая отправка и куча полезных методов для работы с задачками. И во все это сияющее великолепие ну никак не влезает взявшаяся из ниоткуда дополнительная точка, даваемая бонусом BREAK_A_LEG.
Что делать? Долго и сложно переписывать это все. Тем и заняты, параллельно ковыряя отдельные задачки и внося мелкие улучшения в другие куски системы.
Нет, у нас определенно есть некоторый прогресс. Например, мы переписали нашу решалку, чтобы она научилась находить решения с бонусами. Мы слегка оптимизировали ее под такие задачи. Мы даже нашли сколько-то приличных решений с бонусами!
Вот только пользоваться этими бонусами мы пока не умеем.
С Глобалистом все более-менее понятно. Небольшие изменения в алгоритме и вот мы уже учитываем растяжение глобально, что дает нам кучу новых возможностей для решения. А вот Сломанная Нога напрочь сломала нам мозги и всю существующую структуру кода.
Как промышленные программисты, мы написали хорошую инфраструктуру. Система типов, удобное хранение всех возможных решений, их автоматическая отправка и куча полезных методов для работы с задачками. И во все это сияющее великолепие ну никак не влезает взявшаяся из ниоткуда дополнительная точка, даваемая бонусом BREAK_A_LEG.
Что делать? Долго и сложно переписывать это все. Тем и заняты, параллельно ковыряя отдельные задачки и внося мелкие улучшения в другие куски системы.
- «Ваня второй раз переписывает стейт, очень удобно (будет)»
- «Как переписывает? Мы же написали идеальный!»
За ночь ситуация с бонусами стала еще сложнее. В спецификацию добавили третий бонус, WALLHACK — он позволяет одной из вершин размещаться за границами дыры. Как и всем ее вершинам, соответственно.
А еще в задачах начало появляться по несколько доступных бонусов. И по несколько бонусов, которые можно взять, и по несколько бонусов, которые можно использовать. Хотя на последнее наложено ограничение, больше одного бонуса в задаче использовать нельзя. В любом случае, вариативность решений еще немножко подросла. Теперь мы можем решить, взяв первый бонус, взяв второй, взяв оба, ни взяв ни одного, взяв первый бонус с использованием Глобалиста, взяв оба бонуса с использованием BREAK_A_LEG, не беря бонусы с использованием WALLHACK…
Можно еще не решить в принципе. У нас есть несколько нерешенных задачек, так что одновременно с дотачиванием модели и алгоритма мы решаем кое-какие старые задачки. И придумываем новые мутаторы.
До конца контеста 27 часов — посмотрим, что еще интересного мы успеем накодить.
- «Как переписывает? Мы же написали идеальный!»
За ночь ситуация с бонусами стала еще сложнее. В спецификацию добавили третий бонус, WALLHACK — он позволяет одной из вершин размещаться за границами дыры. Как и всем ее вершинам, соответственно.
А еще в задачах начало появляться по несколько доступных бонусов. И по несколько бонусов, которые можно взять, и по несколько бонусов, которые можно использовать. Хотя на последнее наложено ограничение, больше одного бонуса в задаче использовать нельзя. В любом случае, вариативность решений еще немножко подросла. Теперь мы можем решить, взяв первый бонус, взяв второй, взяв оба, ни взяв ни одного, взяв первый бонус с использованием Глобалиста, взяв оба бонуса с использованием BREAK_A_LEG, не беря бонусы с использованием WALLHACK…
Можно еще не решить в принципе. У нас есть несколько нерешенных задачек, так что одновременно с дотачиванием модели и алгоритма мы решаем кое-какие старые задачки. И придумываем новые мутаторы.
До конца контеста 27 часов — посмотрим, что еще интересного мы успеем накодить.
За 24 часа до конца контеста организаторы добавили флекс
Даже SUPERFLEX — последний новый бонус, позволяющий выбрать одно ребро (организаторы использовали формулировку up to one) и деформировать его на какую угодно величину. Ну то есть его растяжимость становится бесконечной. А еще добавили новых задач и по одному дополнительному бонусу в каждую существующую.
Мы же как раз заканчиваем адаптировать наш алгоритм под старые бонусы. GLOBALIST и WALLHACK уже почти побеждены, BREAK_A_LEG на очереди. Интересных алгоритмических деталей пока немного, основная работа была в обновлении нашего кода под новые условия.
Например, для получения бонуса нужно было научиться «закреплять» некоторую вершину на точке с бонусом и не рассматривать другие решения. А еще сохранять в базу всякую дополнительную информацию, чтобы отдельно хранить решения с разными условиями (с использованием бонусов, со взятием бонусов, с разными вариантами использования бонусов и так далее). Ну и, разумеется, использование бонусов влияет на работу функцию оценки — GLOBALIST изменяет оценку растяжимости, WALLHACK добавляет дополнительное условие в оценку «влезаем ли мы в дыру?» и так далее.
Обсуждаем новые решения, фиксим баги, помогаем кое-где алгоритму исправлять ошибки и стабильно держимся за счет этого в районе 18-го места (вот только что на 17 переместились). Посмотрим, смогут ли бонусы вытянуть нас повыше.
Даже SUPERFLEX — последний новый бонус, позволяющий выбрать одно ребро (организаторы использовали формулировку up to one) и деформировать его на какую угодно величину. Ну то есть его растяжимость становится бесконечной. А еще добавили новых задач и по одному дополнительному бонусу в каждую существующую.
Мы же как раз заканчиваем адаптировать наш алгоритм под старые бонусы. GLOBALIST и WALLHACK уже почти побеждены, BREAK_A_LEG на очереди. Интересных алгоритмических деталей пока немного, основная работа была в обновлении нашего кода под новые условия.
Например, для получения бонуса нужно было научиться «закреплять» некоторую вершину на точке с бонусом и не рассматривать другие решения. А еще сохранять в базу всякую дополнительную информацию, чтобы отдельно хранить решения с разными условиями (с использованием бонусов, со взятием бонусов, с разными вариантами использования бонусов и так далее). Ну и, разумеется, использование бонусов влияет на работу функцию оценки — GLOBALIST изменяет оценку растяжимости, WALLHACK добавляет дополнительное условие в оценку «влезаем ли мы в дыру?» и так далее.
Обсуждаем новые решения, фиксим баги, помогаем кое-где алгоритму исправлять ошибки и стабильно держимся за счет этого в районе 18-го места (вот только что на 17 переместились). Посмотрим, смогут ли бонусы вытянуть нас повыше.
Смогли, двенадцатое место взято! Технические детали будут чуть позже.
- У нас какой-то ужасный Time to Market — мы фичу написали пять часов назад, а очки она начала приносить только сейчас
- Да ладно! Прикинь у продуктов в Контуре был бы такой Time to Market?
Фича, которую мы написали — это самая современная версия нашего решателя. По сути, это все еще перебор рандомных вариантов с постоянной оценкой результата, но сильно-сильно прокачавшийся. Мы добавили туда новых мутаторов (и продолжаем работать над ними), сделали два разных варианта стартовой позиции (второй изначально привязывает ребра фигуры к ребрам дыры, что частенько помогает найти более оптимальные решения) и пофиксили очень много мелких ошибок.
А еще мы собираем бонусы. И сами бонусы, и решения с бонусами. Но сабмиттить их пока рано.
С бонусами выходит вот какая история. Допустим, мы решили задачу 1, получили там бонус, с помощью этого бонуса идеально решили задачку 4 и залили это решение. Что произойдет, если мы зальем новое решение задачи 1, которое не берет бонус?
А ничего хорошего не будет, отменится наше идеальное решение задачи 4. А если задача 4 брала бонус, на котором завязано решение задачи 5…
Короче, бонусы производят цепочку зависящих друг от друга решений. А значит, заливать использующие бонусы решения нужно массово — предварительно посчитав, что именно такая последовательность бонусов даст нам наилучший результат. И теперь мы планируем искать наиболее оптимальные решения и их комбинации — пока что не заливая их на сервер, только запоминая в базе. А вот завтра…
А что будет завтра — интрига даже для нас.
- Да ладно! Прикинь у продуктов в Контуре был бы такой Time to Market?
Фича, которую мы написали — это самая современная версия нашего решателя. По сути, это все еще перебор рандомных вариантов с постоянной оценкой результата, но сильно-сильно прокачавшийся. Мы добавили туда новых мутаторов (и продолжаем работать над ними), сделали два разных варианта стартовой позиции (второй изначально привязывает ребра фигуры к ребрам дыры, что частенько помогает найти более оптимальные решения) и пофиксили очень много мелких ошибок.
А еще мы собираем бонусы. И сами бонусы, и решения с бонусами. Но сабмиттить их пока рано.
С бонусами выходит вот какая история. Допустим, мы решили задачу 1, получили там бонус, с помощью этого бонуса идеально решили задачку 4 и залили это решение. Что произойдет, если мы зальем новое решение задачи 1, которое не берет бонус?
А ничего хорошего не будет, отменится наше идеальное решение задачи 4. А если задача 4 брала бонус, на котором завязано решение задачи 5…
Короче, бонусы производят цепочку зависящих друг от друга решений. А значит, заливать использующие бонусы решения нужно массово — предварительно посчитав, что именно такая последовательность бонусов даст нам наилучший результат. И теперь мы планируем искать наиболее оптимальные решения и их комбинации — пока что не заливая их на сервер, только запоминая в базе. А вот завтра…
А что будет завтра — интрига даже для нас.
Так, тут одно ребро неправильное осталось.
- Может выпилим...?
- Ся.
Девятнадцать часов до конца контеста, мы полны сил и оптимизма, как видите. А я пришел к вам с историей о силе, усердии, плодах долгой работы и злой птичке из 93-ей задачи, которая чхать хотела на все вышеперечисленное.
Итак, дыра в виде птички, фигура в виде краба, девяносто третья задача и гарантированно существующее решение на ноль дизлайков. Это значит, что получившаяся фигура должна идеально вписаться в дырку, разместив на каждой вершине дыры по одной вершине фигуры. Это… непросто.
Во всяком случае, алгоритм с этой задачей не особо справился и от решения на ноль баллов был бесконечно далек. Для таких случаев у нас есть ручной решатель, где мы можем ручками помогать алгоритму. Подвигали вершины, запустили решатель, снова подвигали, снова запустили, снова подвигали.
Этим и занялся один из членов нашей команды, Дима — часов так семь назад. До этого он уже справился с несколькими такими задачами и был полон оптимизма. Задача выглядела грандиозно и обещала много баллов. Но…
⁃ «Как-то туго идет. А давайте запилим отображение оригинальной длины ребра?»
Через час стало понятно, что задача идет как-то медленно и хорошо бы немного подтюнить визуализатор. Подтюнили, визуализатор теперь умел отображать не только текущую длину ребра, но и ожидаемую. Новую функцию для визуализатора скидывали в телеге, потому что, ну… Ой, как будто вы никогда не перекидывали код в мессенджерах.
Обновление на лету прошло успешно, но глобально ситуацию не исправило. Поэтому ребята по ходу дела написали еще несколько улучшений для визуализатора. И вот после этого…
И после этого мучения продолжались. Дима все больше мрачнел, визуализатор все больше тормозил, но задача все же двигалась к решению. Часа так через четыре осталось всего несколько неправильно установленных вершин и загадочные 3 дизлайка, непонятно откуда берущиеся. Автоматическая решалка не справлялась, Дима не справлялся, а еще через несколько минут не справился ноутбук и намертво завис.
Всем резко стало грустно. На решение потрачена куча времени, сохранить его не выходит, все зависло, а время работы над задачей потихоньку подкатывало к пяти часам. Придумывались разнообразные варианты спасения ситуации, перезапуска всего на свете, какого-то сохранения решения. Был сделан отчаянный скриншот, по которому можно было попробовать восстановить решение — но это заняло бы кучу времени, а на чертову птицу уже и смотреть не хотелось. Впрочем, пока все эти варианты придумывались, ноутбук таки отвис.
И вот решение отвисло, но алгоритмический двигатель был больше недоступен, ноутбук бы точно завис. И началось долгое-долгое двигание вершин. Три дизлайка в какой-то момент превратились в четыре («нам что, уже сервер дизлайк поставил?»), а последние ребра никак не желали встать так, чтобы удовлетворять требования по максимальному растяжению.
Закончилось все благополучно и через полчаса перебора Дима таки добил задачу, убив на нее больше пяти часов. Ноль дизлайков, оптимальное решение, но чертова птица теперь навечно будет символом боли и страданий.
- Может выпилим...?
- Ся.
Девятнадцать часов до конца контеста, мы полны сил и оптимизма, как видите. А я пришел к вам с историей о силе, усердии, плодах долгой работы и злой птичке из 93-ей задачи, которая чхать хотела на все вышеперечисленное.
Итак, дыра в виде птички, фигура в виде краба, девяносто третья задача и гарантированно существующее решение на ноль дизлайков. Это значит, что получившаяся фигура должна идеально вписаться в дырку, разместив на каждой вершине дыры по одной вершине фигуры. Это… непросто.
Во всяком случае, алгоритм с этой задачей не особо справился и от решения на ноль баллов был бесконечно далек. Для таких случаев у нас есть ручной решатель, где мы можем ручками помогать алгоритму. Подвигали вершины, запустили решатель, снова подвигали, снова запустили, снова подвигали.
Этим и занялся один из членов нашей команды, Дима — часов так семь назад. До этого он уже справился с несколькими такими задачами и был полон оптимизма. Задача выглядела грандиозно и обещала много баллов. Но…
⁃ «Как-то туго идет. А давайте запилим отображение оригинальной длины ребра?»
Через час стало понятно, что задача идет как-то медленно и хорошо бы немного подтюнить визуализатор. Подтюнили, визуализатор теперь умел отображать не только текущую длину ребра, но и ожидаемую. Новую функцию для визуализатора скидывали в телеге, потому что, ну… Ой, как будто вы никогда не перекидывали код в мессенджерах.
Обновление на лету прошло успешно, но глобально ситуацию не исправило. Поэтому ребята по ходу дела написали еще несколько улучшений для визуализатора. И вот после этого…
И после этого мучения продолжались. Дима все больше мрачнел, визуализатор все больше тормозил, но задача все же двигалась к решению. Часа так через четыре осталось всего несколько неправильно установленных вершин и загадочные 3 дизлайка, непонятно откуда берущиеся. Автоматическая решалка не справлялась, Дима не справлялся, а еще через несколько минут не справился ноутбук и намертво завис.
Всем резко стало грустно. На решение потрачена куча времени, сохранить его не выходит, все зависло, а время работы над задачей потихоньку подкатывало к пяти часам. Придумывались разнообразные варианты спасения ситуации, перезапуска всего на свете, какого-то сохранения решения. Был сделан отчаянный скриншот, по которому можно было попробовать восстановить решение — но это заняло бы кучу времени, а на чертову птицу уже и смотреть не хотелось. Впрочем, пока все эти варианты придумывались, ноутбук таки отвис.
И вот решение отвисло, но алгоритмический двигатель был больше недоступен, ноутбук бы точно завис. И началось долгое-долгое двигание вершин. Три дизлайка в какой-то момент превратились в четыре («нам что, уже сервер дизлайк поставил?»), а последние ребра никак не желали встать так, чтобы удовлетворять требования по максимальному растяжению.
Закончилось все благополучно и через полчаса перебора Дима таки добил задачу, убив на нее больше пяти часов. Ноль дизлайков, оптимальное решение, но чертова птица теперь навечно будет символом боли и страданий.
А вот главные герои истории в процессе решения и тот самый скриншот, по которому предполагалось восстанавливать результат.
Заодно и решалку нашу покажу.
Заодно и решалку нашу покажу.
До конца контеста два часа и самое время показать вам Дашборд.
Вот прям с большой буквы, Дашборд. Вы только посмотрите на него. Аккуратные колонки, прогрессбар, куча полезной информации (в том числе переданной цветами!) и логотип Pegovka Solutions в углу! Сейчас объясню, что нам этот дашборд может рассказать. А заодно и ситуацию с бонусами проясню.
Вот прям с большой буквы, Дашборд. Вы только посмотрите на него. Аккуратные колонки, прогрессбар, куча полезной информации (в том числе переданной цветами!) и логотип Pegovka Solutions в углу! Сейчас объясню, что нам этот дашборд может рассказать. А заодно и ситуацию с бонусами проясню.
Итак, на дашборде у нас семь колонок:
- Номер задачи
- Лучшее решение по миру
- Лучшее решение наше (без бонусов)
- И колонки под решения с каждым из бонусов (GLOBALIST, WALLHACK, SUPERFLEX и BREAK_A_LEG)
Дальше — цвета. Красная цифра в колонке BEST означает, что наше решение хуже. Зеленая — что у нас есть лучшее решение. А желтая цифра это «у нас есть лучшее решение, но только при использовании бонуса». В следующих колонках мы выделяем желтым лучшее решение с бонусом. Если решения с бонусами хуже текущего — они останутся серыми.
Что мы можем сказать, позалипав в табличку? Кажется, в основном то, что наши решения с бонусами не слишком-то эффективны. В большинстве случаев они дают совсем небольшую выгоду, которая едва ли окупит затраты на взятие этих бонусов.
В теории, это решается цепочками взятия бонусов. Ну то есть в первой задаче ты пожертвовал каким-то количеством баллов и взял бонус в седьмой, там, за счет взятого бонуса, ты легко берешь следующий бонус и не теряешь баллов, в следующей тоже берешь бонус и даже выходишь в плюс по баллам и так далее.
Основная проблема в том, что мы так не умеем. С учетом наличия в каждой задаче аж трех бонусов для взятия и примерно трех же потенциальных вариантов решения (с бонусом 1, с бонусом 2, без бонуса вовсе) множество потенциальных решений получается неприлично огромным. А в наших решениях и так полно перебора, так что выйти на такой уровень вариативности мы попросту не способны.
Так что, кажется, воспользоваться максимальным потенциалом бонусов нам не суждено (хотя кое-где они наверняка принесут нам дополнительные баллы). А пока мы продолжаем судорожно доделывать последний алгоритм, который может несколько помочь нам под конец контеста. Но о нем уже вечером, когда ребята выдохнут и смогут мне про него детально рассказать.
- Номер задачи
- Лучшее решение по миру
- Лучшее решение наше (без бонусов)
- И колонки под решения с каждым из бонусов (GLOBALIST, WALLHACK, SUPERFLEX и BREAK_A_LEG)
Дальше — цвета. Красная цифра в колонке BEST означает, что наше решение хуже. Зеленая — что у нас есть лучшее решение. А желтая цифра это «у нас есть лучшее решение, но только при использовании бонуса». В следующих колонках мы выделяем желтым лучшее решение с бонусом. Если решения с бонусами хуже текущего — они останутся серыми.
Что мы можем сказать, позалипав в табличку? Кажется, в основном то, что наши решения с бонусами не слишком-то эффективны. В большинстве случаев они дают совсем небольшую выгоду, которая едва ли окупит затраты на взятие этих бонусов.
В теории, это решается цепочками взятия бонусов. Ну то есть в первой задаче ты пожертвовал каким-то количеством баллов и взял бонус в седьмой, там, за счет взятого бонуса, ты легко берешь следующий бонус и не теряешь баллов, в следующей тоже берешь бонус и даже выходишь в плюс по баллам и так далее.
Основная проблема в том, что мы так не умеем. С учетом наличия в каждой задаче аж трех бонусов для взятия и примерно трех же потенциальных вариантов решения (с бонусом 1, с бонусом 2, без бонуса вовсе) множество потенциальных решений получается неприлично огромным. А в наших решениях и так полно перебора, так что выйти на такой уровень вариативности мы попросту не способны.
Так что, кажется, воспользоваться максимальным потенциалом бонусов нам не суждено (хотя кое-где они наверняка принесут нам дополнительные баллы). А пока мы продолжаем судорожно доделывать последний алгоритм, который может несколько помочь нам под конец контеста. Но о нем уже вечером, когда ребята выдохнут и смогут мне про него детально рассказать.
22 июля мы проведём Техноквиз — онлайн-игру на околоайтишные темы в стиле известных барных викторин.
Кто может участвовать?
Дизайнеры, аналитики, тестировщики, менеджеры и, конечно, разработчики.
Какие будут вопросы?
Квиз сделан айтишниками для айтишников. Не заточен на глубокое знание хардкорных тем. Все сделано по фану, будут вопросы не только про языки и разработку, но много на эрудицию и кругозор. Будут интересные факты из мира IT, про интернет, мемчики и все такое.
Как регистрироваться?
Соберите команду из 3-10 человек, придумайте название и выберите капитана. Капитан должен зарегистрировать команду до 10:00 (Мск), 22 июля. Регистрироваться остальным членам команды не нужно.
Где играем?
Трансляция будет на YouTube-канале Технологии в Контуре.
А если победим?
Командам, набравшим больше всех баллов, мы подарим сертификаты на Озон.
Читайте правила, собирайте команду и скорее регистрируйтесь 🚀
Кто может участвовать?
Дизайнеры, аналитики, тестировщики, менеджеры и, конечно, разработчики.
Какие будут вопросы?
Квиз сделан айтишниками для айтишников. Не заточен на глубокое знание хардкорных тем. Все сделано по фану, будут вопросы не только про языки и разработку, но много на эрудицию и кругозор. Будут интересные факты из мира IT, про интернет, мемчики и все такое.
Как регистрироваться?
Соберите команду из 3-10 человек, придумайте название и выберите капитана. Капитан должен зарегистрировать команду до 10:00 (Мск), 22 июля. Регистрироваться остальным членам команды не нужно.
Где играем?
Трансляция будет на YouTube-канале Технологии в Контуре.
А если победим?
Командам, набравшим больше всех баллов, мы подарим сертификаты на Озон.
Читайте правила, собирайте команду и скорее регистрируйтесь 🚀
Продолжаем рассказывать про машинное обучение на Хабре!
У нас в Контуре десятки классных датасайентистов, которые решают самые разные задачи: ищут поддерки паспортов, предсказывают вероятность банкротства компаний, распознают документы, пишут чат-ботов, классифицируют товары… в общем, недостатка идей ML-фичей у нас точно нет :)
В статье Андрей Кулагин разбирается, что делать команде, которая тонет в потоке гипотез: как сразу распознать плохую идею, как убедиться, что в задаче есть ML, на каком этапе выбирать бизнес-метрики и как их связывать с метриками DS?
Скорее читайте на Хабрахабре 🤘
У нас в Контуре десятки классных датасайентистов, которые решают самые разные задачи: ищут поддерки паспортов, предсказывают вероятность банкротства компаний, распознают документы, пишут чат-ботов, классифицируют товары… в общем, недостатка идей ML-фичей у нас точно нет :)
В статье Андрей Кулагин разбирается, что делать команде, которая тонет в потоке гипотез: как сразу распознать плохую идею, как убедиться, что в задаче есть ML, на каком этапе выбирать бизнес-метрики и как их связывать с метриками DS?
Скорее читайте на Хабрахабре 🤘