Solução Informática Avançado – Semana 72

Solução por Samyra Almeida

Conhecimentos prévios:

Para resolver esse problema primeiro vamos definir como $custo[a][b]$ , onde $a < b$ , como o custo de colocar o intervalo de $a$ até $b$ , inclusive, em uma mesma gôndola, ou seja, as somas dos níveis de não familiaridade entre todos os pares $i, j$ onde $a \leq i < j \leq b$ .

Como $u_{ij} = u_{ji}$ , podemos concluir que a matriz $u$ é espelhada em sua diagonal( da esquerda para a direita). Sabendo disso, só iremos processar o custo de uma das metades. Agora, vamos criar o vetor sum[][] como: $sum[i][j] =$ soma de todos elementos dentro do retângulo definido pelas posições $(1, 1)$ e $(i, j)$ , onde:

$sum[i][j] = sum[i][j - 1] + sum[i - 1][j] + u[i][j] - sum[i - 1][j - 1]$

Para calcular o $custo[i][j]$ , sendo $i < j$ , iremos fazer:

$custo[i][j] = sum[j][j] - sum[i - 1][j] - sum[j][i - 1] + sum[i - 1][i - 1]$

Suponha que $n = 5$ e que estamos calculando o $custo[2][4]$ .

Sabemos que:

$custo[2][4] = sum[4][4] - sum[1][4] - sum[4][1] + sum[1][1]$

Note que se descontarmos da parte vermelha (sum[4][4]), imagem da esquerda, a parte amarela mais a verde $(sum[4][1])$ e a parte azul mais a verde $(sum[1][4])$ , os dois últimos na imagem da direita, e somarmos a parte verde $(sum[1][1])$ , que foi descontada duas vezes. Teremos o dobro do $custo[2][4]$ , pois a matriz é refletida, ai basta dividir o $custo[2][4]$ por dois.

Já que já calculamos a matriz de custo, vamos de definir a $dp[i][j] =$ o valor total mínimo de não familiaridade entre as $j$ -ésimas primeiras pessoas que estão nas $i$ primeiras gôndolas.

Suponha que para calcularmos a $dp[i][j]$ já sabemos a resposta da $dp[i - 1][a], \forall \space a \space | \space1 \leq a \leq j$ , e para a $dp[i][j]$ adicionamos uma gôndola a mais. Com isso, podemos notar que a resposta de $dp[i][j]$ é igual ao mínimo entre um dos estados da $dp$ utilizando $i - 1$ gôndolas até o $a - 1$ -ésimo cara na fila mais o custo de colocar da $a$ -ésima até a $j$ -ésima pessoa na $i$ -ésima gôndola. Formalizando, temos:

$dp[i][j] = min(dp[i - 1][a - 1] + custo[a][j]), \forall \space a \space | \space 1 \leq a \leq j$

Note que, em cada estado da $dp$ passamos por no máximo $n$ posições, e como existem $k*n$ estados, a complexidade final desse algoritmo é de $\mathcal{O}(k*n^2)$ . O que é bem ruim. Por isso, iremos utilizar uma técnica de otimização de DP's chamada Divisão e Conquista. Valhe lembrar que não estamos falando da técnica de programação chamada Divisão e Conquista e sim da Otimização de DP (programação dinâmica).

Para que possamos aplicar Divisão e Conquista, temos que provar que