Brigadeiros
Comentário escrito por João Pedro Castro
Conhecimento prévio necessário:
- Introdução à Programação Dinâmica
- Problema da Mochila – Tecnicamente opcional, mas meio impossível fazer sem ter as ideias daqui.
Subtarefa 2: $$N \leq 50$$, $$K \leq 3$$, $$T \leq 1000$$
Vamos brutar tudo (testar todas as possibilidades de algo). Primeiro, vamos brutar as $$K$$ posições finais, isso é $$O({N \choose K})$$. Agora, para cada uma dessas possibilidades vamos brutar a ordem que cada um vai (se o primeiro menor das posições iniciais vai com a segunda menor das posições finais, etc), isso é $$O(K!)$$. Por fim, para cada um desses casos conseguimos calcular em $$O(K)$$ (mas até $$O(N)$$ passaria) o $$t$$ mínimo para chegar nessa posição, e se $$t \leq T$$ falamos que a resposta é o máximo entre a resposta atual e a soma da quantidade de brigadeiros nas posições finais. A complexidade final é $$O({N \choose K} \cdot K! \cdot K)$$.
Dica de implementação: para brutar todas as possibilidades, você pode criar um vetor de $$N$$ posições que comece com $$N – K$$ 0s e depois tenha $$K$$ 1s. E então, usar next_permutation para ver todas as possibilidades. Em uma dada permutação desse vetor original você pode dizer que se e somente se a i-ésima posição for igual a 1 tem alguém do grupo.
Subtarefa 3: $$N \leq 16$$, $$T \leq 1000$$
Podemos fazer a mesma estratégia da parcial anterior mas com uma observação a mais: sejam as posições iniciais do grupo $$s_1 < s_2 < … < s_k$$, e as finais $$f_1 < f_2 < … < f_k$$: para conseguir o tempo mínimo de chegar nessa posição é ideal dizer que o cara na posição $$s_i$$ vai para a posição $$f_i$$ para todo $$1 \leq i \leq k$$; ou seja, o menor vai com o menor, o segundo menor vai com o segundo menor, etc. A intuição disso é bem simples, e não é difícil “provar” (sem muita formalidade) fazendo umas contas.
Assim, conseguimos só brutar as $$O({N \choose K})$$ possibilidades de escolhas, e calcular o tempo para chegar lá em $$O(K)$$. A complexidade final é $$O({N \choose K} \cdot K)$$.
Dica: o caso onde $${a \choose b}$$ é maior é quando $$b = \frac{a}{2}$$, então nesse caso o pior é $${16 \choose 8} \approx 10^{4.1}$$, que ainda passa tranquilamente.
Subtarefa 4 e 5: $$N \leq 50$$, $$T \leq 10^5$$
Vamos usar programação dinâmica! Aqui a definição de cada parte:
- Estado: nosso estado vai ser $$dp_{i, j, t} = s$$, onde:
- $$i$$ significa que usamos as posições de 1 até $$i$$ para as posições finais dos membros do grupo que colocamos até agora.
- $$j$$ significa que já colocamos os $$j$$ primeiros membros do grupo.
- $$t$$ significa o tempo máximo que podemos usar para chegar na melhor soma possível.
- $$s$$ significa a melhor soma possível que conseguimos dado $$i$$, $$j$$ e $$k$$.
- Caso base: o único caso base necessário é $$dp_{0, 0, 0} = 0$$. O resto, se não calcularmos, pode ser visto só como $$-\infty$$.
- Transição: vou colocar várias possibilidades, e vai ser só o máximo entre elas.
- Podemos só não botar nada em $$i$$: $$dp_{i – 1, j, t}$$.
- Podemos ficar parados sem fazer nada: $$dp_{i, j, t – 1}$$.
- Se $$j > 0 $$, podemos botar o $$j$$-ésimo (do menor para o maior em posição) membro do grupo na posição $$i$$: $$dp_{i – 1, j – 1, t – |i – posicao_j|} + p_i$$ (perceba que essa transição só funciona por conta da nossa observação que é sempre melhor colocar o menor com menor, segundo menor com segundo menor, etc.)
- A resposta, dado o estado, é $$dp_{N, K, T}$$.
A complexidade é $$O(N^2 \cdot T)$$.
Subtarefa 6: $$N \leq 100$$
Vamos fazer a mesma DP, só que com uma observação a mais. Responda essa pergunta: se posso fazer trocas de elementos adjacentes, qual o número máximo de swaps para ordenar o vetor?
Se você já viu a técnica de bubble sort, essa pergunta tem uma resposta bem direta: é $$O(N^2)$$, e na verdade sempre vai ser menor que $$N^2$$ (não convém mostrar a conta aqui). Logo, posso chegar de qualquer ordenação do vetor para qualquer outra em menos de $$N^2$$ operações, ou seja, logo após receber o $$T$$ podemos dizer que $$T = min(T, N^2)$$ e a resposta ainda estaria certa, pois se existe uma resposta válida fazendo mais que $$N^2$$ trocas, também existirá uma fazendo menos que $$N^2$$ trocas.
Assim, tendo que $$T \leq N^2$$, temos uma complexidade de $$O(N^4)$$.
Subtarefa 7: Sem restrições adicionais.
Quando você leu o enunciado, idealmente se atentou de um detalhe específico que não seria colocado sem motivo: $$0 \leq P_i \ leq 9$$. Ou seja, todo prato tem entre $$0$$ e $$9$$ brigadeiros, mas o que isso faz a gente pensar? Se você já está acostumado com problemas de DP, é direto: a soma máxima é $$O(N)$$.
E uma técnica legal de problemas de DP, é que em diversos problemas se você tem algo como $$dp_{a, b, c} = d$$ (ou em um caso geral com quantas variáveis você quiser), você pode dizer que $$dp_{a, b, d} = c$$, ou qualquer outra troca. Ou seja, se você tem $$X$$ variáveis que indicam seu estado, e mais $$1$$ que indica sua resposta, você pode trocar qualquer uma das que indicam o estado com a da resposta que o estado ainda vai ser perfeitamente expressado. Claro que varia de problema a problema, e vai ter trocas melhores que outras, mas em problemas de DP sempre pense em qual a maneira com menos possibilidades de guardar esse estado.
No nosso caso, ao invés de fazer a $$dp_{i, j, t} = s$$, vamos fazer a $$dp_{i, j, s} = t$$. Já que o máximo de $$t$$ é $$O(N^2)$$ e o máximo de $$s$$ é $$O(N)$$. Agora a DP significa: colocando os $$j$$ primeiros do grupo em algumas das $$i$$ primeiras posições, qual o menor tempo $$t$$ para atingir a soma $$s$$? Se for impossível podemos só dizer que $$dp_{i, j, s} = \infty$$.
O estado foi explicado acima, o caso base é o mesmo, e o resto fica assim:
- Transição: de novo, colocarei várias coisas aqui, e agora só pegue o mínimo entre elas.
- Não colocamos nada em $$i$$: $$dp_{i – 1, j, s}$$.
- Colocamos o $$j$$-ésimo do grupo em $$i$$: $$dp_{i – 1, j – 1, s – P_i} + |i – posicao_j|$$.
- A resposta vai ser o maior $$S$$ tal que existam quaisuer $$x$$ e $$y$$ com $$dp_{x, y, S} \leq T$$.
Temos $$O(9 \cdot N^3)$$ estados, cada transição é $$O(1)$$, logo a complexidade final é $$O(9 \cdot N^3) = O(N ^3)$$.
OBS: A complexidade acaba ficando apertada, então para ficar tranquilo você tem que fazer pequenas “otimizações” (basicamente não passar por estados impossíveis), veja o código abaixo para ver as que fiz.