CF OBI 2023 - Programação Nível 2

Estante

Comentário por Henrique Vianna

Conhecimentos Prévios Necessários:

Programação Básica

Nesse problema, queremos distribuir $X + Y + Z$ livros em $N$ prateleiras de tal forma que todas elas tenham a mesma quantidade de livros, sendo que essa quantidade, que chamaremos de $Q$ , deve ser maximizada. Intuitivamente, cada uma das prateleiras receberá $Q = \lfloor \frac{X+Y + Z}{N} \rfloor$ livros, sobrando então $X + Y + Z - Q * N$ livros, que é exatamente igual a $(X + Y + Z) \% N$ . Note que comos os valores fornecidos podem ser grandes (até $10^{18}$ ), temos que ler nossas variáveis como long long.

Clique aqui para conferir o código

Garrafões

Comentário escrito por Estela Baron

Conhecimentos prévios necessários:

Introdução à Programação Dinâmica

Subtask M = 1 e 1<= G <= 10:

Note que só pilhas com 1 ou 5 garrafões poderão ser utilizadas, pois temos no máximo 10. Então, veja que $G$ até 4 só tem uma maneira: todo mundo igual a 1. A partir de 5, ganhamos mais uma possibilidade: usar a pilha com 2 camadas. De 5 até 9, vamos ganhando toda vez mais uma maneira de arranjar (tudo com 1, e uma com 5 e o resto com 1 - variando as posições). Com 10 garrafões, podemos fazer tudo com pilhas de 1; 1 pilha com 5 e o resto com 1; 2 pilhas de 5.

Subtask M = 2 e 1 <= G <= 10:

Note que, como queremos minimizar, de 1 até 4 garrafões temos só uma possibilidade - todas pilhas com 1 garrafão. A partir de 5 até 9, podemos utilizar uma pilha com 2 camadas, um total de 5 garrafões. Com isso, o restante vira pilhas de 1 garrafa. Logo, basta contar a quantidade de pilhas totais: (1 + G-5), pois seria a mesma coisa de contar todos os arranjos das posições da pilha com 2 camadas. Por fim, com $G = 10$ , a única possibilidade para a menor quantidade de pilhas é quando temos duas com 2 camadas (cada pilha com 5).

Subtask M = 1 e 1 <= G <= 100000:

Para essa tarefa, vamos usar uma dp. Vamos começar declarando um vetor dp[quantidade de garrafões] = número de formas de arranjar as pirâmides. Para calcular essa dp, vamos fazer uma abordagem iterativa: vamos calcular o caso base e, para todo outro estado, vamos usar algum estado anterior. O caso base é dp[0] = 1, pois só há uma maneira de ter 0 garrafões: que é não colocando nenhum.

Por exemplo, digamos que já calculamos todos os valores de 0 até 20. Então, se eu quero calcular o estado dp[21], eu vou "testar" todos os tamanhos de pilhas que podem estar no final. Quando a última pilha tiver 1 camada, temos que dp[21] += dp[21 - 1]. Quando a última pilha tiver 2 camadas (5 garrafões) : temos que dp[21] += dp[21 - 5]. Quando tiver 3 camadas: dp[21] += dp[21 - 14]. Quando tiver 4 camadas, não poderemos ter, pois o número de garrafões seria igual a 30, o que é maior que o nosso número no exemplo (21). Então, no fim, temos que dp[21] = dp[20] + dp[16] + dp[7].

Assim, podemos usar a estratégia do exemplo para calcular todos os estados: podemos pré-calcular a quantidade de garrafões para cada tamanho de pilha ou podemos usar a fórmula da soma de quadrados: a soma dos n primeiros quadrados é igual a n*(n+1)*(2*n+1)/6. Depois, para cada estado, adicionamos o valor que obtemos quando tiramos a quantidade de uma pilha. A resposta será dp[G]. Lembre de sempre tirar o módulo. Note que o número de camadas não passa de 100 - no código final, o limite ficou 200, mas é só uma aproximação. A complexidade final fica $O(G*100)$ , ou seja, $O(10^7)$ .

Subtask sem restrições adicionais:

Observe que esta subtask é a junção da anterior com a do M = 2 e 1 <= G <= 100000. Vamos utilizar a mesma abordagem vista anteriormente de dp iterativa, mas com uma pequena mudança: ao invés de cada estado guardar somente um valor, agora o vetor guardará um pair<int,int>: dp[quantidade de garrafões] = {menor quantidade de pilhas, número de formas de arranjar as pirâmides com a menor quantidade de pilhas}.

O caso base é dp[0] = {0,1}, pois não temos nenhuma pilha com 0 garrafão e temos 1 possibilidade: não colocar ninguém. Para cada novo estado (i), vamos utilizar a mesma ideia de retirar a última pilha, ou seja, tirar uma quantidade k de garrafões e ver se dp[i-k].first + 1 é a menor quantidade de pilhas que eu consigo com i garrafões. Se for, eu adiciono o valor de dp[i-k].second - quantidade de maneiras- em dp[i].second. Com isso, a nossa resposta será dp[G].second. Lembre de tirar o módulo e, da mesma forma, o limite de camadas não passa de 100. A complexidade final fica igual à outra subtarefa: $O(G*100)$ .

Para conseguir todos os pontos, só precisa juntar o M = 1 e o M = 2 em um único código: pode fazer duas condições diferentes e tratar cada caso.

Clique aqui para conferir o código.

Machine Learning

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

A ideia principal do problema é bem direta: percorremos as palavras do artigo, vemos em qual tópico cada palavra está e contamos qual tópico mais aparece.

$(Subtask$ $2)$ $X \le 10^3$

Um jeito de descobrir em qual tópico uma certa palavra está é procurar tópico por tópico e palavra por palavra dentro de cada tópico.

Complexidade: existem $N$ tópicos, cada tópico tem $K_i$ strings e cada string tem tamanho $s_i$ , então procurar o tópico de uma palavra é $O(NK_i s_i)$ . Como repetimos o processo $X$ vezes, temos a complexidade final $O(XNK_i s_i)$

$(Subtask$ $3)$ $X \le 10^5$

É fácil ver que é possível saber em qual tópico uma certa palavra está de uma maneira bem mais rápida. Quando estamos lendo os tópicos e suas respectivas palavras, salvamos o tópico de cada palavra em um map. Assim, podemos acessar o tópico de qualquer palavra fazendo map[palavra].

Complexidade: acessar cada palavra no map é $O(s_i*log)$ (o que fazemos $X$ vezes) e construir todo o map é $O(NK_i s_i log)$ , então a complexidade final é $O(X s_i log + NK_i s_i log)$ .

Confira o código

Viagem

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Vamos definir como $frutas[N][K]$ o vetor tal que, para cada vértice $v$ e cada fruta $f$, $frutas[v][f]$ guarda quantas frutas $f$ tem no caminho de $1$ até $v$, além disso, defina $anc[N][LOGN]$ como o vetor de ancestrais do grafo, igual num LCA.

Primeiro, já sabemos como calcular $anc[N][LOGN]$ (Caso não saiba, veja a aula de LCA), agora, como calcular $frutas[N][K]$ ? Para isso, vamos fazer uma dp na árvore! Começamos no $1$, e sabemos que $frutas[1][f]$ é a quantidade de frutas que tem no vértice $1$ , pois o caminho de $1$ para $1$ só contem $1$ . Com isso, suponha que estamos no vértice $v$ , e queremos descer para os filhos dele. Seja $x$ um desses filhos, então, a quantidade de $f$ frutas no caminho de $1$ para $x$ é igual a quantidade de frutas $f$ no caminho de $1$ para $v$ mais a quantidade de frutas em $x$ , pois $v$ é o pai de $x$ , ou seja, ele participa no caminho de $1$ para $x$ . Logo, a transição da nossa dp seria

$frutas[x][f] = frutas[v][f] + c[x][f]$

Onde $c[x][f]$ é a quantidade de frutas em $x$ . Depois de fazermos isso para cada fruta, chamamos dfs(x). Essa dp é calculada em $O(NK)$ .

Agora, dada esse vetor, como calcular nossa resposta? Seja $a, b$ os vértices que estamos fazendo a pergunta. Vamos dividir em 2 casos:

Se $lca(a, b) = 1$ , então, nossa resposta vai ser a quantidade de frutas no caminho de $a$ para $1$ , mais a quantidade de frutas no caminho de $b$ para $1$ , porém, nessa contagem repetimos a quantidade de frutas em $1$ duas vezes, então, tiramos a quantidade de frutas em $1$ . Ou seja, a formula fica

$frutas[x][f] + frutas[v][f] - frutas[1][f]$

Para cada fruta, e então, basta verificar se essa fórmula é ímpar.

Agora, se $lca(a, b) != 1$ , seja $l = lca(a, b)$ , então, o caminho que vamos pegar as frutas vai ser de $a$ para $l$ e de $l$ para $b$ . Para calcular a quantidade de frutas de $a$ para $l$ , como $l$ está no caminho de $a$ para $1$ , basta ver a quantidade de frutas no caminho de $1$ para $a$ , e tirar a quantidade de frutas no caminho de $1$ para $pai[l]$ ( $pai[l]$ é o vértice logo acima de $l$ na árvore). Para $b$ , a fórmula fica a mesma, ou seja, a fórmula fica

$frutas[a][f] + frutas[b][f] - 2*frutas[pai[l]][f]$

Porém, veja que repetimos $l$ duas vezes nesse caso, então, também temos que tirar $c[x][f]$ uma vez. Logo, a formula final é

$frutas[a][f]+frutas[b][f]-2*frutas[pai[l]][f]-c[l][f]$

E então, basta ver se essa fórmula é impar.

Ambas as formulas são calculadas em $O(k)$ , mas para achar o lca, fica $O(log n)$ , então a complexidade final é $O(NK + NlogN + Q(logN+K))$ , que passa.

Clique aqui para ver o código