12939. Păo a metro

Olá meus amigos nerds. Hoje vamos brincar de cortar pães para fazermos sanduíches que serão usados durante uma maratona de programação. Isso mesmo! Já que é isso que o problema 12939. Pão a metro nos pede para fazer. Mais especificamente, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem servidas, queremos saber o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.

Solução

A solução simples para esse problema seria tentar todos os tamanhos possíveis para os pães e escolher o maior. Entretanto, isso, é claro, não é eficiente o suficiente.

Suponha que conheçamos o tamanho de pão máximo. Para tamanhos superiores de pão não conseguimos servir as n pessoas (caso contrário por contradição esse tamanho não seria máximo). Assim, ao invés de procurar por força bruta o tamanho ótimo, podemos aplicar busca binária ao problema, uma vez que temos uma propriedade que é verificada para valores inferiores a um número (o tamanho máximo), mas não o é para valores inferiores.

Agora só nos falta definir os limites nos quais queremos aplicar busca binária. Obviamente, o tamanho mínimo de pão é 1. Já o máximo é o maior tamanho entre as k fatias de pão (lembre-se de que não podemos juntar duas fatias).

Implementação

Observe que o código testa duas condições de contorno. Uma delas é o pão de tamanho 1 (limite inferior do intervalo) e outra o pão de tamanho k (todos os pedaços são do mesmo tamanho).

819. Pedágio

Olá meus amigos nerds, hoje vamos ajudar Juquinha a decidir quais cidades ele pode visitar. Já que é isso que o problema 819. Pedágio nos pede para fazer. Mais especificamente, dado um mapa com as cidades e estradas, determinar quais cidades são alcançáveis a partir da cidade em que Juquinha se encontra e que o caminho até elas necessite que sejam pagos no máximo P pedágios.

Solução

O problema quase que implora por uma solução usando-se grafos, onde os vértices representam cidades e as arestas rodovias entre elas. Neste grafo o peso de uma aresta representa o custo do pedágio. Assim sendo o problema se reduz ao cálculo do caminho mínimo entre o vértice que representa a cidade onde Juquinha está e todos os outros vértices do grafo.

O caminho mínimo pode ser calculado facilmente usando-se o algoritmo de dijkstra. Hoje estou com pouco tempo, mas outro dia eu ainda quero discutir mais esse, que é um algoritmo muito clássico.

Assim sendo, para resolver o problema basta calcular o caminho mínimo e a resposta será o conjunto de cidades que estão a menos de P pedágios de distância.

P.S. como todos os pesos das arestas são iguais a 1 eu poderia ter simplesmente feito uma busca em largura para calcular a distância, mas resolvi usar dijkstra para deixar a explicação da solução mais simples :).

Implementação

P.S. Não reparem a feiura do código, mas é que eu resolvi esse problema faz muitos anos e fiquei com preguiça de deixar o código mais bonitinho. Pelo menos, observem que realmente melhoramos quando brincamos continuamente de resolver problemas kkk.

11651. Banda

Olá meus amigos nerds, esquentem seus motores, pois hoje começa o code jam 2015 e é claro que vocês não vão querer perder essa.  E para começar bem o dia, nada melhor do que resolvermos um probleminha, não é mesmo?

Hoje vamos ajudar o Jimmy a montar sua banda, já que é isso que o problema 11651. Banda nos pede para fazer. Mais expecificamente, dada uma lista de músicos e suas respectivas afinidades e deseja-se escolher três dentre esses músicos de modo a maximizar a afinidade deles.

Solução

O problema é bem simples. Podemos modelar os músicos como sendo vértices de um grafo, desse modo as arestas do grafo representariam a afinidade entre o par de músicos representados pelos vértices. Agora basta percorrermos esse grafo e encontrarmos a trinca de músicos com a maior soma das afinidades. O seguinte algoritmo faz isso:

maxScore = -1

for i in vertices_grafo

    for j in vertices_adjacentes[i]

        for k in vertices_adjacentes[j]

            score = afinidade[i][j] + afinidade[i][k] + afinidade[j][k]

            if score > maxScore

                maxScore = score

                trio = (i, j, k)

O algoritmo acima é O(n^3), onde n é o número de vértices, mas como a entrada é pequena esse algoritmo é suficiente para resolver o problema e passar no tempo.

Implementação

17384. Desfile dos Patos

Olá meus amigos nerds, depois de um bom hiato, devido a eu ter me mudado e ficado algum tempo sem internet :(, estamos de volta para resolver mais problemas.

Mas para compensar hoje vamos resolver um tipo de problema que eu gosto muito: um problema que a solução fácil, não é suficientemente boa, nos forçando a ir além e fazer melhor.

Hoje vamos verificar qual a cor que mais aparece durante um desfile de patos. Já que é isso que o problema 17384. Desfile dos Patos nos pede. Mais especificamente, dada uma fila de patos, em que cada pato tem uma plumagem de cor diferente, determinar qual é a cor majoritária dentre as cores da plumagem dos patos, isto é, a cor que aparece em mais da metade das plumagens.

Solução

Apesar da aparente simplicidade esse problema é bem difícil. Ele possuí um limite de tempo muito apertado, e isso faz com que algo que geralmente não é muito importante, quando tratamos de complexidade de algoritmos, se tornar relevante, as constantes.

Vocês já devem ter percebido que um simples mapa resolve o problema, isto é armazene contadores para cada cor e no final verifique qual cor majoritária. Se implementarmos o mapa como um hash, esse algoritmo é linear. Além disso, ele tem complexidade ótima, já que não é possível resolver esse problema sem analisar cada elemento da lista.

Entretanto o algoritmo acima não é eficiente o suficiente para resolvermos esse problema. Quem diria, um hash não é eficiente o suficiente para resolve-lo! Depois de muito pensar (e até achar que quem inseriu o problema cometeu algum equivoco no time limit), observamos que o problema tem uma característica especial, a cor mais frequente é majoritária, isso é ela tem mais aparições na lista que a soma de todas as outras cores. Isso nos permite abrir mão do hash e usar um único contador para verificar qual é a cor majoritária.

A ideia é a seguinte, se do número de aparições da cor majoritária subtrairmos o número de aparições de cada uma das outras cores, esse resultado é necessariamente maior que 0. Assim, podemos usar um algoritmo guloso para contar a diferença entre o número de aparições da cor majoritária para as outras cores. Podemos iniciar nossa contagem com qualquer cor, já que ao final necessariamente a cor majoritária tem elementos o suficiente para "cancelar" com cada um dos elementos das outras cores. O algoritmo abaixo vai verificando qual a cor majoritária até a 0-ésima posição do vetor, 1-ésima posição, ..., n-ésima, etc

corMajoritaria = 0
cnt = 0
for cor in corPatos
    if cnt == 0
       corMajoritaria = cor
    if cor == corMajoritaria
        cnt++
    else
        cnt--

O algorítmo acima é mais eficiente que um hash, pois não tem que pagar o custo de iterar sobre todos os elementos do hash ao final para verificar qual é o que tem o maior contador.

Implementação