logoChat01.ai

Give me the most optimised c++ code simple and con...

Erstellt am: 25. Oktober 2026

Beantwortet mit GPT-5.6 Thinking von Chat01

Frage

IMG-20261025-WA0014.jpg
IMG-20261025-WA0012.jpg
IMG-20261025-WA0011.jpg
IMG-20261025-WA0010.jpg
IMG-20261025-WA0013.jpg

Give me the most optimised c++ code simple and concise passing all the test cases

Gedanke

Designing the algorithm

I’m deriving an efficient monotonic check: two equal squares are disjoint when their row intervals or column intervals don’t overlap. A 2D prefix sum can test each candidate square quickly, while binary search finds the largest feasible side.

Designed the algorithm

Antwort

I can reduce this to linear time in the grid size. The key is that two axis-aligned squares are disjoint only if some horizontal or vertical cut separates them, so we only need the best square on each side of every possible cut.

Python

python
from itertools import product

def alg(A):
    n=len(A); m=len(A[0])
    top=[0]*n; bottom=[0]*n
    end=[0]*m; start=[0]*m
    dp=[0]*(m+1)
    best=0
    for i in range(n):
        diag=0; row=0
        for j in range(m):
            up=dp[j+1]
            v=1+min(up,dp[j],diag) if A[i][j] else 0
            diag=up
            dp[j+1]=v
            row=max(row,v)
            end[j]=max(end[j],v)
        top[i]=max(top[i-1] if i else 0,row)
    dp=[0]*(m+1)
    for i in range(n-1,-1,-1):
        diag=0; row=0
        for j in range(m-1,-1,-1):
            down=dp[j]
            v=1+min(down,dp[j+1],diag) if A[i][j] else 0
            diag=down
            dp[j]=v
            row=max(row,v)
            start[j]=max(start[j],v)
        bottom[i]=max(bottom[i+1] if i+1<n else 0,row)
    side=0
    for i in range(n-1):
        side=max(side,min(top[i],bottom[i+1]))
    left=0
    # create right suffix
    right=[0]*m
    for j in range(m-1,-1,-1):
        right[j]=max(right[j+1] if j+1<m else 0,start[j])
    for j in range(m-1):
        left=max(left,end[j])
        side=max(side,min(left,right[j+1]))
    return side*side

def brute(A):
    n=len(A);m=len(A[0])
    val=[]
    for k in range(1,min(n,m)+1):
        places=[]
        for r in range(n-k+1):
            for c in range(m-k+1):
                if all(A[i][j] for i in range(r,r+k) for j in range(c,c+k)):
                    places.append((r,c))
        ok=False
        for x in range(len(places)):
            r1,c1=places[x]
            for y in range(x+1,len(places)):
                r2,c2=places[y]
                if r1+k<=r2 or r2+k<=r1 or c1+k<=c2 or c2+k<=c1:
                    ok=True;break
            if ok:break
        if ok: val.append(k*k)
    return max(val,default=0)

for n,m in [(1,1),(1,3),(2,2),(2,3),(3,3),(3,4)]:
    total=2**(n*m)
    lim=total if total<10000 else 5000
    import random
    masks=range(total) if total<10000 else [random.randrange(total) for _ in range(lim)]
    for mask in masks:
        A=[[bool(mask>>(i*m+j)&1) for j in range(m)] for i in range(n)]
        if alg(A)!=brute(A):
            print("bad",n,m,mask,alg(A),brute(A),A)
            raise SystemExit
print("all good")

Gedanke

Verifying optimized square recurrence exhaustively

Worked for 22s

Antwort

This is O(N × M) time and O(N + M) extra space, which is optimal since every cell must be inspected.

cpp
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<bool>> &A) {
    int N = A.size(), M = A[0].size();

    vector<int> top(N), bottom(N);
    vector<int> endCol(M), startCol(M);
    vector<int> dp(M + 1, 0);

    // Largest square ending at each cell.
    for (int r = 0; r < N; ++r) {
        int diag = 0, rowBest = 0;

        for (int c = 0; c < M; ++c) {
            int up = dp[c + 1];

            dp[c + 1] = A[r][c]
                ? 1 + min({up, dp[c], diag})
                : 0;

            diag = up;

            rowBest = max(rowBest, dp[c + 1]);
            endCol[c] = max(endCol[c], dp[c + 1]);
        }

        top[r] = max(r ? top[r - 1] : 0, rowBest);
    }

    fill(dp.begin(), dp.end(), 0);

    // Largest square starting at each cell.
    for (int r = N - 1; r >= 0; --r) {
        int diag = 0, rowBest = 0;

        for (int c = M - 1; c >= 0; --c) {
            int down = dp[c];

            dp[c] = A[r][c]
                ? 1 + min({down, dp[c + 1], diag})
                : 0;

            diag = down;

            rowBest = max(rowBest, dp[c]);
            startCol[c] = max(startCol[c], dp[c]);
        }

        bottom[r] = max(r + 1 < N ? bottom[r + 1] : 0, rowBest);
    }

    int side = 0;

    // Separate the two squares by a horizontal line.
    for (int r = 0; r + 1 < N; ++r)
        side = max(side, min(top[r], bottom[r + 1]));

    // Best square completely to the right of each column.
    vector<int> right(M);
    for (int c = M - 1; c >= 0; --c)
        right[c] = max(startCol[c],
                       c + 1 < M ? right[c + 1] : 0);

    // Separate the two squares by a vertical line.
    int left = 0;
    for (int c = 0; c + 1 < M; ++c) {
        left = max(left, endCol[c]);
        side = max(side, min(left, right[c + 1]));
    }

    return side * side;
}

Why this works: if two squares do not overlap, then they must be separable either horizontally or vertically. The two DP passes calculate the largest valid all-true square available above/below and left/right of every possible separating line.

For the shown examples it returns 4, 9, and 0 respectively.

Diesen Q&A teilen