EditorialSeletiva2013

De DCC UFMG - Maratona de Programação
Edição feita às 11h28min de 25 de outubro de 2013 por Lucas (disc | contribs)

(dif) ← Edição anterior | ver versão atual (dif) | Versão posterior → (dif)
Ir para: navegação, pesquisa

Conteúdo

Problema A: Persistência

WriteMe!

Problema B: Metrô

Queremos encontrar um caminho entre duas estações tal que minimize o seu custo. O custo de um caminho é dado pelo número de trocas entre linhas para chegar nas estações.

Seja um grafo $G(V, E)$ em que cada linha $L$ e cada estação $S$ é um nó neste grafo. Existe uma aresta entre $l_i$ e $s_j$ de custo 0 e uma outra aresta $s_j$ a $l_i$ de custo 1 para toda linha que pertença a uma estação. Dessa forma, toda vez que saimos de uma estação por uma linha, contamos o custo de uma troca. Note que isto não é válido na primeira vez que pega-se uma linha, já que não foi feita troca alguma. Logo a resposta é o menor caminho entre estações $s_i$ e $s_j$ no grafo $G$ subtraído de uma unidade.

Como o número de consultas é pequeno, basta para cada consulta, executar um algoritmo de caminho mínimo (Dijkstra por exemplo). Uma outra forma é usar o floyd-warshall (menor caminho entre todos os pares de vértices) e responder cada consulta em $O(1)$.

Problema C: Trending Topics

WriteMe!

Problema D: CraftMine

WriteMe! (Vinícius)

Problema E: Substrings

WriteMe! (Dilson)

Problema F: Reconstrução da Wolônia

WriteMe! (Luiz)

Problema G: Vampiros Primos

Primeiramente, como $n \leq 10^{10}$, os vampiros do problema podem ter até 10 dígitos ($10^{10}$ tem 11 dígitos, mas um número vampiro só pode ter um número par de dígitos).

Assim, as presas são permutações de dois primos menores que $10^5$. note. Você pode determinar eficientemente (até mesmo em tempo linear, com algumas otimizações) se todos os números até $10^5$ são primos ou não usando o Crivo de Eratóstenes.

Resta determinar, dado um número $n$ até $10^{10}$, se ele é um vampiro primo ou não. Seja $2d$ o número de dígitos decimais de $n$, $a$ os $d$ dígitos mais significativos de $n$ e $b$ os $d$ dígitos menos significativos de $n$. Se $n$ é um vampiro primo, então existe uma permutação $p$ de $a$ que é um número primo, que divide $n$ sem deixar resto e tal que $\frac{n}{p}$ é primo e é uma permutação de $b$. O contrário obviamente também é verdadeiro.

Assim, basta iterar por todas as $d!$ permutações de $a$ e realizar o teste: a permutação $p$ deve ser um número primo, deve dividir $n$ e $x = \frac{n}{a}$ deve ser primo e ser uma permutação de $b$. Os testes de primalidade são feitos em $O(1)$ usando o resultado do Crivo. Para testar se $x$ é uma permutação de $b$, basta verificar se $x$ tem todos os dígitos de $b$ na mesma quantidade, com exceção possível dos zeros (já que $x$ pode ter menos dígitos que $b$, e nesse caso teria zeros à esquerda para completar $d$ dígitos. Por exemplo, consideramos que 13 é uma permutação de 130, já que 013 é uma permutação de 130 e é equivalente, em decimal, a 13). Isto pode ser feito em tempo linear.

A complexidade desta solução, então, é:

  • Pré-processamento: Crivo em $O(n \log \log n)$, para n = 10^5.
  • Consultas: $O(d! \times d)$, para um número com $2d$ dígitos. Se o número de dígitos é ímpar, a resposta é sempre "N".

Como $d \leq 5$, esta solução é suficientemente eficiente.

Problema H: Usinas Nucleares

WriteMe! (Henrique)

Problema I: Vai Dar Namoro

WriteMe! (Henrique)

Problema J: 31-TOR mE atsE odaicnunE O

WriteMe! (Henrique)

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas