Matrizes - OBI 2010 e Bitmap - Spoj

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 é 10⁵ e o valor máximo de cada célula é 10⁴. Ou seja, cada matriz tem 10⁵ x 10⁵ 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 10⁵ x 10⁴ x 10⁴ é maior do que 2³¹.

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

Aeroporto - OBI 2002

Olá a todos, o post da vez será com comentários sobre o problema Aeroporto, que é da OBI 2002 e está disponível no SpojBR (link).

O problema pede o aeroporto mais congestionado dentre todos os A existentes. O congestionamento de um aeroporto é definido como a soma do número de vôos que chegam mais o número de vôos que saem dele.

Para a resolução do exercício então basta manter um vetor para cada aeroporto com o número de vôos que ele tem. Para cada vôo os contadores do aeroporto de partida e de destino são incrementados. Ao final basta ver qual o maior número de vôos que um aeroporto tem em uma passada pelo vetor e posteriormente percorrer o vetor imprimindo todos aeroportos com o mesmo número de vôos que o máximo.

Código do Andrei para o problema: http://codepad.org/8cPuTEnU