Solução Informática - Nível Avançado - Semana 30

Escrito por Enzo Dantas

Conhecimento prévio necessário:

• Programação Dinâmica (DP)

A ideia mais básica (força bruta) para resolver esse problema é testar todas as possíveis entradas, o que teria uma complexidade de ${N\choose K} * N$ (${N\choose K}$ para conseguir todos as combinações de entradas possiveis e $N$ para simular cada uma delas). Antes de tudo, perceba como essa ideia calcula muitas coisas repetidas e pense como poderíamos calcular um certo estado (combinação de entradas) rapidamente baseado em outro estado "menor". Sendo assim, temos duas partes do problema que temos que resolver: 1) Como simular uma combinação de entradas e 2) Como otimizar a ideia de força bruta.

Como simular uma combinação de entradas

Primeiramente, usaremos o truque de duplicar o array para simular um círculo.

Assuma que temos uma entrada na posição $e$ e outra na posição $f$. Perceba que uma pessoa no salão $j$ $(e \leq j < f)$ vai ter uma desconforto $j-e$. Logo, um salão $j$ que contém $v_{j}$ pessoas vai gerar um grau de desconforto de $v_{j} * (j-e)$. Sendo assim, para calcular o desconforto em relação a uma entrada, faremos um for começando de $e$ e adicionar $v[i] * (i-e)$ ($e\leq i < f$) ao contador de desconforto. As salas depois de $f$ são calculadas em relação a $f$.

Como otimizar a ideia de força bruta

Usaremos uma DP do tipo $dp_{l, r, k}$ = mínimo desconforto gerado tal que há uma entrada no índice $l$, a primeira entrada de todas está no índice $r+1$ e ainda podemos criar $k$ entradas.

Inicialmente, vamos brutar o $r$, ou seja, vamos testar colocar a primeira entrada em todos os índices. Testaremos todas as combinações de entradas da seguinte maneira: se estamos no estado (l, r, k) tal que $k \geq 1$, podemos criar uma entrada em qualquer índice $j$ entre $l+1$ e $r$, o que nos leva ao estado $dp_{j, r, k-1}$. Além disso, quando criamos uma entrada em $j$ levamos em conta o desconforto das salas entre $e$ e $j$. Sendo assim, formalmente, $dp_{l, r, k} = min(cont + dp_{j, r, k-1})$, tal que $cont$ é o desconforto das salas entre $e$ e $j$.

Os casos base são quando $k=0$, ou seja, não podemos criar nenhuma outra entrada então apenas simularemos como descrito acima e quando $l=r$, onde o resultado é sempre 0.

É facil ver que a DP possui $N^2*K$ estados. Como em cada estado fazemos um for de tamanho possivelmente $N$, a complexidade da DP é $O(N^2*K*N)$ = $O(N^3*K)$.

 

Recomendamos que você tente implementar o problema antes de ver o código. Para conferi-lo, clique aqui.