histcat

histcat

HomeArchives

Square

#oi#qbxt15
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The problem involves a matrix of size \( n \times n \) where each cell has a color represented by \( a_{i,j} \leq n \). Given a threshold \( k \), the task is to determine the maximum size of a square that can be formed with each cell as the top-left corner, such that the number of distinct colors within the square does not exceed \( k \). A brute-force approach would be inefficient, so an optimized method is proposed. This involves iterating through each cell and calculating how far a square can expand while keeping track of the number of new colors added. The algorithm uses two arrays, \( gi \) and \( fi \), to manage the expansion of squares and the count of new colors, respectively. The solution iterates through the matrix, expanding squares until the color limit is reached, and outputs the maximum square size for each cell. The provided C++ code implements this logic.

Problem#

You have a matrix of size $n\times n$, where each cell has a color $a_{i,j}\le n$.

You like large squares, but you do not like a variety of colors. Specifically, given a dislike value $k \le n$, you need to calculate the maximum square with each cell as the top-left corner, such that the number of colors inside does not exceed $k$.

You need to output the side length $len$ of the maximum square for each cell.

Note that the square cannot exceed the boundaries.

For all data, it holds that $1\le n\le 500,1\le k \le n,1\le a_{i,j}\le n$.

Solution#

First, consider a brute force enumeration of $n^5$, which is clearly infeasible.

Consider optimization.

Noticing the small range of values, we enumerate each element and calculate g[i][j], which represents how this element A expands to a length of len at the point (i, j) when it is just added to the square.

g[i][j] = min(g[i + 1][j] + 1, g[i][j + 1] + 1, g[i + 1][j + 1] + 1);

Then, let f[i][j][len] represent how many new points are added when the point i, j expands to a length of len.

When calculating g[i][j], we can simply increment f[i][j][g[i][j]]++.

Code#

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int a[N][N];

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return f * x;
}

int n, k;

int g[N][N];// The A-th number will appear in the square with top-left corner (i, j) and side length g[i][j] 
int f[N][N][N];

int main()
{
    freopen("square.in", "r", stdin);
    freopen("square.out", "w", stdout);
	n = read(), k = read();
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			a[i][j] = read();
		}
	}

	for(int A = 1;A <= n;A++)
	{
		for(int i = n;i >= 1;i--)
		{
			for(int j = n;j >= 1;j--)
			{
				g[i][j] = 0x3f3f3f3f;
				if(i + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j] + 1);
				if(j + 1 <= n) g[i][j] = min(g[i][j], g[i][j + 1] + 1);
				if(i + 1 <= n && j + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j + 1] + 1);
				if(a[i][j] == A) g[i][j] = 1;
				if(g[i][j] <= n) f[i][j][g[i][j]]++; 
			}
		}
	}

	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			int len = 1, tot = f[i][j][1];// For i, j as the top-left corner, how many new colors appeared for the first time with side length len 
			while(i + len <= n && j + len <= n && f[i][j][len + 1] + tot <= k) len++, tot += f[i][j][len];
			printf("%d ", len);
		}
		printf("\n");
	}

	return 0;
}
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.