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