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

Solução por Samyra Almeida

Conhecimentos prévios:

• Programação Dinâmica
• Divisão e Conquista para otimizar DP's (tutorial em inglês)

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