Оказывается Хабр доброжелательно предоставляет возможность завести бесплатный «корпоративный» блог для опенсорсного проекта. Какое‑то время назад я подал заявку — и недавно обнаружил что она была удовлетворена. Начинать программисты любят с «тестового» поста, но т.к. речь идёт о публичном пространстве, пусть он будет хоть немного содержательным:)
На сайт CodeAbbey сегодня добавилась задачка про поиск Белого Прямоугольника. Речь идёт о матрице в которой есть чёрные и белые клетки — расставленные достаточно хаотично — и хочется найти прямоугольник без чёрных клеток максимальной площади (со сторонами параллельными сторонам матрицы, конечно).
Про сам сайт мы ещё расскажем в отдельно (иначе зачем блог было заводить) — а сейчас всё же про саму задачку.
Она, по‑видимому, древняя как мир. Я на неё наткнулся где‑то в конце книжки Ж.Арсака «Программирование Игр и Головоломок» — причём он упоминает что сам встретил её на какой‑то олимпиадке за несколько лет до того. А книжка‑то 1985 года.
Интересно что при очень простом описании самый банальный алгоритм который приходит в голову имеет сложность O(N^6) где N — сторона матрицы. Конечно нынешние компьютеры уже не те что в 80х годах, но если вы заимплементите такой «брутефорс» — то даже на скромных размерах тестовых данных которые предлагает сайт, работать он у вас будет сколько‑то секунд... Заметно не мгновенно.
Гораздо более сносный алгоритм O(N^3) можно реализовать достаточно несложно (именно он срабатывает при загрузке страницы и генерации данных на сайте).
Возможно оптимальный алгоритм за O(N^2) уже требует немножко поднапрячь мозги — но впрочем его не очень сложно нагуглить (сложнее понять).
Комментарии (9)
Alexandroppolus
25.12.2024 12:58Это классика литкода, задача 85. Решал когда-то. Объяснить решение O(n^2) проще всего, предварительно объяснив предыдущую задачу 84, оно в 85 используется как вспомогательная функция прямо без изменений.
SadOcean
25.12.2024 12:58Помню как на олимпиаде написал тупейшее решение с 4-мя вложенными циклами и прекрасно покатило.
С тех пор есть наглядный пример про ненужность предварительной оптимизации.
RodionGork Автор
25.12.2024 12:58ну здесь ограничений по времени нет, по крайней мере в этой задаче - мы демократично позволяем пользователям иногда посидеть часик-другой пока их решение считает - и подумать за это время, может что-то можно было сделать иначе :)
так и здесь - писать более или менее эффективное решение - это на выбор стреляющего. кому-то нравится по нескольку раз возвращаться к задаче и пытаться сделать быстрее, короче, изящнее. кто-то наоборот хочет просто побольше нарешать.
для оптимизации бывают специальные задачки в духе челленджей
RumataEstora
25.12.2024 12:58найти прямоугольник без чёрных клеток максимальной площади
на сайте по ссылке под фразой "Answer should be a single value -
sizeof the largest rectangle". Наверно подразумевается "Answer should be a single value -areaof the largest rectangle"?
Anarchist
25.12.2024 12:58На первый взгляд линейная по памяти и времени от количества клеток. Нет?
RodionGork Автор
25.12.2024 12:58ну такое. если знать как сделать - то от количества клеток линейно а памяти меньше (достаточно на один столбец). вся суть в том чтобы догадаться до этого решения (это мягко говоря нетривиально). поэтому трудно что-то прокомментировать не зная что там за "первый взгляд" :)
tm555
Спасибо, что поделились