Comentário NOIC OBI 2018 - Fase 1 - Programação Nível 1

Comentário por Lúcio Cardoso

Xadrez

Conhecimento prévio necessário:

1. Estruturas condicionais (Aula 2)
2. Operador de resto da divisão (Aula 2)

Seja $(x,y)$ o quadrado na linha $x$ e coluna $y$ do tabuleiro. Já que a cor do quadrado $(1, 1)$ é branca, a cor de cada quadrado $(x,y)$ pode ser encontrada baseando-se nos seguintes casos:
1. Se x e y tem a mesma paridade, a cor de $(x,y)$ é branca.
2. Se x e y tem paridades diferentes, a cor de $(x, y)$ é preta.
Como queremos encontrar a cor do $(L,C)$ (canto inferior direito), basta checar em qual dos casos o quadrado se encaixa, imprimindo sua respectiva cor. Segue o código para melhor entendimento.

Escadinha

Conhecimento prévio necessário:

1. Estruturas de repetição (Aula 2)
2. Vetores (Aula 3)

Perceba que uma escadinha é, na verdade, uma Progressão Aritmética (PA). Então, o problema se resume em encontrar a quantidade de PAs na sequência tais que nenhuma delas esteja totalmente contida em alguma outra,
e todas as PAs calculadas possuam o maior tamanho possível. Assim, para um índice $i$ (inicialmente 1), encontraremos o maior índice $j$ tal que a sequência de $i$ a $j$ seja uma PA, repetindo o processo novamente, ou seja, fazendo o novo indíce inical de uma escadinha sendo $j$, até que o último índice seja o próprio fim da sequência $(n)$. Segue o código para melhor entendimento.

Pirâmide

1. Programação dinâmica (Aula 13)

Para cada linha $i$ da pirâmide com $i$ caixas numeradas por colunas de $j$ a $j+i-1$, a linha acima $(i-1)$ possui $i-1$ caixas consecutivas, ou com colunas desde $j$ a $j+i-2$, ou desde $j+1$ a $j+i-1$, já que, caso contrário, ao menos uma das caixas não possuiria uma respectiva caixa abaixo dela, na linha $i$. Assim, podemos utilizar uma função recursiva $f(k, j)$ para encontrar a resposta mínima do problema, representando a pirâmide com a linha de índice $k$ em sua base, e que por sua vez tem $k$ caixas consecutivas a partir da coluna $j$. Temos, assim, que:

1. O caso base da função pode ser tomado quando $k = 1$, já que a resposta neste caso é apenas o valor da caixa na linha $1$, coluna $j$.
2. Como a linha $k$ é a base da pirâmide, a soma de todos os valores das $k$ caixas desde a coluna $j$ até a coluna $j+k-1$ estará incluída na resposta de $f(k, j)$.
3. Pelas observações anteriores, há dois casos para a coluna inicial na linha $k-1$: ou $j$, ou $j+1$. Perceba que assim, a coluna final em tal linha está definida: será, respectivamente, $j+k-2$ ou $j+k-1$, já que a linha $k-1$ possui $k-1$ caixas. Como queremos a soma mínima possível dos valores das caixas, escolheremos o mínimo entre estes dois casos.

Podemos, então, finalmente montar a relação de recursão de $f(k, j)$:
Se $k = 1$, $f(k, j) = caixa[1][j];$
Senão, $f(k, j) = s[k][j...j+k-1] + min(f(k-1, j), f(k-1, j+1))$, onde $s[x][a...b]$ é a soma dos números na linha $x$ desde a coluna $a$ até a coluna $b$. No entanto, a complexidade da função é exponencial, e logo, não passa nas restrições do problema. Para tornar a complexidade aceitável, utilizaremos duas técnicas adicionais:

1. Podemos conseguir $s[x][a..b]$ em $O(1)$, com pré-cálculo em $O(n²)$, da seguinte maneira: Primeiro, vamos definir uma matriz $soma[x][b]$ como sendo a soma dos números na linha $x$ desde a coluna $1$ até a coluna $b$. Inicialmente, $soma[x][0] = 0$, para todo $x$ tal que $1 <= x <= n$. Então, $soma[x][b] = soma[x][b-1]+caixa[x][b]$, com $1 <= b <= n$. Portanto, é possível conseguir $s[x][1...b]$ em $O(1)$ após o pré-cálculo, já que $s[x][a...b] = s[x][1...b]-s[x][1...(a-1)]$, ou seja, $s[x][a...b] = soma[x][b]-soma[x][a-1]$.
2. Finalmente, usaremos uma matriz $n*n$ chamada $dp[n][n]$ que irá guardar todos os estados que já foram previamente calculados na recursão (essa técnica é conhecida como programação dinâmica). Assim, evitamos que um estado seja calculado mais de uma vez, tornando a complexidade da função $O(n²)$, já que $1 <= k, j <= n$. Obteremos então a resposta do problema chamando $f(n, 1)$.
Segue o código para melhor entendimento.