Оказывается Хабр доброжелательно предоставляет возможность завести бесплатный «корпоративный» блог для опенсорсного проекта. Какое‑то время назад я подал заявку — и недавно обнаружил что она была удовлетворена. Начинать программисты любят с «тестового» поста, но т.к. речь идёт о публичном пространстве, пусть он будет хоть немного содержательным:)
На сайт CodeAbbey сегодня добавилась задачка про поиск Белого Прямоугольника. Речь идёт о матрице в которой есть чёрные и белые клетки — расставленные достаточно хаотично — и хочется найти прямоугольник без чёрных клеток максимальной площади (со сторонами параллельными сторонам матрицы, конечно).
Про сам сайт мы ещё расскажем в отдельно (иначе зачем блог было заводить) — а сейчас всё же про саму задачку.
Она, по‑видимому, древняя как мир. Я на неё наткнулся где‑то в конце книжки Ж.Арсака «Программирование Игр и Головоломок» — причём он упоминает что сам встретил её на какой‑то олимпиадке за несколько лет до того. А книжка‑то 1985 года.
Интересно что при очень простом описании самый банальный алгоритм который приходит в голову имеет сложность O(N^6) где N — сторона матрицы. Конечно нынешние компьютеры уже не те что в 80х годах, но если вы заимплементите такой «брутефорс» — то даже на скромных размерах тестовых данных которые предлагает сайт, работать он у вас будет сколько‑то секунд... Заметно не мгновенно.
Гораздо более сносный алгоритм O(N^3) можно реализовать достаточно несложно (именно он срабатывает при загрузке страницы и генерации данных на сайте).
Возможно оптимальный алгоритм за O(N^2) уже требует немножко поднапрячь мозги — но впрочем его не очень сложно нагуглить (сложнее понять).
Комментарии (11)
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ну такое. если знать как сделать - то от количества клеток линейно а памяти меньше (достаточно на один столбец). вся суть в том чтобы догадаться до этого решения (это мягко говоря нетривиально). поэтому трудно что-то прокомментировать не зная что там за "первый взгляд" :)
VaalKIA
25.12.2024 12:58Сложность измеряется от количества элементов, остальные метрики, могут быть только модификаторами. Выводя сложность от стороны, вы утверждаете что можете сделать за n^2 (цитирую: "N - Сторона матрицы") , где это соотвествует площади, то есть количеству элементов, а значит за 1 проход. Решение - в студию!
RodionGork Автор
25.12.2024 12:58Да, за 1 проход. Нужно идя например по колонкам справа-налево одновременно поддерживать "кэшик" пустых клеток справа и использовать стек для хранения размеров прямоугольников (справа же). Думаю, как и я, вы можете это решение нагуглить :) Правда не скажу что в него легко вчитаться. Чтобы не совсем спойлить - оно на сайте drdobbs опубликовано плюс есть ссылка туда же со стековерфлоу где автор целиком реализацию написал.
В то же время, поскольку как вы справедливо замечаете, сторона матрицы это лишь квадратный корень от общего количества клеток, то решение за N^3 (или за C^3/2 если считать что C - количество клеток) не сильно хуже, но ощутимо проще.
Alexandroppolus
25.12.2024 12:58Как уже говорил, надо сначала решить предыдущую задачу за O(n). Потом здесь поддерживать массив высот h длиной N, изначально с нулями. На очередной i-й строке сначала обновлять h (в цикле по столбцам, h[j] = a[i][j] == "белый" ? h[j] + 1 : 0), и вызывать решение предыдущей задачи для h.
tm555
Спасибо, что поделились