Brigadeiros OBI F3 2024

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.

Clique aqui para conferir o código.