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

Solução por Lúcio Figueiredo

Conhecimento prévio necessário:

• Programação Dinâmica

Uma das grandes dificuldades presentes nesse problema é o valor alto das constantes $W$, $B$ e $X$. Isso nos impede de usar, por exemplo, algum tipo de programação dinâmica que dependa de tais constantes nos seus estados.

No entanto, há dois valores "pequenos" no problema: $n$ (que é no máximo $10^3$) e o somatório de pássaros nas árvores (no máximo $10^4$). Vamos explorar este fato, pensando em algum tipo de programação dinâmica que use estas constantes pequenas em seus estados.

Vamos então definir a seguinte DP: $dp[i][j]$ é a quantidade máxima de magia que podemos obter no momento em que saímos da árvore $i$ e vamos para a árvore $i+1$, assumindo que já conseguimos chamar $j$ pássaros.

Note que, caso seja possível calcular a DP de maneira eficiente, a resposta do problema é o máximo valor $j$ tal que $dp[n][j] \geq 0$, já que só podemos chamar uma quantidade de pássaros se em todos os momentos estivermos com uma quantidade positiva de pontos de magia. Portanto, o que resta é achar uma maneira eficiente de calcular a DP.

Imagine que acabamos de chegar na árvore $i$, já chamamos $j$ pássaros e vamos chamar $k$ dentre os $c_i$ pássaros na árvore $i$ ($0 \leq k \leq c_i$). Ignorando o fato de que há uma capacidade máxima de magia, podemos obter a seguinte recorrência:

$dp[i][j+k] = dp[i-1][j] + X - custo[i] \cdot k$

.

Isto se deve ao fato de que ao $dp[i-1][j]$ já contém a quantidade de magia que possuíamos logo após sair da árvore $i-1$. Após escolhermos $k$ pássaros na árvore $i$, perdemos $custo[i] \cdot k$ de magia e ao prosseguirmos da árvore $i$ para a $i+1$, ganhamos $X$ pontos de magia.

O único problema restante é a capacidade máxima de magia. Porém, podemos facilmente lidar com isso. Perceba que, se usarmos $j+k$ pássaros, a capacidade de magia que possuíremos é $B \cdot (j+k) + W$, pois possuíamos capacidade mágica $W$ inicialmente. Logo, se $dp[i-1][j] + X - custo[i] \cdot k$ (o valor da recorrência acima) for maior que $B \cdot (j+k) + W$ (a capacidade máxima de magia escolhendo $j+k$ pássaros), o valor de magia que obteremos é exatamente a capacidade máxima de magia. Caso contrário, o valor de magia será o valor da recorrência acima.

O que resta analisar é a complexidade da solução. Como a DP possui estados de complexidade $O(n)$ e $O(c)$, (onde $c$ é o maior valor $c_i$) e há $c_i$ transições na $i$-ésima árvore (precisamos escolher um $k$ entre $0$ e $c_i$), em uma primeira análise podemos afirmar que a complexidade será $O(n \cdot c^2)$. Porém, na verdade, a complexidade da DP será $O(c \cdot (\sum_{i=1}^n c_i))$, e esté valor é, nó máximo, $10^4 \cdot 10^4 = 10^8$. Portanto, a solução é eficiente.

Confira o código abaixo para melhor entendimento: