E para finalizar os comentários sobre os problemas selecionados para a primeira lista de treinos para OBI, vou falar em um mesmo post do problema Matrizes, da OBI 2010 e disponível no SpojBR (link) e do problema Bitmap, do Spoj (link).
Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.
Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.
Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.
Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.
Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.
Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv
No comments:
Post a Comment