Resultado e Editorial da Quarta e Última Etapa da Liga de Programação 2020

Programação Competitiva

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

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 😄.

  1. Lúcio Cardoso (Campeão Geral 😎)
  2. Paulo Miranda (Code Marathon)
  3. Leonardo Blanger
  4. Tiago Figueiredo
  5. 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.

A - Buff ou Nerf

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”.

B - i18n

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.

C - Human Learning

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 K=3K = 3:

1,3,4,6,101, 3, 4, 6, 10

Se eu juntar o 10,110, 1 e o 33 em um time, estarei aumentando a habilidade de um aluno em 99 e a habilidade de outro aluno em 77. Se eu juntar o 10,610, 6 e o 44 estarei aumentando a habilidade de um aluno em 44 e o outro em 66.

Então fica claro que 9+7>6+49 + 7 > 6 + 4.

Seguindo essa estratégia, aumentaremos a habilidade da escola de maneira ótima.

Existem N/KN/K arrendondado para baixo times de tamanho KK. Então vou pegar os N/KN/K alunos com mais conhecimento e adicionar na minha resposta Kv[i]K * v[i] já que ele representará um time.

E por fim, existe um time com tamanho NN%K (resto da divisão de NN por KK), então pegarei mais um aluno além dos demais e multiplicar seu conhecimento por NN % K.

D - Rotacionando na Colina

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: R=1R = 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 xx (para todo 1xM1 \leq x \leq M), basta contar quantas colunas tem x ou mais itens.

Subtask 2: R100R \leq 100

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 NN e MM 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: R109R \leq 10^9

Na terceira subtask a quantidade de rotações sobe bastante. Simular 10910^9 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 KK, a cada PP rotações os itens voltam à mesma posição que estavam à PP rotações atrás. O desafio está em encontrar os valores KK e PP. Após isso, basta tirar o módulo de RR em PP, e simular apenas um número baixo de rotações.

E - Desperados

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 XX 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 XX 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.

F - Faltou uma Historinha

Podemos utilizar uma tripla <L,R,X><L, R, X> para representar que o intervalo de LL até RR está colorido com a cor XX. 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 O(log2k)O(log_2 k), onde kk é 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 O(log2k)O(log_2 k) como um std::set, std::priority_queue ou uma segtree.

G - Combinação Genética

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 N1N-1 a partir de um array de tamanho NN, 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 XX xor X=0X = 0 e YY xor 0=Y0 = Y, 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 AA, BB, CC, DD, e EE. Teremos:
AA, BB, CC, DD, EE, FF
A+B,B+C,C+D,D+E,E+FA+B, B+C, C+D, D+E, E+F
A+2B+C,B+2C+D,C+2D+E,D+2E+FA+2B+C, B+2C+D, C+2D+E, D+2E+F
A+3B+3C+D,B+3C+3D+E,C+3D+3E+FA+3B+3C+D, B+3C+3D+E, C+3D+3E+F
A+4B+6C+4D+E,B+4C+6D+4E+FA+4B+6C+4D+E, B+4C+6D+4E+F
A+5B+10C+10D+5E+FA+5B+10C+10D+5E+F

É possível notar e provar que os coeficientes ao lado do i-ésimo número da entrada no valor final é C(n1,i1)C(n-1, i-1), ou seja, combinação de N1N-1 tomados a i1i-1. Mas como só nos interessa saber se esse valor é impar ou par, podemos nos usar do teorema de lucas que diz que C(n1,i1)C(n-1, i-1) é í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 c[i]c[i] onde (n-1)&(i-1)==(i-1). A não ser que para algum destes c[i]=1c[i]=-1, 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.

  1. Tiago Figueiredo (Campeão 😎)
  2. Leonardo Blanger
  3. Lucas Turci
  4. Paulo Miranda (Code Marathon)
  5. Lúcio Cardoso
  6. Leonardo Paes
  7. lclpsoz
  8. Gabriel Candeia
  9. Luca Dantas
  10. 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