XV Maratona Algar Telecom – Editorial (incompleto)

Neste dia 11 de abril aconteceu a décima quinta edição da Maratona Algar Telecom, sediada na cidade de Uberlândia.

Nesta edição eu colaborei com dois exercícios inéditos, e abaixo segue um editorial escrito sobre eles.

Clique no link abaixo para vê-lo.

Escada Rolante – [uri]

Temos aqui um problema de simulação: precisamos descobrir por quanto tempo a escada rolante ficou ativa.

Uma solução simples seria declarar um vetor de booleanos, onde cada posição deste vetor representaria um tempo t, entre 1 e 1010, inclusive. Tal vetor é inicializado como falso em todas as posições, e para cada pessoa que se aproxima da escada rolante no tempo t alteramos o valor das posições entre t e t+9, inclusive, como verdadeiro. Ao final, contamos quantas posições foram marcadas como verdadeiras, e imprimimos tal soma como resposta. Tal solução tem complexidade linear com constantes médias, mas passa no tempo limite do problema.

Uma solução mais elaborada seria se considerássemos dois tipos de situações que podem acontecer entre duas pessoas consecutivas que se aproximam da escada:

(1) a segunda pessoa chega após a primeira sair: somamos 10 ao resultado final, que foi o tempo em que a primeira pessoa utilizou a escada, e repetimos o processo para a próxima pessoa.

(2) a segunda pessoa chega enquanto a primeira ainda está na escada: somamos a diferença de tempo entre as duas pessoas ao resultado final, que foi o tempo em que a primeira pessoa esteve sozinha na escada, e repetimos o processo para a próxima pessoa.

Tal solução tem complexidade linear com constantes baixas, e passa no tempo limite do problema.

Ataque Programado – [uri]

Temos aqui um problema de grafos: dado um grafo direcionado, precisamos descobrir se é possível visitar todos os N vértices em alguma ordem, de tal modo que tal ordem atenda à duas condições:

(1) só é permitido visitar um vértice v se todos os vértices u que tem v como seus vizinhos já foram visitados.

(2) dado que você e cada vértice possuem um determinado número de soldados, só é possível visitar um vértice se o seu número de soldados for maior do que o do vértice em questão.

A primeira condição é relacionada a um problema clássico de grafos chamado Topological Sorting, porém ao invés de imprimirmos uma ordem válida nós precisamos apenas verificar se ela existe. Uma ordem válida existe se, e somente se, o grafo não contém nenhum ciclo.

A segunda condição é uma variação adicionada para tornar o problema mais difícil. É possível utilizar uma variação do algoritmo de Kahn (topological sorting) para resolver tal problema, que pode ser resumido como:

- Seja S um set de vértices candidatos a serem visitados. No início, S é composto dos vértices v tal que não existe nenhum vértice u com aresta em v. Repetimos então o seguinte processo:

- Remova de S o vértice com o menor número de soldados. Se o seu número de soldados é maior que o número de soldados de tal vértice a visita é válida. Caso contrário a visita é inválida, e o problema não tem solução válida.

- Se a visita for válida, adicione os soldados reféns ao seu grupo de soldados, remova tal vértice v do set S, e adicione no vértice S todos os vértices u vizinhos de v se, e somente se, v era o último vértice com aresta em u ainda não visitado.

Se todos os N vértices forem visitados, então a resposta é possível. Caso contrário é impossível. O processo acima pode ser implementado com uma fila de prioridade, e a complexidade da solução é igual a O(N * (lg N + M)).

 

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

Uma ideia sobre “XV Maratona Algar Telecom – Editorial (incompleto)”

  1. Uma solução força bruta para o segundo problema tem complexidade O(N^2 + M), Q é só começar com uma flag true e ficar procurando um vértice para capturar, caso n consiga capturar nem um, sai. Caso tenha capturado todos então é possivel, se não, não é possível.
    Não precisa nem de toposort xD

Deixe uma resposta

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