Comentário Noic OBI 2019 - Fase 2 - Programação Nível 1

Comentário por Willian Wang e Lúcio Cardoso

Para conferir a prova na íntegra, clique aqui.

Nota esquecida

Conhecimento prévio necessário:

Entrada e Saída

Perceba que $A+B = 2*M$ e $B = 2*M - A$ .

Um possível erro é tentar calcular $B$ usando divisão com variáveis inadequadas, como $B=(M+A/2)*2$ sendo $A$ e $M$ inteiros, por isso uma boa prática é sempre evitar a operação de divisão no código.

Complexidade: $O(1)$ .

	// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 1
	// Nota esquecida

	#include <bits/stdc++.h>

	using namespace std;

	int main()
	{
	int a, m;

	cin >> a >> m;

	int b = m*2 - a;

	cout << b << "\n";
	}

view raw nota.cpp hosted with ❤ by GitHub

Ponto do Meio

Conhecimento Prévio Necessário:

Seja $f(x)$ a quantidade de pontos no lado do quadrado no passo $x$ . É possível notar que $f(x) = 2*f(x-1) -1$ e criar uma função recursiva em cima disso.

O método recursivo de calcular a resposta descrito faz parte de uma área mais ampla chamada programação dinâmica.

Complexidade: $O(n)$ .

	// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 1
	// Ponto do Meio

	#include <bits/stdc++.h>

	using namespace std;

	long long f(int x)
	{
	//base da recurssão
	if(x==0) return 2;

	return 2 * f(x-1) - 1;
	}

	int main()
	{
	int n;

	cin >> n;

	long long resposta = f(n);

	//é necessário ainda obter a área do quadrado
	resposta *= resposta;

	cout << resposta << "\n";
	}

view raw ponto.cpp hosted with ❤ by GitHub

Implementar a solução acima deve garantir os 100 pontos do problema, mas quando analisamos mais a fundo a recursão, descobrimos que $f(x) = 2^x + 1$ , e com isso criar uma solução com complexidade logarítmica usando a técnica de exponenciação de matrizes, deixamos claro que essa solução não é necessária para o problema.

Matriz Super-Legal

Conhecimento prévio necessário:

Este mesmo problema estava presente na prova do Nível 2 e, provavelmente, foi um dos problemas mais interessantes dessa fase da OBI.

O seguinte lema é essencial na solução do problema:

Lema: Uma matriz é super-legal se, e somente se, todas as suas submatrizes $2$ x $2$ são legais.

Prova

Note que, pelo enunciado do problema, todas as submatrizes $2$ x $2$ de uma matriz super-legal devem ser legais. Queremos, então, provar que a condição é suficiente.

Fato 1: Toda matriz $2$ x $M$ ( $M \geq 2$ ) que possui todas as suas submatrizes $2$ x $2$ legais é super-legal.

Prova do Fato 1:

Vamos supor, por indução, que o fato vale para qualquer matriz $2$ x $K$ , onde $2 \leq K < M$ . Se provarmos que a matriz $2$ x $M$ é legal, podemos concluir, como um resultado da hipótese de indução, que ela é super-legal.

Note que o caso base é o caso trivial consistindo apenas de uma matriz $2$ x $2$ . Temos que:

1. $A(1, 1) + A(2, 2) \leq A(1, 2) + A(2, 1)$ , pois a matriz de cantos $(1,1)$ e $(2, 2)$ é legal.

2. $A(1, 2) + A(2, M) \leq A(1, M) + A(2, 2)$ , pois, por hipótese de indução, a matriz de cantos $(1, 2)$ e $(2, M)$ é legal.

Somando as desigualdades, temos que:

$A(1, 1) + A(2, 2) + A(1, 2) + A(2, M) \leq A(1, 2) + A(2, 1) + A(1, M) + A(2, 2)$

$\implies A(1, 1) + A(2, M) \leq A(1, M) + A(2, 1)$ .

Ou seja, a matriz $2$ x $M$ é legal. Assim, o Fato 1 está provado por indução.

Fato 2: Toda matriz $N$ x $2$ ( $N \geq 2$ ) que possui todas as suas submatrizes $2$ x $2$ legais é super-legal.

Prova do Fato 2: Análoga à prova do Fato 1.

Agora, vamos supor, novamente por indução, que uma matriz $P$ x $Q$ ( $2 \leq P < N, 2 \leq Q < M$ ) qualquer é super-legal. Para finalizar a prova, é suficiente provar que a matriz $N$ x $M$ será legal.

Perceba que os casos base da indução são exatamente o Fato 1 e o Fato 2. Temos que:

1. $A(1, 1) + A(N-1, M) \leq A(1, M) + A(N-1, 1)$ , pois pela hipótese de indução, a matriz de cantos $(1, 1)$ e $(N-1, M)$ é legal.

2. $A(N-1, 1) + A(N, M) \leq A(N-1, M) + A(N, 1)$ , pois, pelo Fato 1, a matriz de cantos $(N-1, 1)$ e $(N, M)$ é legal.

Somando as desigualdades, obtemos que:

$A(1, 1) + A(N-1, M) + A(N-1, 1) + A(N, M) \leq A(1, M) + A(N-1, 1) + A(N-1, M)$

$+ A(N, 1) \implies A(1, 1) + A(N, M) \leq A(1, M) + A(N, 1)$ .

Ou seja, a matriz $N$ x $M$ inteira é legal. Assim, a prova está concluída.

[collapse]

Redução do Problema

Utilizando dessa observação, vamos construir uma nova matriz $B$ de dimensões $(N-1)$ x $(M-1)$ , de valores $0$ ou $1$ . Ela será definida da seguinte maneira:

Se a submatriz $2$ x $2$ de $A$ de cantos $(i, j)$ e $(i+1, j+1)$ for legal, então $B(i, j) = 1$ .
Caso contrário, $B(i, j) = 0$ .

Suponha que a maior matriz super-legal de $A$ possui cantos $(a, b)$ e $(c, d)$ ( $a \leq c, b \leq d$ ). Então, teremos que todos os valores na submatriz em $B$ de cantos $(a, b)$ e $(c-1, d-1)$ serão iguais a $1$ . Ou seja, todas as submatrizes $2$ x $2$ em $A$ com canto superior esquerdo indo desde $(a, b)$ até $(c-1, d-1)$ devem ser legais.

Logo, a maior submatriz super-legal em $A$ representa, em $B$ , a submatriz de comprimentos $x$ e $y$ tal que o valor $(x+1) \cdot (y+1)$ é máximo e que todos os seus elementos sejam iguais a $1$ . Resta agora encontrarmos esta matriz em $B$ .

Algoritmo em $O(NM^2)$

Defina $h(i, j)$ como o maior valor $k$ tal que $B(i, j), B(i-1, j), ..., B(i-k+1, j)$ são células de valor $1$ . Ou seja, $h(i, j)$ é a "altura" da célula $B(i, j)$ . Além disso, defina $X_m$ e $Y_m$ como os comprimentos da matriz que desejamos encontrar em $B$ . Perceba que o valor $h$ de cada uma das células na última linha da matriz procurada é maior ou igual a $Y_m$ .

Assim, para encontrar o valor $(X_m+1) \cdot (Y_m+1)$ máximo, ou seja, a área da maior matriz super-legal, podemos realizar o seguinte algoritmo:

Algoritmo 1:

Fixe uma célula $(i, j)$ qualquer da matriz $B$ de tal forma que $B(i, j) = 1$ .
Encontre o índice $j_0$ mais à direita tal que $1 \leq j_0 < j$ e $h(i, j_0) < h(i, j)$ .
Encontre o índice $j_1$ mais à esquerda tal que $j < j_1 \leq M$ e $h(i, j_1) < h(i, j)$ .
Caso $(j_1 - j_0) \cdot (h(i, j) + 1)$ seja maior do que a resposta atual, atualize-a para este valor.
Repita as etapas $1...4$ para as outras células não-nulas de $B$ .

Essencialmente, o algoritmo acima escolhe uma célula e encontra a matriz de maior comprimento $X$ possível tal que seu comprimento $Y$ seja $h(i, j)$ e que a célula $(i, j)$ seja uma das células na base da matriz.

Assim, note que é possível realizar um algoritmo de complexidade $O(NM^2)$ : Podemos encontrar os valores $h(i, j)$ para cada célula em $O(NM)$ (mais detalhes no código abaixo) e realizar o Algoritmo 1 para cada uma das $(N-1)(M-1)$ células, encontrando os valores $j_0$ e $j_1$ em $O(M)$ . Essa solução era suficiente para conseguir $60$ pontos no problema.

Otimização do Algoritmo 1

Para uma solução mais eficiente, vamos encontrar os valores $j_0$ de $j_1$ de maneira rápida. Para isso, iremos utilizar a estrutura de dados stack (pilha) da STL do C++. O algoritmo será o seguinte:

Algoritmo 2:

Inicie na célula $(i, 1)$ da matriz $B$ , onde $i$ é a linha atual (iniciando por $1$ ) e declare uma pilha vazia de pares da forma $(j, h(i, j))$ .
Se a célula atual for $(i, j)$ , remova o par no topo da pilha caso seu segundo elemento tenha valor maior ou igual a $h(i, j)$ .
Repita a etapa $2$ até que a pilha esteja vazia ou até que o valor do segundo elemento do par no seu topo seja menor do que $h(i, j)$ .
O índice $j_0$ será o valor do primeiro elemento do par no topo da pilha (ou será inexistente caso a pilha esteja vazia).
Insira o par $(j, h(i, j))$ na pilha.
Repita as etapas $2...5$ para os elementos restantes na linha atual. Após isso, recomece da etapa $1$ na linha seguinte.

O Algoritmo 2 é extremamente similar àquele usado no Problema da Semana #39 - Avançado. Para melhor entendimento, confira a sua solução.

Para encontrar o valor $j_1$ , o algoritmo será análogo: Basta iterar por cada linha de trás para frente e refazer o mesmo processo. Finalmente, perceba que a complexidade do Algoritmo 2 em cada uma das $N-1$ linhas de $B$ será $O(M)$ , já que cada elemento na linha é inserido/removido da pilha no máximo uma vez.

Complexidade da solução: $O(NM)$ .

	// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 2
	// Matriz Super Legal

	#include <bits/stdc++.h>

	using namespace std;

	typedef pair<int, int> pii;

	const int maxn = 1e3+10;

	int n, m;

	// altura de cada célula
	int h[maxn][maxn];

	// matrizes
	int A[maxn][maxn], B[maxn][maxn];

	int j_0[maxn][maxn], j_1[maxn][maxn];

	void calc_h(void)
	{
	for (int i = 1; i < n; i++)
	{
	for (int j = 1; j < m; j++)
	{
	if (!B[i][j]) continue;

	// calculamos h[i][j] baseando-nos na célula acima
	if (B[i-1][j] == 1) h[i][j] = 1+h[i-1][j];
	else h[i][j] = 1;
	}
	}
	}

	void calc_j0(void)
	{
	for (int i = 1; i < n; i++)
	{
	stack<pii> stk;

	for (int j = 1; j < m; j++)
	{
	// algoritmo 2

	while (!stk.empty() && stk.top().second >= h[i][j])
	stk.pop();

	// se j0 não existe, digamos que ele será uma posição a
	// menos do limite (1)
	if (stk.empty()) j_0[i][j] = 0;
	else j_0[i][j] = stk.top().first;

	stk.push({j, h[i][j]});
	}
	}
	}

	void calc_j1(void)
	{
	for (int i = 1; i < n; i++)
	{
	stack<pii> stk;

	for (int j = m-1; j >= 1; j--)
	{
	// algoritmo 2

	while (!stk.empty() && stk.top().second >= h[i][j])
	stk.pop();

	// se j1 não existe, digamos que ele será uma posição a
	// mais do que o limite (m-1)
	if (stk.empty()) j_1[i][j] = m;
	else j_1[i][j] = stk.top().first;

	stk.push({j, h[i][j]});
	}
	}
	}

	int main(void)
	{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++)
	scanf("%d", &A[i][j]);

	// checando todas as matrizes 2x2
	for (int i = 1; i < n; i++)
	for (int j = 1; j < m; j++)
	if (A[i][j]+A[i+1][j+1] <= A[i+1][j]+A[i][j+1])
	B[i][j] = 1;

	calc_h();

	calc_j0();
	calc_j1();

	// resposta do problema
	int ans = 0;

	for (int i = 1; i < n; i++)
	for (int j = 1; j < m; j++)
	if (h[i][j])
	ans = max(ans, (j_1[i][j]-j_0[i][j])(h[i][j]+1)); // (x_m+1)(y_m+1)

	printf("%d\n", ans);
	}

view raw noic-fase2-p2-matriz.cpp hosted with ❤ by GitHub