Redaksiya

Group 1: it is guaranteed that the answer is at most $2$.

In this group, we can just iterate through all the cells as if they were the top-left corners of the square with some rune, and check $5\cdot 4=20$ cells for being blue to determine whether there is a rune of size $2$ there and check $1\cdot 4=4$ cells to see whether there is a rune of size $1$.

Time complexity: $O(n^2)$

Memory complexity: $O(n^2)$

Group 2: $n\le 70$.

The solution for this group is the same as for the first one, but here we need to iterate through all the $k$'s (not just $1$ and $2$). And here we need to think a bit about optimizations, so that the constant factor in time complexity becomes small enough to let the solution pass. For example, we can:

• iterate through $k$'s in decreasing order so that we can break right after we find some rune of the size we are checking;

• don't start checking some $k$ if the needed rune does not fit the rest of the pattern (if the number of cells left before the bottom-right corner from the cell we are checking is less than $3\cdot (2\cdot k-1)$);

• immediately exit checking some square for having rune if we find a yellow cell that should be blue;

and so on.

Time complexity: $O(n^2\cdot n\cdot n^2)=O(n^5)$.

Memory complexity: $O(n^2)$

Group 3: $n\le 300$.

Spoiler: when optimized enough, this solution passes all the groups (and solves the problem).

This group can be solved using the same idea as the previous one uses, but with one addition. Note that, if we check some pattern of the rune for being valid, all the cells that need to be blue have the same parity of the sum $(row\_index+column\_index)$. That means that we can do prefix sums over cells with even and odd sums of coordinates and check all the patterns that should be in rune (and, thus, the whole squares) in $O(1)$ time complexity, instead of $O(n^2)$.

To initialize the prefix sums over both parities, we can create two tables of regular prefix sums, but "ignore" the cells of not needed coordinates (setting their value as $0$, no matter which color they are). The code of the queries remains the same as for the regular prefix sums.

Time complexity: $O(n^3)$

Memory complexity: $O(n^2)$

Group 4: $n\le 1,000$.

This group was added to let the optimized solutions from the previous groups or not optimized enough solutions from the next groups, get more points.

Group 5: $n\le 2,500$.

It follows from this that the maximum size of a chessboard that can be built around some cell as its center is binary-searchable. Let's call this value $d_{ij}$. To check if some size $x$ is reachable ($x\le d_{ij}$), we can make one query to the parity prefix sums that were explained for the $3$-rd group. Then we can apply binary search of this value to every cell and get all the $d_{ij}$'s in $O(n^2\log n)$ time.

Pictures for the proof:

The rune of size $2$.

The rune of size $2$ from the previous picture, but with $d_{ij}$'s of chessboards centers increased by $3$. Now, the rune of size $3$ (marked with green color) can be found here. The same works for other sizes also, since increasing $d_{ij}$ expands the boundaries by three cells in each direction, allowing the chessboards which are larger by $2$ cells to fit (considering the shift by $1$ cell from the center as well)

Considering this observation, we can now iterate through all the cells and update the answer by supposing that the current cell:

• is the center of the chessboard which is one of those that form the rune of maximum size;

• has the minimum $d_{ij}$'s out of four such chessboards;

• is the upper, left, right or the bottom one;

• has $d_{ij}$ larger than the size $ans$ of the rune by $0$, $1$ or $2$.

To check whether these conditions correspond to the valid rune or not, we can either use parity prefix sums or $d_{ij}$'s of the other three centers of the chessboards of the rune. For the second way, we need to find these cells using the size we are checking, the coordinates of the current cell and its relative position among the other three.

Time complexity: $O(n^2\log n)$

Memory complexity: $O(n^2)$

Group 6: no additional constraints.

The full solution uses the same logic as the previous group, but it also uses one additional step to reduce finding the size of the maximum chessboard with the center in some cell from $O(n\log n)$ to $O(n)$.

Let's turn our grid by $45$ degrees and "ignore" the cells with some parity of the sum of coordinates (highlighting some chessboard this way):

Now, if we also turn every cell by $45$ degrees, then it will be more noticeable that the chessboard of size $k$ is formed by cells whose Manhattan distance (the sum of differences between the coordinates) to the center one does not exceed $k-1$:

Thus, if the closest cell to the cell $(i;j)$ that is yellow and has the same parity of the sum of coordinates if $(i_c;j_c)$ — then $d_{ij}=\frac{|i-i_c|+|j-j_c|}{2}+1$. Now, these values can be found using BFS, taking yellow cells (and "imaginary" cells outside the grid to prevent going there) as cells with $d_{ij}=0$.

Full solution (C++):

#include <bits/stdc++.h>

using namespace std;

const pair <int, int> delta[4] {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

const int N = 4007;

int n;
int a[N][N];
int d[N][N];
bool used[N][N];

bool validate(int i, int j) {
    return i >= 0 && j >= 0 && i <= n + 1 && j <= n + 1;
}

// Checking whether the given square has the rune of the given size or not   
bool check(int i, int j, int k, int corner) {
    if (k <= 0) return false;
    int di = corner;
    do {
        if (!validate(i, j)) return false;
        if (d[i][j] < k) return false;
        i += delta[di].first * (2 * k - 1);
        j += delta[di].second * (2 * k - 1);
        di = (di + 1) % 4;
    } while (di != corner);
    return true;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;

    memset(a, 0, sizeof(a));
    memset(d, 0, sizeof(d));
    memset(used, 0, sizeof(used));

    // Reading input and pushing yellow cells to the BFS queue
    queue <pair <int, int>> q;
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            if (i == 0 || j == 0 || i == n + 1 || j == n + 1) {
                q.push({i, j});
                used[i][j] = true;
                continue;
            }
            char c;
            cin >> c;
            if (c == '#') a[i][j] = true;
            else {
                a[i][j] = false;
                q.push({i, j});
                used[i][j] = true;
            }
        }
    }
    
    // Building d[i][j]'s with BFS
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto [di, dj] : delta) {
            int id = i + di, jd = j + dj;
            if (!validate(id, jd)) continue;
            if (used[id][jd]) continue;
            d[id][jd] = d[i][j] + 1;
            used[id][jd] = true;
            q.push({id, jd});
        }
    }
    
    // Calculating the answer
    int ans = 0;
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            for (int add = 2; add >= 0; add--) {
                for (int corner = 0; corner < 4; corner++) {
                    if (ans < d[i][j] + add) {
                        if (check(i, j, d[i][j] + add, corner))
                            ans = max(ans, d[i][j] + add);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

Time complexity: $O(n^2)$

Memory complexity: $O(n^2)$

P.S. We would like to thank Valerii Kovnatskyi a lot for providing us the idea (and the code) of the $O(n^2)$ solution! :)