3597. Par ou Ímpar

Olá meus amigos nerds, tenho boas notícias para hoje. Vocês se lembram que eu comentei aqui que eu estava implementando um recomendador de problemas, para facilitar a vida de quem usa o spoj. Pois é, essa semana consegui dar mais um pequeno passo e implementar alguns algoritmos mais simples para fazer isso. E nada melhor do que testar um algoritmo implementando outro, não é verdade? Assim o problema que vamos resolver hoje nos foi sugerido por um dos algoritmos de recomendação que implementei. Não vou falar do recomendador hoje, pois pretendo dissecar esse assunto mais a fundo nas próximas semanas.

O problema de hoje é o 3597. Par ou Ímpar e ele nos pede que ajudemos Joaõzinho e Maria a resolverem a confusão que eles fizeram em uma brincadeira de par ou ímpar. Eles jogaram muitas vezes par ou ímpar e anotaram os resultados em cartões. Em todos os jogos João escolheu ímpar (e, conseqüentemente, Maria escolheu par). Durante os jogos cada jogador escreveu nos cartões quantos dedos ele/ela mostrou, usando uma carta para cada jogo. O objetivo deles era ser capar de re-checar os resultados depois, procurando pelos cartões de cada jogo. Entretanto, no fim do jogo os cartões de cada jogador estavam fora de ordem o que impedia que eles contassem exatamente quantas partidas cada um ganhou.

Mais especificamente, o problema nos pede que dado o conjunto de números escritos nos cartões,  determinar o número mínimo de jogos que Maria certamente ganhou.

Solução

Observe que é impossível saber quantos jogos cada um ganhou exatamente. Entretanto, independente de quantos jogos cada um ganhou o seguinte invariante deve se manter:

jogos_ganhos_maria + jogos_ganhos_joao = n

onde n é o total de jogos disputados.

Como é muito difícil calcular diretamente o número mínimo de jogos que Maria ganhou, vou resolver o problema reverso: calcular qual é o máximo de jogos que João pode ganhar. Esse tipo de abordagem as vezes é bem útil, sendo aplicada em vários problemas de otmização.

Na situação que Maria ganha o mínimo de jogos possíveis, João necessariamente deve ganhar o maior número de jogos possíveis, assim:

min_jogos_ganhos_maria + max_jogos_ganhos_joao = n

ou

min_jogos_ganhos_maria  = n - max_jogos_ganhos_joao


Só um lembrete:
par + par = par
par + ímpar = impar
ímpar + par = impar
ímpar + ímpar = par

Maximizar o número de jogos ganhos é fácil. Lendo o lembrete acima, você provavelmente já matou ou problema. Basta pensar que cada vez que João colocou um número par, Maria colocou um ímpar, e vice versa. Assim:

max_jogos_ganhos_joao = max_casamentos(joao_par, maria_impar) + max_casamentos(joao_impar, maria_par)

max_casamentos(joao_par, maria_impar) é fácil de calcular, e é igual ao mínimo entre joao_par e maria_impar. Assim:

max_jogos_ganhos_joao = min(joao_par, maria_impar) + min(joao_impar, maria_par)

logo

min_jogos_ganhos_maria  = n - min(joao_par, maria_impar) - min(joao_impar, maria_par)

E essa é justamente a solução do problema.

Implementação

1745. Recuperação

Olá meus amigos nerds, hoje estou com preguiça então falarei de um problema fácil. Mentirinha, estou é fazendo um recomendador de problemas para o spoj, em breve falarei mais sobre ele. 

Por incrível que pareça existem dezenas de problemas fáceis no spoj. E o problema 1745. Recuperação é um deles. Nesse problema, é pedido que dado uma lista de inteiros se encontre um inteiro nessa lista tal que ele seja igual a soma dos outros inteiros que o antecedem na lista.

Solução

De forma mais formal queremos um número a[k] tal que:

a[k] = a[1] + a[2] + ... + a[k-1]

Então basta percorrer a lista e testar essa propriedade. É o que o algoritmo abaixo faz:

soma = 0
for cada elemento a[i] da lista
    if  a[i] == soma
        numeroPedido = a[i]
        break;
    soma += a[i]

Basta então imprimir numeroPedido

Implementação

Observe que  numeroPedido deve ser inicializado com um valor inválido (menor que a menor soma possível, ou maior que a maior soma possível), se você usar numeroPedido = -1 (eu fiz isso da primeira vez :P) você vai levar merecidamente um belo de um wrong answer.

2616. Caixeiro-Viajante B

Olá meus amigos nerds, mesmo estando com um pouco de calos nos olhos devido ao jogo de ontem da seleção, estou aqui hoje para resolver um probleminha com vocês.

Hoje vamos falar do problema 2616. Caixeiro-Viajante B que nos pede para traçar a rota de um caixeiro viajante de modo que ele gaste o mínimo possível com passagens de trem para visitar todos os seus clientes. Mais especificamente, o problema só nos pede o valor mínimo gasto com as passagens.

Solução

O primeiro ponto a destacar, é que esse não é o clássico problema do caixeiro viajante, tão estudado quando se fala em problemas NP. Ainda bem, já que isso facilita bastante as coisas.

Como em outros problemas que já resolvemos aqui, vamos pensar em uma modelagem usando grafos. Nesse problema isso é bem simples, as cidades seriam os vértices e as ferrovias as arestas.

O problema nos afirma que há apenas um caminho ligando cada par de cidades, então nosso grafo é, na realidade, uma árvore. Cada cidade em que há um cliente do caixeiro precisa ser visitada, isso significa que cada ferrovia que o caixeiro passar será usada 2 vezes (ida e volta).

A forma de minimizar o gasto com passagens é não percorrer uma ferrovia mais do que uma duas vez (ida e volta), já que há apenas 1 caminho entre qualquer par de cidades. Isso significa que, cada vez que o caixeiro chegar a uma "encruzilhada" que tem caminhos para mais do que uma cidade ele deve visitar a primeira delas, voltar até a encruzilhada e partir dali direto para a próxima cidade. Observe que o que acabei de descrever é simplesmente percorrer o grafo em uma busca em profundidade.

Problema resolvido? Não! Pode haver cidades que não possuem clientes do caixeiro e que não estão no caminho de outras cidades, ou seja, que não precisam ser visitadas, mas que provavelmente seriam contadas caso você fizesse uma busca em profundidade simples. Mas isso é simples de resolver. Para contornar esse pequeno detalhe basta fazer a busca em profundidade primeiro (enraizando a árvore pelo nó que representa a cidade inicial do caixeiro) e ir percorrendo os caminhos das cidades de destino para a raiz (ou seja, fazendo o caminho oposto), marcando as arestas para que elas não sejam contadas novamente.

Implementação

1389. Pedido de Desculpas

Olá meus amigos nerds, hoje falaremos um pouco de um dos problemas mais clássicos de programação dinâmica, o problema da mochila. E isso, graças ao nosso amigo Cuca, que saiu para jogar futebol e se esqueceu de se encontrar com sua namorada. 

Mais especificamente, o problema 1389. Pedido de Desculpas nos pede que ajudemos Cuca a escrever um pedido de desculpas com o maior número de repetições da palavra desculpa. Para isso Cuca nos forneceu um conjunto pré escolhido de frases e quer usar essas frases para preencher um cartão de desculpas que cabe apenas um número limitado de caracteres.

Solução

O problema aqui é bastante simples, apenas se você já estudou um pouco de algoritmos (e consequentemente, conhece o problema da mochila booleana). Observe que podemos mapeá-lo da seguinte forma:

cartão = mochila
tamanho das frases = peso dos objetos
# de desculpas por frase = valor ($) dos objetos

Mochila Booleana

O problema da mochila é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.

O problema da mochila é um dos 21 problemas NP-completos de Richard Karp. Isso quer dizer que sua solução tem complexidade O(2^n). Observe que, esse problema pode ser resolvido como um problema de decisão, ou seja, para cada objeto, decida se ele deve ou não ser colocado na mochila. Uma forma simples de se decidir pela adição ou não de um objeto é gerando todos os subconjuntos de objetos e escolhendo o subconjunto de maior valor:

melhorSolucao=0
foreach subconjunto dos objetos
    valor = calcule o valor desse subconjunto
    if valor > melhorSolucao
         melhorSolucao = valor

Felizmente, existe uma solução pseudo polinomial para o problema. Suponha que temos n objetos, sendo que o i-ésimo objeto tem valor v[i] e peso p[i]. Podemos usar uma estrutura recursiva para resolver o problema da mochila booleana por programação dinâmica. A ideia é guardar em uma tabela (mochila) as soluções das (sub)instâncias do problema. A tabela é definida como:

mochila[# de objetos][capacidadeMáximaMochila] =  maior valor alcançado com uma mochila de capacidade capacidadeMáximaMochila  e itens 1,...,# de objetos

Lembrando que ou um item é necessário para alcançar o valor ótimo, ou não é, então podemos expressar o valor dos elementos de nossa tabela como:

mochila[i][peso] = max(
               mochila[i-1][peso], //o elemento i não é usado pela solução ótima
               v[i] + mochila[i-1][peso-p[i]] //o elemento i é usado pela solução ótima
              )

como condição de contorno caso p[i] > peso => mochila[i][peso] = mochila[i-1][peso]

Observe que essa solução tem complexidade O(# de objetos * capacidadeMáximaMochila). Mas, anteriormente eu não afirmei que o problema da mochila é NP-completo? Se você ficou curioso a esse respeito aqui e aqui você poderá encontrar a justificativa.

Dei aqui apenas uma explicação superficial sobre o problema da mochila, se você não o conhecia e achou interessante uma ótima referência para uma leitura mais aprofundada é o livro do Cormen (Introduction to Algorithms).

Implementação