Ver classificação dos alunos que participaram
Nota: este treino usou problemas do COCI (Croatian Open Competition in Informatics) e será provável que voltemos a usar mais problemas desta competição para efeitos de treino.
Os enunciados foram traduzidos para português e adaptados. As descrições de soluções e o próprio código das soluções são também baseadas nas oficiais do COCI, também traduzidas e adaptadas. As soluções oficiais originais estavam em C++ e foram também transcritas para código Java equivalente.
Para descrever a complexidade temporal da solução iremos usar a notação Big-O. Podem ver uma pequena introdução no Loop: Introdução à Análise de Algoritmos.
Para determinar quantas cartas faltam de cada naipe, basta ler cada um dos caracteres que aparecem no input (que aparecem de 3 em 3 posições) e incrementar uma variável, para saber quantas cartas de cada naipe apareceram. No final basta subtrair esse número a 13 e escrever o resultado, se nenhum erro for encontrado. Esta parte demoria portanto O(S), pois corresponde a simplesmente passar uma vez pela string dada.
Para saber se existe um erro, bastaria usar dois ciclos for na string lida para saber se existem duas posições i e j tal que a carta da posição i é igual à carta da posição j. Esta parte implementada desta maneira demoraria O(S2), mas passaria na mesma no tempo, pois o limite do tamanho de S é apenas 1000).
Uma maneira de fazer a verificação do erro em tempo O(S) seria por exemplo usar um array booleano bidimensional para guardar se um certo valor de um certo naipe já apareceu no baralho. Para detalhes desta implementação podem espreitar a solução oficial.
Skills necessários: arrays
Não faz sentido agrupar os livros em grupos de menos do que 3 livros, porque o desconto só existe para um grupo de 3 livros (recordando que o desconto é receber o mais barato dos 3 livros passar a ser grátis). Isto significa que temos de agrupar todos os livros em grupos de 3, de tal modo que apenas exista no máximo um grupo que não tenha 3 livros (no caso do número de livros não ser um múltiplo de 3).
Para decidir como agrupar, comecemos primeiro por descobrir os dois livros mais caros. Como não existe nenhum livro mais aro que estes, nunca conseguiremos tê-los grátis, mas podemos colocar o terceiro mais caro nesse grupo dos dois mais caros, e desse modo ter esse terceiro mais caro grátis (e nenhuma outra hipótese conseguiria um desconto melhor).
Com o processo anterior reduzimos o número de livros que temos ainda de agrupar em três livros a menos. Podemos depois repetir exatamente o mesmo processo com os livros restantes, e repetir até ficarmos no final com menos que 3 livros (sendo que se forem 1 ou 2 sobrantes, não podemos colocá-los em nenhum grupo.
Podemos dizer que estamos a usar uma estratégia greedy, que em cada passo faz a melhor escolha local (pegar nos 3 mais caros), sendo que no final isso leva à melhor escolha global.
Para obter os mais caros podemos por exemplo ordenar por ordem decrescente. e depois simplesmente percorrer por essa ordem. Os algoritmos de ordenação típicos de uma linguagem de programação têm complexidade O(N log N) (ex: sort em C++ ou Arrays.sort em Java). Esta parte da ordenação irá dominar o tempo de execução do algoritmo, pois depois percorrer o array irá ter tempo de execução linear, ou seja, O(N). Note-se que como N<2000 para este problemas, até um algoritmo de ordenação menos eficiente seria suficiente (ex: InsertionSort ou SelectionSort em O(N2)).
Skills necessários: ordenação, greedy
Existem várias estratégias possíveis para rebentar os balões.Aqui vamos só mencionar a que está implementada na solução oficial.
A estratégia óptima é: escolher o primeiro balão a partir da esquerda que ainda não foi rebentado e disparar uma seta com a sua altura. Vamos tentar agora provar a correção desta estratégia.
O balão mais à esquerda de todos tem de ser atingido por pelo menos uma seta que comece à sua altura. A única questão é perceber se por vezes seria melhor começar por rebentar um balão mais alto e mais à direita, e só depois rebentar este balão. Vejams que existem dois casos:
Podemos dizer que estamos a usar uma estratégia greedy, que em cada passo faz a melhor escolha local (escolher o mais à esquerda ainda não rebentado), sendo que no final isso leva à melhor escolha global.
O algoritmo descrito pode ser implementado usando um set (c++) ou um TreeSet (Java), por exemplo (ver artigo do loop sobre implementações de estruturas de dados). A questão a que o set tem de responder é "Qual é o primeiro balão ainda não rebentado, que está na altura H-1 e está localizado à direita de uma posição P?"
Temos de criar H sets, uma para cada altura entre 1 e H, armazenando as posições dos balões a cada uma das alturas.
Com perguntas simples ao set e retirando as posições dos balões que forem sendo rebentados, podemos ir mantendo a estrutura de dados sempre pronta para as perguntas futuras (vejam as soluções).
A complexidade temporal de todo este processo é O(N log N), pois cada uma das operações básicas no set gasta tempo logarítmico, ou seja O(log n).
Notem que seria possível resolver o problema em O(N) e deixamos essa solução como um desafio adicional para o leitor (dica: "disparar" todas as setas ao mesmo tempo.
Skills necessários: árvores binárias de pesquisa (set), greedy
Seja Ri o total XOR de todas as torres localizadas na linha i. Analogamente, seja Ci o total XOR das torres localizadas na coluna i. Notem que o número de posições atacadas é igual ao número de pares (i,j) tal que Ri ≠ Ci (isto é uma consequência directa do facto da posição (i,j) ser atacada se e só se o total XOR na linha i for diferente do total XOR na coluna j).
No início, podemos calcular para cada k quantas linhas i existem tal que Ri=k, e quantas colunas j existem tal que Cj=k. É fácil calcular o número de posições atacadas com esta informação.
Quando um movimento ocorre, precisamos de eficientemente calcular a mudanças no número de posições atacadas. Quando uma torre se move a partir da posição (y,x), calculamos o número de posições atacadas na linha l ou na coluna c, e subtraimos ao total de posições atacadas. Quando uma torre se move para a posição (y,x), calculamos o número de posições atacadas na linha l ou na coluna c, e adicionamos ao total de posições atacadas.
Se usarmos uma árvore binária (ex: map (c++) ou um TreeMap (Java) para armazenar os dados, a complexidade temporal total do algoritmo fica O(M log N).
Skills necessários: árvores binárias de pesquisa (map), combinatória
Vamos resolver primeiro o caso de não existirem mudanças no requisitos, asumindo então número constante pedido de ai pinturas a cores e bi pinturas a preto e branco. Precisamos de determinar de quantas maneiras podemos escolher diferentes configurações de venda de pinturas tal que pelo menos C pinturas sejam coloridas. Vamos usar programação dinâmica. Seja dpi j o número de maneiras de escolher as primeiras transações tal que exatamente j delas sejam satisfeitas com pinturas coloridas. A relação usada pode ser a seguinte:
dpij = dpi-1 j * bi + dpi-1 j-1 * ai
No final, a solução é a soma dos valores dpn i para i ≥ C. O cálculo pode ser ainda mais simplificado se definirmos dpi k como sendo não a maneira de ter exacamente k pinturas coloridas, mas pelo menos k pinturas coloridas. Calcular esta relação uma vez tem custo temporal O(N*C). A solução que passa por calcular esta relação de cada vez que os requisitos mudam tem por isso complexidade O(Q*N*C) e daria para obter 30% dos pontos.
Para conseguir os 100 pontos é necessária uma maneira eficiente para manter os valores desta relação depois das mudanças nos requisitos serem feitas. Podems usar por exemplo uma árvore de segmentos. Cada nó da árvore será usado para representar o número de maneiras do intervalo representado por essa sub-árvore, de 0 até k.
Resta-nos manter a relação de cada vez que mudamos os requisitos para uma pessoa. É evidente que é relativamente simples calcular a mudança de cada nó. A questão é como juntar dois nós, ou seja como faze o merge da árvore de segmentos.
Seja T um nó da árvore de segmentos e Ts o número de maneiras, para o seu intervalo, de obter pelo menos s pinturas coloridas. Sejam também L e R os seus nós filhos esquerdo e direito. Então:
Ts = ∑ Li * Rs-i, para cada i ≤ s
A complexidade temporal final fica O( (N+Q) log N * C2).
Skills necessários: árvore de segmentos, programação dinâmica
Seja Sx o conjunto de todos os possíveis intervalos de piadas que existiriam na festa se observarmos a pessoa x e todos os seus diretos e indiretos subordinados (a subárvore que começa na pessoa x).
Vamos assumir que para a pessoa x já calculamos os valores dos conjuntos S para todos os subordinados directos da pessoa. Então, podemos calcular Sx usando programaçõa dinâmica.
Seja Qi o conjunto de todos os lados direitos do intervalo de piadas que pode ser ouvido na subárvore da pessoa x e cujo lado esquerdo do intervalo é igual a l. Iteramos por ordem decrescente sobre todos os possíveis lados esquerdos l e para cada l iteramos sobre todos os possíveis lados direitos r tal que exista um nó filho de x que tem o intervalo [l,r] no seu conjunto, e usamos a seguinte relação:
Ql = Ql ∪ Qr+1
Um caso especial acontece quando l = vx, o que significa simplesmente que:
Ql = {vx} ∪ Ql+1
A complexidade temporal deste algoritmo é O(N*K3), onde K é o número de diferentes piadas que existem.
A solução oficial usa um bitset como estrutura de dados, de maneira a acelerar o cálculo da operação de união (vejam a solução para os detalhes da implementação)
Skills necessários: dfs, programação dinâmica, bitset