Resultado e Editorial da Quarta e Última Etapa da Liga de Programação 2020
Fala galera,
Concluímos nossa liga de programação com a conclusão da nossa quarta e última etapa. Essa etapa foi a melhor etapa que tivemos até agora, não tivemos nenhum problema técnico e a equipe responsável pela liga fez um trabalho fantástico como sempre.
Por isso agradeço do fundo do coração ❤️ a todos eles haha
- Cristhian Bonilha
- Diego Rangel
- Francisco E. P. Arcos Filho
- Gustavo Policarpo
- Sisterolli
- Vitor Hugo
- Thalyson Nepomuceno (revisão dos exercícios)
O Cristhian, líder da equipe de organização da Liga do Neps e Engenheiro de Software na Google, relatou a experiência de organizar as 4 etapas da liga no seu Blog pessoal, vale a pena dar uma conferida.
Classificação Final
Depois de 4 etapas e vários exercícios nós temos nossos campeões. Eu gostaria de parabenizar os melhores programadores do Brasil 😄.
- Lúcio Cardoso (Campeão Geral 😎)
- Paulo Miranda (Code Marathon)
- Leonardo Blanger
- Tiago Figueiredo
- Lucas Turci
A classificação completa já está disponível na página da Classificação da Liga de Programação.
Quarta Etapa
A classificação da quarta e última etapa da Liga de Programação 2020 pode ser encontrada no link.
Como sempre, os organizadores prepararam uma explicação para cada exercício da prova.
Para resolver o exercício, precisávamos calcular qual era o valor total da habilidade antes e depois. Se cada projétil causa uma determinada quantidade de dano, só é preciso multiplicar esse dano pelo número de projéteis disparados e temos o dano total. Assim, com o dano da habilidade original e depois das mudanças calculados, se depois das mudanças a habilidade dá mais dano, então ela sofreu um “BUFF”, caso contrário ela sofreu um “NERF”.
Este é um exercício simples de manipulação de string. Basta conhecer o método correto de contar quantos caracteres uma string tem (strlen em C, string.size() em C++, string.length() em Java, etc). Por fim, basta imprimir o primeiro caractere, seguido do tamanho da string subtraído de 2, e o último caractere.
Nosso objetivo nesse problema é crescer ao máximo possível o conhecimento de todos os alunos, juntando os que tem mais conhecimento com os que tem menos.
Então, o primeiro passo é ordenarmos o vetor para termos uma base de quem tem mais conhecimento que quem.
Imagine esse vetor de exemplo, com :
Se eu juntar o e o em um time, estarei aumentando a habilidade de um aluno em e a habilidade de outro aluno em . Se eu juntar o e o estarei aumentando a habilidade de um aluno em e o outro em .
Então fica claro que .
Seguindo essa estratégia, aumentaremos a habilidade da escola de maneira ótima.
Existem arrendondado para baixo times de tamanho . Então vou pegar os alunos com mais conhecimento e adicionar na minha resposta já que ele representará um time.
E por fim, existe um time com tamanho (resto da divisão de por ), então pegarei mais um aluno além dos demais e multiplicar seu conhecimento por .
Esse exercício foi dividido em três subtasks com restrições diferentes. Para cada uma delas, existe no mínimo uma solução que seria aceita.
Subtask 1:
Como haveria exatamente uma rotação, bastava simular o resultado dessa rotação e imprimir a resposta.
Vamos descrever o processo de simulação de rotação: Note que todos os itens que estavam na primeira linha, após rotacionarem, cairão na primeira coluna. De maneira semelhante, todos os itens que estavam na segunda linha cairão na segunda coluna, e por aí vai. Logo, para descobrir quantos itens cairão na coluna (para todo ), basta contar quantas colunas tem x ou mais itens.
Subtask 2:
Na segunda subtask podem haver mais rotações. Não muito diferente da subtask 1, basta simular as rotações. A maior diferença é que, caso e sejam diferentes, será necessário tratar as rotações ímpares de forma diferente das rotações pares, pois a quantidade de linhas e colunas invertem a cada rotação.
Subtask 3:
Na terceira subtask a quantidade de rotações sobe bastante. Simular rotações se torna impraticável (dado o tempo limite do problema).
A solução está escondida no fato de que, a partir de uma rotação , a cada rotações os itens voltam à mesma posição que estavam à rotações atrás. O desafio está em encontrar os valores e . Após isso, basta tirar o módulo de em , e simular apenas um número baixo de rotações.
Neste exercício, podemos notar que ciclos de tamanho até no máximo 3 podem ser removidos do grafo.
Ciclos de tamanho 4 ou mais, por outro lado, não podem ser removidos, pois podemos eliminar apenas 3 inimigos por turno. Se o ciclo tem tamanho, digamos, 5, então não importa quais 3 inimigos sejam nocauteados, sempre sobrarão 2 inimigos para soar o alarme. A mesma lógica vale para todo ciclo de tamanho 4 ou mais.
De maneira semelhante, se um inimigo não necessariamente faz parte de um ciclo de tamanho 4 ou mais, porém está sendo vigiado por um inimigo que faz parte de um ciclo de tamanho 4 ou mais, então o inimigo nunca poderá ser eliminado, pois isso iria requerer que todos os inimigos do ciclo de tamanho 4 ou mais fossem eliminado em algum turno anterior, porém já notamos que isto é impossível.
Feitas estas observações, podemos reduzir o grafo original a um grafo de componentes conexos, usando, por exemplo, o algoritmo de Tarjan. É importante saber, para cada vértice que representa um componente, quantos vértices do grafo original o compõem. Com isso temos em mão um DAG (grafo direto acíclico). Agora podemos fazer várias buscas em profundidade começando pelas folhas, e marcando os vértices como “removidos” caso eles representem um componente de tamanho 3 ou menos. Caso contrário, a busca não deve continuar.
Podemos utilizar uma tripla para representar que o intervalo de até está colorido com a cor . Note que cada vez que utilizamos a operação do tipo 1 serão criadas no máximo 2 novas triplas. Assim, podemos utilizar um std::set para a manutenção dos intervalos em tempo , onde é o tamanho do set.
Para as operações do tipo 2 e 3 podemos utilizar alguma estrutura de dados que responde a frequência em tempo como um std::set, std::priority_queue ou uma segtree.
A primeira coisa a ser observada é que a operação de fusão de códigos genéticos é equivalente ao operador bitwise xor presente na maioria das linguagens de programação. Feito isso, podemos reformular o problema como: Construir repetidamente um array de tamanho a partir de um array de tamanho , onde os valores no novo array são o xor de posições adjacentes no array anterior. Determinar o valor que estará no array de tamanho 1.
Outra coisa a ser observada é que nem toda célula contribui para a resposta, isso porque toda vez que um valor inicial parece um número par de vezes dentro do xor de uma célula, pelas propriedades xor e xor , ele se cancela. Ele só pode reaparecer novamente em um array de tamanho menor, se ainda existirem outras células no array atual onde ele ainda não tenha se cancelado.
Se de fato, em vez de fazermos o xor para criar os novos arrays, fizéssemos a soma das posições adjacentes, poderíamos nos concentrar somente na paridade dos coeficientes em vez de nos próprios valores dele. Isso porque se um número aparece uma quantidade par de vezes em um xor, ele se cancela, caso contrário é o mesmo que ele aparecer somente uma vez.
Vamos simular esse processo de combinação com soma para 6 elementos iniciais por exemplo. Sejam eles , , , , e . Teremos:
, , , , ,
É possível notar e provar que os coeficientes ao lado do i-ésimo número da entrada no valor final é , ou seja, combinação de tomados a . Mas como só nos interessa saber se esse valor é impar ou par, podemos nos usar do teorema de lucas que diz que é ímpar se (n-1) & (i-1) == (i-1). Onde & é o and bitwise.
Em resumo, considerando o array 1-indexado, a resposta será o xor de todos os valores onde (n-1)&(i-1)==(i-1). A não ser que para algum destes , nesse caso a resposta é -1.
Complexidade O(N)
Por fim, gostaria de parabenizar todo mundo que participou da nossa quarta etapa, espero que vocês tenham tido uma experiência bacana. Aproveitando a oportunidade, peço para que cada um de vocês deixem nos comentários abaixo como foi sua experiência pessoal, tantos comentários positivos como negativos são super bem vindos.
Pra finalizar vamos parabenizar quem ficou no topo da classificação ao final das 3 horas.
- Tiago Figueiredo (Campeão 😎)
- Leonardo Blanger
- Lucas Turci
- Paulo Miranda (Code Marathon)
- Lúcio Cardoso
- Leonardo Paes
- lclpsoz
- Gabriel Candeia
- Luca Dantas
- Rafael Nascimento
Bons estudos para todos e aproveitem as dicas acima para resolver os exercícios que não deu para resolver durante a prova aqui no Neps. Eu criei uma lista com os exercícios para vocês, só cair em campo agora hahaha.
Até próximo ano!
Comentários