TFC 2021

Para conferir a prova na íntegra, clique aqui.

Amizade

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops

Para este problema, precisamos ler a entrada e, para cada $M_i$, verificamos se a diferença entre $A$ e $M_i$ é menor ou igual a $D$. Observe que é necessário comparar o valor absoluto da diferença, então podemos usar a função $abs()$, que retorna o valor absoluto de um número.

Clique aqui para conferir o código

Livros

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Soma de Prefixos
• Compressão de Coordenadas

Nesse problema, é fundamental analisar os limites e as subtasks, porque, caso a ideia para a questão inteira não esteja clara, ainda é possível conseguir pontos das parciais.

A princípio, uma das primeiras ideias que podemos ter para resolver o problema é, para cada $X_i$ e $Y_i$, adicionar em um vetor, em que cada posição representa um dia e guarda a quantidade de livros lidos naquele dia, +1 em todos os dias de $X_i$ até $X_i + Y_i - 1$, por meio de um $for$.

No entanto, apesar dessa solução atender a subtask 2, há diversos problemas com a complexidade e a memória. Para cada livro, no pior caso, teríamos que percorrer $10^9$ posições, resultando em uma complexidade de $O(N*Y)$, a qual estouraria o limite de tempo - e também não tem como criar um vetor com $10^9$ posições, por causa da memória.

Primeiro, vamos ignorar o problema de acessar as posições e concentrar em como não ter que percorrer todas as $Y_i$ posições quando estivermos analisando um livro. Para isso, vamos utilizar um truque muito comum para soma em intervalos contínuos, que é adicionar +1 na posição de início (no caso $X_i$) e somar -1 na posição imediatamente após a última do intervalo (no caso $X_i + Y_i$). No final, quando fazemos a soma acumulada, todas as posições de $X_i$ até o final ganham + 1 e todas as posições de $X_i + Y_i$ perdem -1, totalizando um acréscimo de 1 no intervalo desejado e 0 no restante. Com isso, conseguimos adicionar um livro em todos os dias do intervalo em $O(1)$ e, no final, obtemos a quantidade exata de livros lidos em cada dia - obtendo, assim, a resposta.

Agora, vamos resolver o problema do acesso às posições. Observe que só precisamos de duas posições para somar em um intervalo - o início e o fim + 1. Isso nos possibilita comprimir as coordenadas, ou seja, transformamos todos os dias que precisamos ($X_i$ e $X_i + Y_i$) em novos índices, de forma que tenha no máximo $2*N$ posições no vetor que usamos para calcular a soma acumulada. Podemos fazer isso colocando cada $X_i$ e cada $X_i + Y_i$ em um $vector$ e ordenar. Após isso, com um map, atribuímos um novo índice para esse dia e adicionamos +1 ou -1 a essa posição.

Por último, fazemos uma soma de prefixos e salvamos o maior resultado que aparece.

Clique aqui para conferir o código

Figurinhas

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Árvores
• DFS
• Bitmask

Observe que existem exatamente $N-1$ arestas ligando bancas diferentes, isso é uma das propriedades de uma árvore, portanto, o problema envolve árvores! Outra observação legal de se fazer ao observar as restrições é que há no máximo 20 tipos de figurinhas. Tal informação nos permite representar um conjunto de figurinhas em um inteiro ao invés de usar um $vector$ - aula de bitmask. Outra constatação importante é que a banca de origem é fixa para todas as $Q$ consultas, isso nos permite pré-calcular o resultado a quantidade de figurinhas diferentes para cada banca e depois só responder as consultas. Ao fazer esse passo, evitamos ter que calcular cada consulta individual - o que tornaria a nossa complexidade quadrática, ou seja, incorreta.

Portanto, só precisamos fazer uma $dfs$ a partir do nosso ponto de origem. Para fazer isso, notamos que, como só há um caminho de $U$ para $V$, se é possível chegar em $V$ a partir de $U$, então $V$ recebe todas as figurinhas que $U$ consegue adquirir partindo de $S$. Para fazer essa junção das figurinhas de $U$ com as de $V$, podemos utilizar o operação binária OU (|) - assim, se tivermos ou bit aceso na posição $i$, que representa a figurinha do tipo $F_i$, a representação binária resultante da operação também terá. Exemplo: suponha que $mask[U]$ = $10100$ e $mask[V]$ = $11010$, temos que $U$ tem as figurinhas dos tipos 2 e 4 (indexa do 0 da direita para a esquerda) e $V$ tem as figurinhas dos tipos 1, 3 e 4. Quando fazemos a junção desses dois conjuntos - que representa quais figurinhas conseguimos de $S$ até $V$- obtemos $11110$, ou seja, é possível coletar as figurinhas dos tipos 1, 2, 3 e 4. Assim, atualizamos a $mask[V]$ para $11110$ e continuamos para as outras bancas.

Ao final, para cada consulta, basta acessarmos o número em $mask[D_i]$ e descobrir quantos bits estão acesos - a nossa resposta. Para fazer esse último passo, como podemos ter no máximo 20 bits acesos, é possível realizar um $for$ e checar por meio da operação binária AND (&) se $1 << i$ & $mask[D_i]$ é diferente de zero. Se for, significa que o bit está aceso, ou seja, temos uma figurinha do tipo $F_i$ e que podemos adicionar uma figurinha a nossa resposta. No fim, teremos a quantidade exata de figurinhas diferentes que podemos obter do caminho de $S$ até $D_i$.

Clique aqui para conferir o código

Anagrama

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• String
• Map

Enunciado

Primeiramente, é necessário entender bem o enunciado e entender o que ele pede, pois ele é, de fato, confuso. O enunciado diz "o número máximo de possíveis pares de anagramas que poderiam ser formados considerando todas as possibilidades de correspondência". Utilizando o exemplo fornecido, entre todos os pares das palavras "dados", "caixa" e "testa", é possível formar um par de anagramas com 3 deles. Note que é possível formar exatamente 3_escolhe_2 = $3 \choose 2$ = 3 pares com 3 palavras, o que significa que qualquer par pode formar um par de anagramas nesse caso. Isso indica que "dados" pode formar um anagrama com "caixa" ao mesmo tempo que pode formar um anagrama com "testa", apesar de não usar o mesmo embaralhamento, e as duas possibilidades são contadas na resposta. Ou seja, cada par é analisado individualmente. A pergunta então é "quantos pares de palavras, analisados individualmente, poderiam formar um par de anagramas?"

Checagem

A etapa mais importante da solução é saber checar se é possível que um par de palavras forme um par de anagramas. Analisando os casos teste e tendo em mente a condição para que duas palavras sejam um par de anagramas, observamos o seguinte padrão: as palavras "caixa" e "testa" possuem um letra que se repete uma vez ('a' e 't') e todas as outras não se repetem, além de possuírem o mesmo tamanho.

A mesma situação acontece na palavra "dados". Observe que não importa como as letras estão organizadas, tudo que importa para que duas palavras sejam um par de anagramas é a frequência das letras. Como é possível transformar uma letra em qualquer outra letra usando o embaralhamento, a condição final ignorará as letras em si e focará na frequência delas.

A condição final é a seguinte: para que duas palavras possam formar um par de anagramas, a quantidade de letras cuja frequência é igual a $i$ deve ser igual em ambas $\forall 1 \le i \le 20$. Ambas as palavras "acbcb" e "ddefe", por exemplo, possuem duas letras com frequência igual a 2 e uma letra com frequência igual a 1 e, portanto, podem formar um par de anagramas.

Em relação à implementação, é possível guardar, para cada frequência, quantas letras a possuem, mas aqui utilizaremos a seguinte ideia (que é mais simples de implementar): para calcular as frequências das letras de uma palavra, percorreremos a palavra e salvaremos em um map a frequência de cada letra. Feito isso, vamos percorrer esse map e adicionar as frequências em um vector que vamos chamar de $aux$. Como comparar esse vector com o vector de outra palavra? Vamos ordená-los. Assim, caso os $aux$'s sejam exatamente iguais, então esse é um par válido.

Exemplo:

string = abbfe

map = $[a, 1]$, $[b, 2]$, $[e, 1]$, $[f, 1]$

aux = $[1, 2, 1, 1]$ e, após o sort, $[1, 1, 1, 2]$

Solução final

Para resolver a subtask 1 ($N=2$) , basta rodar o algoritmo acima entre as duas strings. Já para a subtask 2 ($N \le 10^3$), é possível percorrer cada par e rodar o algoritmo de checagem neles, o que tem uma complexidade de aproximadamente $O(N^2)$. Para a solução final, perceba que, se $X$ palavras possuem o mesmo vector $aux$, então escolher qualquer duas dessas palavras formará um par válido. Ou seja, é possível formar $X \choose 2$ pares válidos com essas palavras. Sendo assim, vamos salvar a frequência de cada vector $aux$ em um map e para cada um adicionaremos $frequencia \choose 2$ na resposta. A complexidade final é $O(N \cdot (m \cdot log_m + m \cdot log_n))$ tal que $m$ é o tamanho da maior string. Como $m \le 20$, a complexidade é aproximadamente $O(N \cdot m \cdot log_n)$. É possível ainda reduzir essa complexidade para $O(N*m)$ usando um unordered_map em vez de um map normal, mas é desnecessário nesse caso.

Clique aqui para conferir o código