818. Aeroporto

Olá meus amigos nerds, depois de algumas decepções na última semana, nada melhor que afogar as mágoas resolvendo alguns problemas! E hoje eu trago um problema simples para vocês.

A crescente utilização do transporte aéreo preocupa os especialistas, que prevêem que o congestionamento em aeroportos poderá se tornar um grande problema no futuro. Pensando nisso, o problema 818. Aeroporto nos pede para determinar, a partir de uma listagem de aeroportos e vôos, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento o problema usa a soma do número de vôos que chegam e que partem de cada aeroporto. Mais especificamente, o problema pede o identificador do aeroporto que possui maior tráfego aéreo, onde o tráfego é medido pela soma do número de vôos que chegam e que partem do aeroporto.

Modelagem

A simples leitura do problema sugere uma modelagem por grafos. Podemos representar cada aeroporto por um vértice no nosso grafo, assim cada aresta representará um vôo de um aeroporto para outro. Nessa modelagem, o tráfego de cada aeroporto corresponde ao grau do vértice que representa aquele aeroporto. Assim, a resposta para nosso problema é o maior grau dos vértices de nosso grafo.

Computar o grau de cada vértice é bastante simples:

para cada aresta (v1->v2) do grafo

    grau_saída[v1]++

    grau_entrada[v2]++

Observe que o algoritmo acima funciona mesmo que o grafo tenha arestas paralelas (o que pode ser o caso em nosso problema).

Logo o tráfego em cada aeroporto A será:

trafego[A] = grau_saída[A] + grau_entrada[A]

Assim a resposta do problema será o maior elemento do vetor trafego.

Implementação

Dica Nerd - Algorithms: Design and Analysis, Part 2

Oi, hoje venho aqui dar uma dica para você que gosta de algoritmos. Segunda passada, começou (novamente) o curso de algoritmos 2 do coursera. Esse curso fala sobre algoritmos gulosos, programação dinâmica, grafos e problemas NP. É um curso muito interessante e vale muito a pena fazer. Experimente!

O Coursera, se você não sabe, é uma plataforma de educação online que oferece cursos de qualidade em várias áreas do conhecimento. 

2836. Moedas

Olá meus amigos nerds, essa semana meus parcos conhecimentos sobre programação dinâmica me permitiram chegar um pouco mais perto de um antigo objetivo meu. E para comemorar, nada melhor que apresentar um problema sobre esse tema!

Hoje vamos discutir o problema 2836. Moedas. Nesse problema, vamos ajudar o rei da Pinelândia a descobrir qual é o número mínimo de moedas que ele precisa juntar para ter um determinado valor. Mais especificamente, dados os valores das moedas disponíveis e um valor que se deseja somar, determinar o número mínimo de moedas que deve ser usado para somar o valor desejado, ou dizer que tal soma é impossível.

Modelagem

Este é um problema clássico de Programação Dinâmica, chamado de Change-making problem, ou Coin Change. Sendo assim não vou falar muito sobre ele.

Vamos começar pelos casos triviais:

Se queremos somar 0 tostões, precisamos de 0 moedas...

Se precisamos somar x tostões e temos uma moeda de x tostões precisamos de uma moeda...

Se precisamos somar x tostões e a moeda de menor valor é maior que x, então o problema é impossível...

Agora vem o truque.

Se precisamos somar y tostões usando uma única moeda de x tostões precisamos ser capazes de juntar moedas no valor de y-x tostões. Assim se formos capazes de determinar o número mínimo de moedas necessárias para juntar y-x tostões nosso problema fica resolvido.

Mais formalmente, sejam m o valor que queremos ajuntar e m1, m2,..,mm os valores das moedas disponíveis, temos:

minimoMoedas(0) = 0
minimoMoedas(m) = 1 se temos uma moeda de m tostões
minimoMoedas(m) = 1 + minimo [minimoMoedas(m-m1), minimoMoedas(m-m2), ...,minimoMoedas(m-mm)]

Basta agora fazermos uma programação dinâmica para calcular minimoMoedas e Voilá, problema resolvido.

Implementação

11753. Investindo no mercado de ações 1

Olá, desculpem-me meus amigos nerds mas essa semana não tive tempo de resolver nenhum problema junto com vocês (problemas mais desafiadores me atacaram). Mesmo assim, para não deixar passar em branco a semana mais divertida da copa (valeu Costa Rica e Chile), passei aqui para resolver mais um probleminha.

Investir no mercado de ações não é algo simples, normalmente exige tempo e atenção. Mesmo assim, nesse problema, vamos ter a oportunidade de ver como nosso amigo João investe de uma forma engraçada e peculiar. O problema 11753. Investindo no mercado de ações 1 nos pede para ajudar João a determinar em quantas partes ele deve dividir seu dinheiro para que ele obtenha um investimento mais seguro (pelo menos na opinião dele).

Modelagem

O problema nos pede para contar em quantas partes precisamos dividir N reais até que tenhamos apenas partes de no máximo k reais. Sendo que a divisão deve ser feita recursivamente em duas partes iguais a ⌊N/2⌋ e ⌈N/2⌉, até restar apenas partes de no máximo k reais.

Observe que, uma leitura atenta do problema já nos indica um algoritmo para resolvê-lo. Seja conta(N), o número de partes que devemos dividir N, assim temos nossa recursão:

conta(N) = conta(⌊N/2⌋) + conta(⌈N/2⌉) se N > k
conta(N) = 1                           se N <= k

Pronto, basta implementar essa recursão e o problema de João está resolvido. Sem graça, né? Então, vamos explorar um pouco mais esse problema? Vamos brincar de derivar a complexidade da nossa solução?

É possível achar uma fórmula fechada para essa recursão, entretanto fazer isso é complicado, pois teríamos que lidar com ⌊N/2⌋, o que não é simples. Observe, entretanto que a solução para um problema de tamanho N depende da solução de um problema de tamanho N/2, então a complexidade de nossa recursão é provavelmente logarítmica.

Para comprovar nossa hipótese de que o número de passos de nossa recursão é logarítmico, suponha que N seja uma potência de 2 (N=2^h), assim ⌊N/2⌋ e ⌈N/2⌉ serão iguais, logo temos:

conta(N)         = 2*conta(N/2) <=> conta(N/2^0) = 2*conta(N/2^1)
conta(N/2)       = 2*conta(N/4) <=> conta(N/2^1) = 2*conta(N/2^2)
...
conta(N/2^(h-1)) = 2*conta(N/2^h)

logo nossa recursão terá profundidade h. Mas h = log2(N). Assim a complexidade do nosso algoritmo é logarítmica. E como você já deve ter ouvido, em algum lugar, que algoritmos de complexidade logarítimica são eficientes vamos implementá-lo, então!

Implementação

O código abaixo, implementa nossa solução. Observe que ⌊N/2⌋ e ⌈N/2⌉ são simples de calcular (basta saber se N é par ou ímpar!).

1331. Dominó

Olá, hoje vamos comemorar a estreia do Brasil na copa resolvendo mais problemas de maratona! Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em sequência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo do problema 1331. Dominó é justamente esse: determinar se é possível formar uma sequência com todas as peças de dominó fornecidas.

Modelagem

Antes de resolver esse problema, irei fazer uma breve revisão sobre grafos. Falarei apenas do necessário para solucionar esse problema. Se você não sabe o que são grafos, eu sugiro fortemente que você estude um pouco sobre isso já que eles são uma ferramenta muito poderosa na resolução de problemas.

Em teoria de grafos, diz-se que um grafo possui um caminho euleriano se existe um caminho que visita cada aresta apenas uma vez. Com caso especial, um circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg.

Em um grafo euleriano G todos os vértices têm grau par.

Prova: Seja G um grafo euleriano. Logo, por definição, ele contém um circuito euleriano. Assim, por cada vértice desse circuito, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas que passam por cada vértice é par.

Se removermos uma aresta de um grafo euleriano, ele deixara de ser euleriano, mas ainda conterá um caminho euleriano (é só começar e terminar o caminho nos vértices correspondentes as arestas removidas). Isso significa que um grafo que contém um caminho euleriano pode ter dois vértices de grau ímpar.

Voltando aos dominós, ligar peças, montar caminhos, é um forte indicio de que nosso problema pode ser resolvido usando-se grafos. Seja o seguinte grafo: G, onde os vértices são os números 0..6 e as arestas são os dominós. Será possível montar uma sequência com todos os dominós se, e somente se, G contiver um caminho euleriano. Em outras palavras, uma sequência de dominós não é nada mais do que um caminho euleriano onde eu peguei as arestas do grafo (os dominós) e enfileirei.

Note que os dominós podem formar um grafo que não é conexo, mas que possui dois sub grafos conexos e eulerianos, assim é necessário testar isso (com uma busca em profundidade por exemplo) para garantir que os dominós formem uma sequência única.

Implementação

8776. Batalha naval

Olá, estamos aqui de novo para resolver mais problemas! Hoje vamos falar de batalha naval e nos divertir um pouco contando quantos navios conseguimos afundar nesse conhecido jogo, já que é isso que o problema 8776. Batalha naval nos pede. 

Modelagem

Mais especificamente, esse problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determine o número de navios do outro jogador que foram destruídos.

A entrada do problema já nos dá uma boa ideia de como resolvê-lo, basta armazenar o tabuleiro em uma matriz e contar quantos navios foram afundados. Cada posição da matriz pode ser de três tipos: água, navio intacto ou navio avariado por um disparo. Observe que não precisamos armazenar a informação sobre os tiros que acertaram a água.

A restrição de que dois navios não podem ter arestas em comum nos permite aplicar uma busca em largura ao tabuleiro e ir contando quantos navios foram afundados. Não vou explicar, aqui, o que é uma busca em largura já que esse assunto é extensamente abordado em qualquer estudo sobre grafos. Veja que estou apenas pegando emprestada a ideia da busca em largura, mas não estou modelando o problema usando grafos.

Complexidade

Dado um tabuleiro de N x M nossa solução avalia cada posição da matriz uma vez, assim sendo nossa solução é O(N*M).

Implementação

Abaixo uma implementação em c++ do problema. Infelismente, não estou muito inspirado para falar sobre ela já que, como você deve ter visto, o problema é bem simples.

18285. Ano Novo

Para você que gostou de nossa últama postagem, estamos aqui de novo para resolver mais problemas!

Nem só de problemas complexos vive o spoj e hoje vamos falar de um problema, que se você não for capaz de resolver com facilidade, você deve pensar seriamente em parar de ler esse blog. Nesse post vamos falar do problema 18285. Ano Novo. De modo resumido o problema pede que, dada a hora atual, você responda quantos segundos faltam para meia noite.

Modelagem da solução

Converta a entrada para segundos e faça a subtração (eu falei que era simples).

Implementação

Uma dica que pode servir em outros problemas, sempre use printf e scanf eles são bem mais rápidos que cin/cout e além disso, é possível ler entradas mais complexas de forma mais simples.