Пришло время создать немного инфраструктуры.
Организаторы контеста предлагают нам решить несколько десятков задач. За время контеста мы обязательно напишем несколько десятков алгоритмов их решения. Однозначно выбрать лучший алгоритм обычно нельзя: для разных задач лучше подходят разные.
Это значит, что нам нужно попробовать решить каждую задачу каждым алгоритмом. Когда задач и алгоритмов станет много, получатся тысячи или даже десятки тысяч комбинаций.
Стандартная инфраструктура, которую мы делаем для подобных контестов, выглядит так:
1. Мы запускаем на небольшом вычислительном кластере несколько решателей. Эти решатели делят весь объем задач между собой. Например, первый решатель берет задачи с 1 по 10 и решает их алгоритмами А, B и C. Второй решатель берет задачи с 11 по 20 и так далее. Готовые решения сохраняются в базу.
2. Отдельный сервис время от времени забирает из базы лучшее решение для каждой задачи и отправляет на сервер организаторов через API. Таким образом мы убеждаемся, что мы всегда сдаем лучший набор решений, даже если алгоритмы были написаны разными членами команды в разные дни.
В этот раз мы впервые работаем на Яндекс.Облаке, а в качестве базы данных используем YDB. Контест — хороший шанс попробовать новую технологию в безопасных условиях :)
Организаторы контеста предлагают нам решить несколько десятков задач. За время контеста мы обязательно напишем несколько десятков алгоритмов их решения. Однозначно выбрать лучший алгоритм обычно нельзя: для разных задач лучше подходят разные.
Это значит, что нам нужно попробовать решить каждую задачу каждым алгоритмом. Когда задач и алгоритмов станет много, получатся тысячи или даже десятки тысяч комбинаций.
Стандартная инфраструктура, которую мы делаем для подобных контестов, выглядит так:
1. Мы запускаем на небольшом вычислительном кластере несколько решателей. Эти решатели делят весь объем задач между собой. Например, первый решатель берет задачи с 1 по 10 и решает их алгоритмами А, B и C. Второй решатель берет задачи с 11 по 20 и так далее. Готовые решения сохраняются в базу.
2. Отдельный сервис время от времени забирает из базы лучшее решение для каждой задачи и отправляет на сервер организаторов через API. Таким образом мы убеждаемся, что мы всегда сдаем лучший набор решений, даже если алгоритмы были написаны разными членами команды в разные дни.
В этот раз мы впервые работаем на Яндекс.Облаке, а в качестве базы данных используем YDB. Контест — хороший шанс попробовать новую технологию в безопасных условиях :)
🔥12👍4
Иногда лучшее решение задачи можно найти вручную. Но не на бумажке, конечно. Тут ключевую роль играет интерактивный визуальный инструмент, в котором сложную концептуальную часть работы делает человек, а довести решение до оптимального в мелочах помогает алгоритм.
Часто в контестах ICFPC хороший результат показывают команды, которые могут сделать хороший современный фронтенд для визуализации и ручного решения. На чистых алгоритмах обычно не выехать.
Часто в контестах ICFPC хороший результат показывают команды, которые могут сделать хороший современный фронтенд для визуализации и ручного решения. На чистых алгоритмах обычно не выехать.
Привет!
Мы возвращаемся в эфир. Прошло 19 часов контеста. Через 4,5 часов будет так называемый Lightning — отсечка первого дня, в которой можно тоже победить. Мы пока на 8 месте. Ночью были даже на третьем! Так что мы не отчаиваемся.
А теперь давайте посмотрим, что у нас есть сейчас.
Мы возвращаемся в эфир. Прошло 19 часов контеста. Через 4,5 часов будет так называемый Lightning — отсечка первого дня, в которой можно тоже победить. Мы пока на 8 месте. Ночью были даже на третьем! Так что мы не отчаиваемся.
А теперь давайте посмотрим, что у нас есть сейчас.
🔥11
За ночь нам насыпали еще 10 картинок. Они стали сложнее и Мона Лиза наконец-то вернулась к истокам. А по картинам Ван Гога и Климта понятно, что организаторы любят причинять боль.
😁6👍2
У нас есть 2 алгоритма, один мануальный и “улучшатель”. Лучше всех, конечно, справляется мануальный — ребята просто вручную нарезают каждую картинку и раскрашивают ее. Но пока нарезаны не все картинки.
Вот такая статистика. Под цифрами: 1. Алгоритм Гриди, 2. Симпл алгоритм, 3. Мануальный
Рядом с каждым вы можете еще видеть результаты, после того как к алгоритмам применили “улучшатель”. Он работает примерно так: алгоритм что-то нарезал/нарисовал, улучшатель двигает на пиксель в какую-то сторону и проверяет стало ли лучше. Если стало лучше — двигает дальше, если нет, говорит, что “пока это лучший вариант”.
Вот такая статистика. Под цифрами: 1. Алгоритм Гриди, 2. Симпл алгоритм, 3. Мануальный
Рядом с каждым вы можете еще видеть результаты, после того как к алгоритмам применили “улучшатель”. Он работает примерно так: алгоритм что-то нарезал/нарисовал, улучшатель двигает на пиксель в какую-то сторону и проверяет стало ли лучше. Если стало лучше — двигает дальше, если нет, говорит, что “пока это лучший вариант”.
👍2🤔1
Ну и немного о том, где ребята ищут идеи.
Ваня Дашкевич: «Я пока спал придумал все про правильный быстрый выбор цветов в готовом решении.»
Ваня Дашкевич: «Я пока спал придумал все про правильный быстрый выбор цветов в готовом решении.»
🔥9😁6
Осталось совсем немного времени, а у нас проблемка.
Если разрезал блок вертикальной линией (лайн кат) потом соединил части (мерж), а потом пытаешься сделать точечный разрез (поинт кат) — это дает ошибку: «Нельзя делать блоки нулевого размера.» Но дело в том, что они и не возникают! При этом если ты сделал лайн кат, потом мерж и снова лайн кат, то всё ок.
Из-за этого у нас не проходит множество хороших решений. Сабмитилка их просто не пропускает.
Ребята негодуют.
(посмотреть методы, которые используются для решения, можно в спецификации)
Если разрезал блок вертикальной линией (лайн кат) потом соединил части (мерж), а потом пытаешься сделать точечный разрез (поинт кат) — это дает ошибку: «Нельзя делать блоки нулевого размера.» Но дело в том, что они и не возникают! При этом если ты сделал лайн кат, потом мерж и снова лайн кат, то всё ок.
Из-за этого у нас не проходит множество хороших решений. Сабмитилка их просто не пропускает.
Ребята негодуют.
(посмотреть методы, которые используются для решения, можно в спецификации)
Lightning (первые 24 часа) — закончился. Хотели бы вам рассказать на каком мы месте, но не все так просто. Scoreboard заморозили за 2 часа до и разморозят только через 4. При этом последние сабмиты на участие в Lightning они приняли в 17:02.
Когда все разморозится картина будет совершенно другая и мы не сможем понять попали мы в 10 или нет. Нам вообще скажут об этом скорее всего во второй половине сентября.
За два часа до у нас был результат как на скриншоте (14 место из 131). Последний раз мы засабмитили что-то около 666 тыс. Если предположить, что в сетку никто новый не врывался, то, возможно, мы окажемся на 9 месте или около того.
Что дальше? А дальше мы ждем новую спецификацию🤷♀️
Когда все разморозится картина будет совершенно другая и мы не сможем понять попали мы в 10 или нет. Нам вообще скажут об этом скорее всего во второй половине сентября.
За два часа до у нас был результат как на скриншоте (14 место из 131). Последний раз мы засабмитили что-то около 666 тыс. Если предположить, что в сетку никто новый не врывался, то, возможно, мы окажемся на 9 месте или около того.
Что дальше? А дальше мы ждем новую спецификацию🤷♀️
👍16