Comments 30
по-моему, проще было бы сделать так:
maxS = 0
for i in range(1,hght):
for j in range(1,wdth):
if vector2D[i][j]:
vector2D[i][j]+=min(vector2D[i-1][j],vector2D[i][j-1],vector2D[i-1][j-1])
maxS=max(maxS,vector2D[i][j])
print(maxS)да и быстрее тоже
А еще было бы полезно добавить, что задача (как и это решение) более широко известно под названием "Largest Square Submatrix of all 1's". В интернете легко ищется множество объяснений алгоритма.
Зашел в комментарии, чтобы написать про это решение. Стоило бы расписать, как оно работает. Тут, фактически, считается динамическое программирование: для каждой клетки мы находим максимальный квадрат, имеющей в ней правый нижний угол. Немного порисовав станет ясно, что для расчета надо взять минимум из трех соседних клеток и прибывить 1. Потому что если в текущей клетке квадрат размера K, то в тех трех - хотя бы K-1, ведь квадраты размера K-1 в квадрат размера K вкладываются.
Работает это все за O(N^2), что быстрее О(N^3) с перфиксными суммами.
Поизучал тему, я знаю что для нотации BigO константы не имеют значения, но всё же происходит 4 действия за итерацию (ну или 5) - 4 чтения из массива, расчёт и одна запись в массив. Получается O(K*N*N) где K=5. Я придумал одно решение, которое, может быть, окажется производительнее тех самых K действий, как в ситуации с черепашками, которые мы когда-то обсуждали, попробую реализовать, если будет неудачно, то просто напишу здесь, если удачное - напишу отдельную статью. Плюс там вычленяются зоны, по которым не придется проходить совсем. Может что-то дельное получится.
Эти константы обычно не счититают, потому что они слабо относятся к реальности и их фиг вообще посчитаешь. Ибо действия занимают разное время. 1 деление по модулю дороже нескольких сложений. Более того, одно и то же действие может занимать разное время. Например int a = b; может быть одним тактом, если компилятор соптимизировал обе переменные до регистра. Или несколько тактов, чтобы прочитать данные из регистра и засунуть в память, или десятки, если надо читать из кеша, или тысячи, если данные b лежат в RAM, или миллионы, если страницу памяти операционка выгрузила в swap на диск (не уверен про конкретные числа, но суть правильная). Плюс, современные процессоры настолько сложны, что даже без этих приколов с кешами, черт поймешь сколько оно работает.
И это обычно и не важно, потому что O(n^2), пусть даже там константа 10, будет все-равно сильно быстрее O(n^3) даже с константой 1 при N хотя бы 100. Потому что вот этот лишний фактор 100 микроптимизациями вы никак не перебъете.
Может быть на мелких тестах ваше решение будет даже быстрее. Например, ту же сортировку вставками за O(n^2) используют для мелких массивов вместо быстрой сортировки за O(n log n). Потому что если у вас N порядка 20, то вот уже разница в константе в константе в 10 раз значима. Но это имеет смысл только если вы пишите библиотеку на все случаи жизни и вам надо комбинировать разные решения в зависимости от размера данных.
Но с точки зрения олимпиадной задачи, как в статье, однозначно лучше использовать алгоритм с меньшей ассимптотикой. Ибо на мелких тестах все решения работают за миллисекунды и укладываются в тайм-лимит. А на больших ассимптотика перебивает любые константы.
потому что O(n^2), пусть даже там константа 10, будет все-равно сильно быстрее O(n^3)
ну моё решение так же O(N*N)
Может быть на мелких тестах ваше решение будет даже быстрее
Ну вот чтобы не было того самого "может быть" мне и интересно изучить этот вопрос
Но с точки зрения олимпиадной задачи, как в статье
Я не принимаю участия в олимпиаде и меня это совсем не интересует, меня интересует альтернативное решение, изучение этого вопроса и как следствие - более быстрое решение. А быстрое оно на мелких данных или на больших - покажет результат. В любом случае меня привлекает сам процесс поиска решения.
А на больших ассимптотика перебивает любые константы.
Ну вот ваше решение O(K*N*N), а моё O(L*N*N), где L<K - это и интересно.
ну моё решение так же O(N*N)
Но тогда непоянтно, зачем вы про BigO высказывались.
Ну вот ваше решение O(K*N*N), а моё O(L*N*N), где L<K - это и интересно.
Это интересно, да.
Но тогда непоянтно, зачем вы про BigO высказывались.
Мне кажется я весьма понятно описал. Чем моё первое объяснение отличается от второго? И там и там речь про K и разницу в скорости решений с асимптотикой O(N*N).
Это интересно, да.
То решение о котором я говорил еще перевариваю как лучше реализовать, но пока раздумывал придумалась оптимизация для решения с применением динамического программирования, та что упомянута в этом треде. В реализации будет попроще, наверное с неё и начну.
делаю (точнее сделал и буду оформлять наверное как пост, на статью может и не потянет, тесты не делал и есть подозрения что прибавки в скорости может и не быть) мод для этого решения.
Код в этом треде использовал как эталон, в результате при изучении разных вариантов массивов нашёл ошибку, в текущем виде эта реализации не увидит данные из первой строки и первого столбца и maxS будет равен нулю даже если должен бы выдаваться результат равный 1. то есть для клеток
11
10ноль сделает невидимыми все единицы.
Дело в том что берётся минимальное значение из трёх соседних ячеек, а значит единицу мы получим только в случае когда все три клетки заняты 1 как на примере выше, если же хоть одно значение будет 0, то maxS не получит 1. А значит в текущем виде реализация детектирует квадрат размером 1 только при одной конфигурации, когда в ячейках (0,0), (1,0) и (0,1) у нас стоят единицы.
Как вариант можно считать Max или сумму значений для этих трёх ячеек и в самом конце, если maxS == 0, то выдавать результат 1 если Max/Sum > 0.
Что-то перечитываю написанное и как-то сумбурно получается. Если будет непонятно то спрашивайте что да как. Если что речь про пустые/полупустые массивы, например для такого массива maxS будет ноль для текущей реализации из начала треда:
10000
00000
00000
00000Хотя считать постоянно сумму нет смысла, так как единицы внутри массива нормально детектируются строкой
maxS=max(maxS,vector2D[i][j])так что после основного кода достаточно поставить условие, если maxS == 0 то пройти по первому столбцу и первой строке в поисках единицы.
квадрат в данной задаче считается от 2Х2, т.е.
1 1
1 0
должно вернуть 0. Только
1 1
1 1
это минимум.
согласен с тем, что возможно не явно прописано в условии, но тем не менее отработка на тренажере показала, что нужно считать так
понял, тогда можно это учесть в моей реализации. посмотрите если интересно мою статью на эту тему.
мне тут дали ссылку на эту задачу на leetcode и там квадрат размером 1 возможен
есть подозрения что прибавки в скорости может и не быть
тесты на таймерах дают прирост в скорости ~5-15%, ну лучше конечно на бенчмарках сделать, как будет время сделаю тесты на разных данных.
более сложный вариант реализации делать не стану, накладные расходы точно будут больше, мне кажется текущий мод вполне себе успешно реализует возможности небольшого тюнинга. До публикации может еще что-то придумается, сейчас два тюна реализованы.
Код-то покажите, пожалуйста. Не очень понял, что вы там поменяли.
код мода пока не покажу и не расскажу, не хочу спойлерить, а вот код исправления для реализации в начале треда:
int maxS = 0;
for (int y = 1; y < Ysize; y++)
{
for (int x = 1; x < Xsize; x++)
{
if (platz[x, y] == 1)
{
platz[x, y] += Math.Min(
Math.Min(
platz[x, y - 1],
platz[x - 1, y]),
platz[x - 1, y - 1]);
maxS = Math.Max(maxS, platz[x, y]);
}
}
}
if (maxS == 0)
{
for (int y = 0; y < Ysize; y++)
{
if (platz[0, y] == 1)
{
maxS = 1;
goto FinLabel2;
}
}
for (int x = 0; x < Xsize; x++)
{
if (platz[x, 0] == 1)
{
maxS = 1;
goto FinLabel2;
}
}
}
FinLabel2:на goto переделывал чтобы обрывать раньше
Решил всё же оформить в виде статьи и сделать тесты с разными данными, вот первый результат в сравнении с DP:
| Method | scale | Mean | Error | StdDev | Ratio | RatioSD | Allocated | Alloc Ratio |
|-------------- |------ |----------------:|--------------:|--------------:|------:|--------:|----------:|------------:|
| Zara6502 | 1 | 19.85 us | 0.210 us | 0.196 us | 1.00 | 0.01 | - | NA |
| petropavelMod | 1 | 94.99 us | 0.585 us | 0.518 us | 4.79 | 0.05 | - | NA |
| | | | | | | | | |
| Zara6502 | 10 | 7,690.34 us | 151.352 us | 155.427 us | 1.00 | 0.03 | 6 B | 1.00 |
| petropavelMod | 10 | 26,028.98 us | 132.892 us | 124.307 us | 3.39 | 0.07 | 4 B | 0.67 |
| | | | | | | | | |
| Zara6502 | 100 | 1,097,519.83 us | 10,810.220 us | 10,111.886 us | 1.00 | 0.01 | 400 B | 1.00 |
| petropavelMod | 100 | 3,357,881.64 us | 18,745.504 us | 16,617.401 us | 3.06 | 0.03 | 400 B | 1.00 |
это для массива
int[100 * scale, 100 * scale];рабочий вариант. Проверил.
Спасибо.
Как-то давно писал алгоритм поиска пути для разноразмерных юнитов, экспериментировал с алгоритмами distance field. Помню, что тогда меня заворожила картинка полученная с использованием манхэттенского расстояния. Обратил внимание, что из нее можно вычленить координаты самого большого прямоугольника, который влезает на карту.
Мне кажется в постановке задачи ошибка - квадрат должен иметь равные стороны, а в условии речь про прямоугольник, судя по описанию размера N*M и отсутствию ремарки что N=M.
Понятно, я просто плохо прочитал условие :)
А квадраты под углом 45 градусов не учитываются? В условии сказано про квадрат, при этом не сказано что его его сторона должна быть целочисленной. Скажем в матрице [[0,1,0], [1, 1, 1], [0, 1, 0]] есть квадрат со стороной sqrt(2).
такого усложняющего условия нет) только 90 градусов.
вот кстати, ровно наоборот. как раз хотел сказать в комментах. Если в задаче явно не сказанно какое-то ограничение, то его нет. кролику не запрещено идти по диагонали. т.е. по умолчанию это надо учитывать. 45 градусов... интересно, могут ли быть другие углы.
если мы поварачиваем даже на 45 - то у нас есть как бы дырка - половина пустой клетки-грядки. считается ли, что квадрат полностью заполнен грядками с морковкой.. может да, может нет. может, нужен такой квадрат, что в нём нет ни одной целой грядки без морковки. а части могут быть. тогда возможны и другие углы.
Для этого условия надо было бы описать как именно считается, что квадрат заполнен морковками полностью. В случае квадрата в матрице - все понятно, он состоит из множетсва грядок и про них ясно, есть там морковка или нет. Если квадрат не параллелен осям координат, то тут возникает много вопросов. Какой формы морковка в грядке? Считаются ли куски пустых грядок? Так что в текущей формулировке ясно, что квадрат параллелен осям.
Кроме того, задача разминочная, так что ясно, что она простая. А как-то повернутые квадраты - это уже сильно более сложная задача.
Нет, не ясно. В задаче нет слов "матрица", "оси", "параллелен".
единственное что спасает и за что можно затецпиться "...сторону квадрата, заполненного морковками полностью".
конечно, на живом интервью это всё проговаривается и уточняется - это норм.
на каких олимпиадах - такие вещи выверяются и условия задаются более точно.
Там есть "клеточному полю N × M клеток". Что эквивалентно "матрица". Оси параллелен там нет, да, но это единственная инерпретация слов "заполненного морковками полностью", которая не порождает кучу вопросов.
Согласен, что стоило бы задачу по формальнее описать. Но, подозреваю, там еще есть пример ввода вывода и все становится понятно по ним.
А вот такое как раз можно решать с помощью distance field с диагональным манхэттеном :)
Префиксные суммы. Решение задачи из тренировок Яндекса по алгоритмам