Largest Square with All-One Diagonals
Autumn Tournament (2020)
Submission name: square.cpp
Problem summary
Find the largest odd side length of an axis-aligned square in a binary grid whose two diagonals contain only 1 s. Cells outside the diagonals are unrestricted. At least one grid cell is 1.
Source clarification. The prose specifies columns then rows, but the displayed 10 8 example contains 10 rows of 8 digits. The implementation reads the first row to determine which of the two dimensions is the width, supporting both published orientations. The four-direction method is confirmed by the official editorial: https://infos.infosbg.com/files/Contests/ETI/2020/C/analyses/square_analysis.docx
Input
Two grid dimensions, then the binary grid as rows of digits without separators.
Output
The maximum odd side length.
Constraints
Both dimensions are strictly between 2 and 3000.
Worked example
Original statement sample.
Input
10 8 10111111 11111111 10111111 11111110 01111110 11111110 11111111 10110111 11111111 11111111
Output
7
Solution analysis
- Every odd-sided square has a central cell. Its two diagonals form four 45-degree arms. If each arm, including the center, has at least r consecutive 1 s, those arms define a square with side 2 r−1.
- For every cell compute the lengths of its up-left and up-right runs in a top-to-bottom pass. Store their minimum in a flat array. In a bottom-to-top pass compute the two downward runs and minimize with the saved value. A 0 always gets run length 0.
- Two rolling rows are enough for each pair of diagonal directions; only the upward minimum must be retained per cell. In the sample there is a center with four arms of length 4, giving side 7. A zero just beyond one of those arms prevents extending that center to a larger square. Even an isolated 1 always contributes side 1.
Why it works
Each directional recurrence counts exactly the consecutive 1 s from the current cell by extending the neighboring diagonal run, or resetting at 0. The minimum of the four counts is therefore the maximum common arm length at that center. Every valid odd square has such a center, so maximizing 2 r−1 over all centers is exact.
Watch out. The interior need not be filled with 1 s. Require both diagonals and an odd side, not an all-one rectangle. Do not confuse an arm length including the center with the full side 2 r−1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int columns;
int rows;
cin>>columns>>rows;
string firstRow;
cin>>firstRow;
// The published example reverses the prose's dimension order.
if(static_cast<int>(firstRow.size())!=columns){
swap(columns,rows);
}
vector<string>grid(rows);
grid[0]=firstRow;
for(int i=1;i<rows;i++){
cin>>grid[i];
}
vector<unsigned short>upward(rows*columns);
vector<int>previousLeft(columns+2,0);
vector<int>previousRight(columns+2,0);
vector<int>currentLeft(columns+2,0);
vector<int>currentRight(columns+2,0);
for(int row=0;row<rows;row++){
for(int column=1;column<=columns;column++){
bool one=grid[row][column-1]=='1';
currentLeft[column]=one?previousLeft[column-1]+1:0;
currentRight[column]=one?previousRight[column+1]+1:0;
upward[row*columns+column-1]=
static_cast<unsigned short>(min(currentLeft[column],currentRight[column]));
}
previousLeft.swap(currentLeft);
previousRight.swap(currentRight);
}
fill(previousLeft.begin(),previousLeft.end(),0);
fill(previousRight.begin(),previousRight.end(),0);
int answer=1;
for(int row=rows-1;row>=0;row--){
for(int column=1;column<=columns;column++){
bool one=grid[row][column-1]=='1';
currentLeft[column]=one?previousLeft[column-1]+1:0;
currentRight[column]=one?previousRight[column+1]+1:0;
int radius=min(currentLeft[column],currentRight[column]);
radius=min(radius,static_cast<int>(upward[row*columns+column-1]));
answer=max(answer,2*radius-1);
}
previousLeft.swap(currentLeft);
previousRight.swap(currentRight);
}
cout<<answer<<'\n';
}