Lista de Problemas:
- Ring Road 2: http://codeforces.com/problemset/problem/27/D
- King's Path: http://codeforces.com/problemset/problem/242/C
- Marble Game: https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=1808
- Olympiad: http://codeforces.com/problemset/problem/222/D
- Shifts: http://www.codeforces.com/problemset/problem/229/A
- Lucky String: http://codeforces.com/problemset/problem/110/B
- Colorful Graph: http://codeforces.com/problemset/problem/246/D
- Physics Practical: http://codeforces.com/problemset/problem/253/B
- Labirinto: http://br.spoj.com/problems/LAB07/
Link para simulado: http://ahmed-aly.com/Contest.jsp?ID=7426
Ring Road 2
2-SAT, não? Só me parece chato calcular o que não pode com o que, mas acho que o outline é esse
Seja a aresta (u_i, v_i), definimos x_i = {true se aresta (u_i, v_i) está por dentro, false c.c.} e ~x_i a negação de x_i.
x_i ser verdadeiro implica que todas o x_j de todas as arestas que cruzam (u_i, v_i) devem ser falsos. Isto é, x_i -> ~x_j. Podemos então construir o implication graph. Para resolver basta garantir que x_i e ~x_i não fazem parte da mesma componente fortemente conexa, para qualquer i.
King's Path
Frase essencial do enunciado "It is guaranteed that the total length of all given segments doesn't exceed 10^5".
Usar map do C++. m[i][j] = 1 se a célula é válida. Não coloca no map pares (i, j) onde a célula não seja válida.
Usando esse map pode fazer uma BFS andando pelas células pois tem no máximo 10^5 delas.
Montar o map custa O(N*logN) e fazer a BFS O(N).
Marble Game
BFS complexa - encodar o tabuleiro com bits (tem pedra vs. não tem pedra). Parece complicado de codar, mas a ideia é bem clara.
Olympiad
Observação 1: sempre tem um jeito do cara conseguir primeiro
Partindo desse princípio, o problema se torna “de quantos jeitos você consegue somar a[i] e b[j] de forma que o resultado seja >= x”
Se você ordenar as duas listas, você tem um jeito de fazer isso O(n), que é mais que suficiente aqui - na primeira lista o ponteiro começa no primeiro elemento e na segunda, no último – volte na segunda lista até que o resultado não seja >= x, e some o número de elementos até o final. Daí, mantenha posição na segunda lista e avance o ponteiro da primeira.
Shifts
Solução 1: Calcula soma(i, j) = somatório da i-ésima linha até a coluna j.
Para cada coluna j
Para cada linha i
Faz busca binária em soma(i, 1...m) para achar o 1 mais próximo da coluna j
Custa O(M*N*log(M))
Solução 2:
Calcula umEsquerda(i, j) = posição do um mais próximo a esquerda da coluna j na linha i (pode ser zero se mat(i, j) = 1)
umDireita(i, j) = posição do um mais próximo a direita da coluna j na linha i (pode ser zero se mat(i, j) = 1)
Para cada coluna j
Para cada linha i
Escolhe min{umEsquerda(i, j), umDireita(i, j)}
Custa O(M*N)
Lucky String
Melhor string vai ser sempre repetir "abcd".
A string gerada sempre vai ser lucky pois as letras repetidas estão a uma distância 4.
É a menor lexicograficamente pois trocar uma letra por outra maior obviamente não faz sentido. E trocar por uma menor cria uma string não lucky.
Colorful Graph
Cria um grafo onde os nós são as cores e aresta (u, v) existe se existe um nó da cor u ligado a um nó da cor v no grafo original.
Resposta é o nó com maior grau no grafo de cores.
Physics Practical
Solução 1:
Note que os números estão no intervalo [1, 5000]
Cria o vetor v[i] = número de vezes que o número i aparece
pMaior = maior i tal que v[i] != 0
pMenor = maior i tal que v[i] != 0 AND pMaior <= 2*i
while pMaior >= pMenor
Computa quantos precisou jogar fora.
Decrementa pMaior até achar v[pMaior] != 0
Decrementa pMenor até achar um valor que satisfaça pMaior <= 2*pMenor.
Note que o valor de pMaior e pMenor sempre decresce e como o valor máximo que eles assumem é 5000.
A complexidade total é O(maior c_i), no caso do problema maior c_i = 5000.
Solução 2: Usar a mesma ideia da Solução 1 porém num vetor ordenado de todas as medidas.
Precisa ter mais atenção pois temos medidas repetidas.
Como precisamos ordenar e depois percorrer o vetor de medidas a solução custa O(N*logN + N) = O(N*logN), onde N = 10^5.
Labirinto
Camadas de grafo, sendo que a última liga com a primeira - BFS
Outra forma de fazer: Imagine um grafo onde custo(u, v) é quanto custa sair de u e chegar até v em um pulo (pode custar até 9 pois pode ser necessário esperar).
Comece o Dijkstra pelo nó inicial e calcule custo(inicial, v), vc vai escolher o v com menor custo.
Agora deve atualizar o vetor de distância do Dijkstra considerando que pode sair de v no instante que acabou de calcular.
Isso vai gerar novos custo(v, u) e vai atualizar o vetor de direção utilizando esse custo(v, u).
Note que custo(a, b) saindo no instante x pode ser diferente de custo(a, b) saindo num instante y, porém isso não atrapalha no Dijkstra pois a invariante de “selecionar o i-ésimo nó mais próximo na iteração i” é mantida.
