analysis070614

Link para o contest: Contest

P1 - Dengue

http://br.spoj.com/problems/DENGUE/

Calcular a distância de todos os pontos para todos outros. Pode fazer N vezes a BFS ou um Floyd-Warshall.

P2 - Macaco-prego

http://br.spoj.com/problems/MACACO/

Encontrar interseção de N retângulos de lados paralelos aos eixos x e y. As interseções entre dois retângulos desse tipo, geram um outro retângulo desse tipo.
Precisa algum cuidado para cuidar de todos os casos de posicionamento entre dois retângulos

P3 - Palíndrome

http://br.spoj.com/problems/PAL/
Seja w a palavra do input.

Solução 1

Vamos utilizar programação dinâmica:
Seja $S(i, j) =$ número de divisões que precisamos fazer na substring (i, j).
Caso base: $S(i, j) = 0$, se substring (i, j) é uma palíndrome
Passo Indutivo: $S(i, j) = max\{S(i, k) + S(k+1, j) + 1\}$, onde $i \leq k < j$.

Essa solução executa em $O(N^3)$, onde N é o tamanho da palavra w. Como N vale 2000, essa solução não passa no timelimit!

Solução 2

Seja $Pal(i, j) =$ vale true se a substring (i, j) da palavra w é uma palíndrome e false caso contrário. Podemos calcular isso com a seguinte programação dinâmica:
Casos Base:

  • Pal(i, j) = true, Se i = j
  • Pal(i, j) = true, Se i = j-1 E w[i] = w[j]

Passo Indutivo:

  • Pal(i, j) = Pal(i+1, j-1), Se w[i] = w[j]
  • Pal(i, j) = false, caso contrário

Vamos criar um grafo com N+1 nós, onde N é o tamanho da palavra. Os nós são numerados $\{0, 1, \dots , N-1, N\}$, onde o nó N é um nó terminal.
A aresta (i, j) no grafo existe se e somente se existe a substring (i, j-1) é uma palíndrome.

Desejamos então descobrir o custo do menor caminho de 0 até N. Isso vai dizer por quantas palíndromes até chegar ao nó terminal.

Calcular a programação dinâmica Pal(i, j) custa $O(N^2)$. Gerar o grafo custa $O(N^2)$ e finalmente executar a BFS também $O(N^2)$.
Logo toda solução custa $O(N^2)$, o que passa no timelimit!

P4 - Macaco Rural

http://br.spoj.com/problems/MACACOMG/

Ordena as ofertas e casar a oferta 1 com a N, a 2 com a N-1, 3 com N-2, etc..
Uma intuição de que essa ideia funciona: Seja $(i, j)$ o par que tem a maior soma no casamento definido acima, trocar ele com o par $(k, w)$ onde $k < i$ e $j < w$ não gera uma soma menor. Esse novo casamento não gera um par menor pois apesar do par $(k, j)$ ser menor, o par $(i, w)$ é maior.

P5 - TV da Vovó

http://br.spoj.com/problems/TV/

Modificar toda a tela a cada correção gera um algoritmo $O(M*N*total de correções) = 10^9$, não passa no timelimit.
Se perceber que pode somar as correções, o algoritmo fica $O(M*N)$, que passa no timelimit.

P6 - Mini-Poker

http://br.spoj.com/problems/OBIPOKER/

Pura implementação de todas as regras. Trabalhoso.

P7 - João e o Pé de Feijão

http://br.spoj.com/problems/JOAOMG/

Para verificar se um número $n$ é de kaprekar pode testar todas as possibilidades de $m$. São poucas pois $n$ é até 41001.

P8 - Braceletes Mágicos

http://br.spoj.com/problems/BRACELMG/

Encontrar se uma substring está dentro de outra com o algoritmo ingênuo $O(N^2)$. Deve replicar a string do bracelete algumas vezes pois a string é circular.

P9 - Palavras Primas

http://br.spoj.com/problems/PAPRIMAS/

Somar as letras e verificar se um número é primo ou não.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License