Как указано в комментариях, мы не можем знать, может ли решение O (n ^ 2 log n) пройти, если мы не знаем, какое оборудование использует онлайн-судья.Возможно, что решение O (n ^ 2 log n) должно быть в состоянии пройти, но вы написали его таким образом, что постоянный фактор слишком велик, например, путем неправильной итерации по матрице (что приводит кпостоянные пропуски кеша).Таким образом, в этом случае необходимо будет увидеть ваш код для диагностики любых ошибок производительности.Но, возможно, судья находится на какой-то старой машине, где O (n ^ 2 log n) не должен проходить.В этом случае вы можете попробовать решение O (n ^ 2).Я опишу один ниже.
Для каждого квадрата (i, j) в сетке N by N мы вычислим наибольшее значение M[i][j], так что квадрат с длиной стороны M[i][j] будет иметь нижнюю правуюугол в (i, j) имеет не более K единиц.Также мы будем хранить количество единиц в этом квадрате - назовите его O[i][j].Тогда ответом на весь экземпляр проблемы является максимальное значение M[i][j] для всех (i, j).
Чтобы вычислить эти значения M[i][j] и O[i][j], мы используем следующий алгоритм:
// precompute row and column partial sums
int bestM = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == 0 || j == 0) {
// this case is trivial
} else {
// use the values of M[i-1][j-1] and O[i-1][j-1] to compute M[i][j] and O[i][j]
}
bestM = std::max(bestM, M[i][j]);
}
}
return bestM;
Чтобы вычислить M[i][j] и O[i][j] из M[i-1][j-1] и O[i-1][j-1], мы поступим следующим образом: мы знаем, что M[i][j] не больше M[i-1][j-1] + 1 (потому что квадрат длины стороны M[i-1][j-1] + 2 с правым нижним углом в (i, j) будет строго содержать квадрат длины стороны M[i-1][j-1] + 1 с правым нижним углом в (i-1, j-1), но этот квадрат, как известно, слишком большой).Итак, у нас есть внутренний цикл:
int o = /* number of ones in square of side length M[i-1][j-1] + 1 with lower right corner at (i, j) */;
for (int k = M[i-1][j-1] + 1; k >= 0; k--) {
if (o <= K) {
O[i][j] = o;
M[i][j] = k;
break;
} else {
// reduce o to be the number of ones in square of side length k-1 with lower right corner at (i, j)
}
}
Чтобы эффективно вычислить o, мы видим, что квадрат длины стороны M[i-1][j-1] + 1 с нижним правым углом в (i, j) является просто несвязным объединением:
- квадрат длины стороны
M[i-1][j-1] с нижним правым углом в (i-1, j-1) и - L-образной формы, состоящей из нижней и правойребра квадрата с вершиной в (i, j)
Таким образом, начальное значение o является просто суммой числа единиц в области 1, а именно O[i-1][j-1], ичисло единиц в области 2. Мы можем получить последние в постоянное время, если у нас есть предварительно вычисленные частичные суммы вдоль каждой строки и каждого столбца, как указано в первом блоке псевдокода.Точно так же каждый раз, когда o нужно уменьшить во внутреннем цикле, нам просто нужно вычесть количество единиц, найденных в L-форме, которая является верхним и левым краями квадрата длины стороны k, которое мыможно также использовать частичные суммы.
Общее время выполнения равно O (N ^ 2), несмотря на 3 вложенных цикла, поскольку левый верхний угол вычисляемого в данный момент квадрата никогда не перемещается назад, и поэтомуобщее время, затрачиваемое во внутреннем цикле вдоль каждой диагонали квадрата, является линейным по размеру этой диагонали, а это означает, что общее время бега является линейным по общему количеству квадратов.