XIV Maratona Algar Telecom – Editorial (incompleto)

Neste dia 30 de agosto aconteceu a décima quarta edição da Maratona Algar Telecom, que aconteceu tanto presencialmente, em Uberlândia, quanto online, no portal do URI Online Judge.

Nesta edição eu colaborei com três exercícios inéditos.

Abaixo segue um editorial escrito sobre os meus exercícios. Clique no link abaixo para vê-lo.

Lâmpadas – [uri]

Para cada valor K e N, é possível encontrar um valor C, de tal modo que após C operações o estado das lâmpadas volta a ser o original. Logo, fazer C, C*2, C*3, etc, sempre mantém o estado original das lâmpadas.

Com isso em mente, é possível diminuir consideravelmente o número de operações a ser realizada por M%C, e aplicá-las com força-bruta.

Labirinto – [uri]

É possível visualizar o labirinto como um grafo, sendo cada posição um vértice, e adicionando uma aresta entre cada duas posições adjacentes. Na teoria dos grafos, este problema pode ser classificado como “encontre o diâmetro do grafo”.

Para facilitar, o seguinte trecho do enunciado “só há um caminho entre quaisquer dois espaços vazios” nos garante que este grafo é uma árvore. Esta propriedade nos permite diminuir a complexidade do algoritmo para diâmetro de um grafo genérico (N^3) para o de uma árvore (N), onde N é o número de vértices do grafo.

Segue uma descrição em alto nível do algoritmo: Escolha um vértice qualquer da árvore, e chame-o de A. Encontre o vértice que está o mais distante possível do vértice A, e chame-o de B. Agora encontre o vértice que está o mais distante possível do vértice B, e chame-o de C. O diâmetro desta árvore é a distância entre os vértices B e C.

Os detalhes de implementação eu vou ficar devendo. Vale a dica de que é possível resolver isso com duas buscas em profundidade ou em largura.

Baile de Formatura – [uri]

Este exercício pode ser resolvido com programação dinâmica. Seja dp[b][g] um estado, onde ainda devem ser distribuídos b garotos para dançarem com g garotas.

Seguindo a lógica do enunciado, podemos recorrer ao estado dp[b-1][g], assumindo que um garoto dançou com uma das garotas que já havia dançado com alguém; e ao estado dp[b-1][g-1], assumindo que um garoto dançou com uma garota que ainda nao havia dançado com ninguém. Logo:

dp[b][g] = dp[b-1][g] * (total_garotas - g) +
           dp[b-1][g-1] * g

 

Qualquer dúvida, comentário ou sugestão são bem-vindos. Basta escrever um comentário abaixo 😉

2 ideias sobre “XIV Maratona Algar Telecom – Editorial (incompleto)”

  1. Vc não explicou a solução do baile de formatura direito …. Por favor análise novamente !!!!!!!!!! Desde já agradeço 😉

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *