Doceria – Seletiva IOI 2021

Doceria

Comentário por João Pedro Castro

Subtask 2 – $C_i = E_i = 1$

Conhecimento prévio necessário:

• Set

Como todos os doces tem o mesmo custo, e nesse caso é 1, sempre fazer sentido pegar os $min(R, N)$ doces com maior doçura. Para lidar com as mudanças podemos manter um multiset e em cada atualização apagar $D_{X_i}$ e adicionar $F_i$, para depois pegar os $min(R, N)$ doces com maior doçura. A complexidade é $O(N \cdot (log(N) + min(R, N)))$.

Clique aqui para ver uma possível implementação.

Subtask 1 – $E_i = C_{X_i}$ e $F_i = D_{X_i}$

Conhecimento prévio necessário:

• Knapsack DP (Problema da Mochila)

Nessa subtask o cenário após toda mudança é o mesmo, logo basta usar uma DP no mesmo modelo da knapsack para calcular a resposta para o problema inicial, e depois imprimir o mesmo valor após cada mudança. A complexidade é $O(N \cdot R)$.

Subtask 3 – $F_i = 0$

A ideia dessa subtask é a de que nunca faz sentido pegar os doces já atualizados, já que a doçura deles agora é 0. Podemos “renomear” os doces, falando que o primeiro doce a ser atualizado tem número $N$, o segundo número $N - 1$, etc. Com o último doce a ser atualizado tendo número $1$. Agora, podemos rodar uma knapsack normal nessa ordem atualizada, e com $dp[i][j] =$ usando os $i$ primeiros doces e $j$ reais qual a maior doçura atingível. Assim, para a atualização $k$ a resposta é $dp[i - k][R]$, já que não usamos os últimos $k$ doces. A complexidade é $O(N \cdot R)$.

Clique aqui para ver uma possível implementação.

Subtask 4 – $X_i = i$

Podemos fazer duas knapsacks, com $pf[i][j] =$ usando os $i$ primeiros doces com seus valores atualizados e $j$ reais qual a maior doçura atingível; e $sf[i][j] =$ usando os últimos $i$ primeiros doces com seus valores não atualizados e $j$ reais qual a maior doçura atingível. Assim, para cada atualização $k$ sabemos que usaremos uma quantidade $x \leq R$ reais nos $k$ primeiros doces, conseguindo $pf[k][x]$ de doçura, e usaremos $R - x$ reais nos últimos $N - k$ doces, conseguindo $sf[N - k][R - x]$ de doçura. Assim, para cada atualização podemos brutar o $x$ ótimo, e deixar $pf[i][j]$ e $sf[i][j]$ pré-calculados.

Subtask 5 – Sem restrições adicionais

A solução é basicamente a mesma da subtask 4, mas com a ideia adicional da subtask 3 que podemos “renomear” os doces. Assim, renomeamos o primeiro doce a ser atualizado como 1, o segundo como 2, etc, e o último como $N$.

Clique aqui para ver uma possível implementação.