PRACAALI - Praça de alimentação

Olá meus amigos nerds! Hoje vamos resolver o problema PRACAALI - Praça de alimentação pedido pelo nosso amigo Jonas. Mais especificamente, o problema pede para estimar a quantidade máxima de pessoas que podem ter estado dentro de uma cantina, dados os horários de entrada e saída de cada pessoa.

Solução

Esse é um problema difícil, levei um bom tempo para resolver. Quando nos deparamos com um problema assim, a primeira coisa a fazer é tentar resolver uma versão mais fácil do problema. E é assim que vamos resolver esse problema hoje.

Caso não houvessem ? o problema poderia ser modelado como um problema de soma máxima em vetores. Pense que cada pessoa que entra adiciona +1 a soma de pessoas dentro da cantina e cada pessoa que sai -1 a tal soma. Assim, se ordenássemos os eventos de entrada e saída pela hora que eles aconteceram e aplicarmos o algoritmo de soma máxima encontraríamos o número máximo de pessoas dentro da cantina.

Como queremos o número máximo possível de pessoas que poderiam estar na cantina, podemos dispor das ? da forma que quisermos. Então nosso problema se torna em tentar descobrir a atribuição correta de entrada/saída para cada ?.

Vamos começar descobrindo o número de interrogações que temos que transformar em entradas. Sejam num_e o número de eventos de entrada dados na instância do problema, num_s o número de eventos de saída e num_x o número de eventos incertos (?). É garantido pelo enunciado que a entrada do problema é coerente. Ou seja, metade de todos os eventos, mesmo os ?, são de entrada e metade de saída. Além disso, todo evento de saída é correspondente a um evento anterior de entrada.

Vamos estimar o número máximo de eventos ? que podem ser de entrada. Temos dois casos a considerar.

Se num_e > num_s: sabemos que, dos num_x eventos ?, (num_e - num_s) são de saída, para compensar a falta de eventos de saída na entrada. Do restante, metade será de entrada e metade de saída.

Por outro lado, se num_s > num_e, sabemos que (num_s - num_e) eventos ? deverão ser de entrada correspondente aos eventos de saída sobrando.

De forma mais algorítmica, o número máximo de eventos ? que necessariamente tem que ser eventos de entrada (max_entradas) seria:

num_x = total_eventos - (num_s + num_e)
if num_e > num_s
    max_entradas = (num_x - (num_e - num_s)) / 2
else
    max_entradas = num_s - num_e + (num_x - (num_s - num_e)) / 2

 

A grande sacada para resolver esse problema é ver que podemos atribuir os primeiros max_entradas eventos ? como sendo eventos de entrada. A prova de que este algoritmo guloso funciona será por contradição. Vamos supor que exista outra solução e mostrar que nossa solução não será pior que essa outra solução. Para isso, vamos partir da nossa solução e trocar eventos de posição e ver o que acontece

Vamos chamar de período o espaço entre dois eventos correspondentes a uma mesma pessoa, relativo à sua entrada. Ou seja, o período de uma pessoa é o tempo entre seus eventos de entrada e saída. Note que o período depende do horário de entrada.

Suponha uma solução ótima diferente da gerada pelo nosso algoritmo. Consideremos nesta outra solução as duas primeiras pessoas a entrar no local que tenham período diferente da nossa solução. Nosso algoritmo, obviamente, classificaria os 4 eventos, em ordem, como EESS (onde E é entrada e S é saída). Uma solução válida diferente da nossa só pode ser ESES; caso contrário, ela seria incoerente (dado que as pessoas que entraram antes têm eventos coerentes associados a elas). Assim, temos três casos possíveis: ou o momento em que o maior número de pessoas estava no restaurante foi entre os dois primeiros eventos, ou entre o segundo e o terceiro, ou entre os dois últimos (E*E*S*S os momentos são os *). Transformando esta suposta solução ótima na nossa solução (ou seja, trocando o tipo dos dois eventos do meio), obtemos uma solução melhor que essa solução ótima (o número de pessoas no restaurante entre os dois primeiros e entre os dois últimos eventos permanece o mesmo, enquanto o número de pessoas entre os eventos do meio foi aumentado em 1). A partir de sucessivas transformações deste tipo, podemos transformar qualquer solução ótima, sem piorá-la, na solução dada pelo nosso algoritmo. Portanto, esta deve, necessariamente, ser ótima.

Então a solução final para o problema é supor que os primeiros num_entradas eventos ? são de entrada e os outros de saída e aplicar o algorítimo da soma máxima de vetores no array resultante.

Implementação

 

8699. Dentista

Olá meus amigos nerds. O circo político do Brasil está pegando fogo hoje. Por isso vou falar rapidinho, já que há coisas mais interessantes que resolver problemas agora.

Hoje vamos resolver conflitos na agenda do doutor Pedro, já que é isso que o problema 8699. Dentista pede para fazer. Mais especificamente, dada a agenda de Pedro, com todos os horários de consulta, determinar qual é o maior número de consultas que ele consegue atender.

Solução

Uma forma ótima de escolher qual a primeira consulta a atender (de modo a maximizar o número total de consultas atendidas) é escolher aquela que acabaria primeiro. Pois, nesse caso, Pedro ficaria disponível o mais cedo possível para atender uma nova consulta. Aplicando essa ideia recursivamente chegamos a solução do problema.

Dito de um modo mais algorítmico:

Ordene as consultas por tempo de término.
Enquanto a lista de consultas não estiver vazia
    Atenda a primeira consulta da lista.
   Remova da lista cada consulta que o tempo de início é menor que o tempo de término da consulta que Pedro está atendendo no momento (como ele esta ocupado, ele não pode atender essas consultas)

Implementação

19949. Fechadura

Olá meus amigos nerds. Hoje vamos brincar de abrir fechaduras. Já que é isso que o problema 19949. Fechadura nos pede para fazer. Mais especificamente, dados uma serie de números (que representam a altura dos pinos da fechadura) e uma posição em que os pinos tem que ser colocados para que a fechadura se abra, determinar qual o número mínimo de movimentos de elevar ou abaixar os pinos para que a fechadura se abra.

Solução

Quando li esse problema pela primeira vez, achei que sua solução envolveria programação dinâmica, já que ele pedia o menor número de movimentos. Entretanto se observarmos bem, o problema afirma que quando um pino é mexido o da frente também o é. Assim, não há o que otimizar, basta percorrer o vetor com as alturas (armazenando o número de movimentos gastos para mover o pino anterior) e ir somando o número de movimentos necessários.

Seja 'altura' o vetor com as alturas dos pinos
Seja m a altura que devemos colocar os pinos
soma_mov = 0
acum = 0
for altura in alturas
        diff = m - (altura + acum)
        soma_mov += abs(diff)
        acum = diff

Implementação

3237. Apagando e ganhando

Olá meus amigos nerds. Hoje vamos tentar descobrir qual é o maior número que podemos formar apagando D dígitos de um número de N dígitos. Já que é isso que o problema 3237. Apagando e ganhando nos pede para fazer.

Eu tenho uma história engraçada com esse problema. Em uma regional da maratona de programação do ICPC eu consegui resolver-lo, mas meu colega de time me convenceu que minha solução estava errada (mesmo estando certa). No final, faltou justamente esse problema para passarmos de fase. Quem mandou eu ser burro kkk.

Solução

Existe uma solução trivial para esse problema:

Seja num o número de N digitos dado
max = 0
while d > 0
    d--
    m = 0
    for i in len(num)
        Seja x o número obtido apagando o i-ésimo digito de num
        m = maximo(x, m)
    max = maximo (m, max)

Obviamente ela não passa no tempo! Isso porque a comparação entre x e m tem complexidade N (o número de bits de x), sendo a complexidade do algoritmo O(d*N^2), o que é muito ineficiente para o problema.

Pense comigo, dados dois números com a mesma quantidade de dígitos, qual deles é maior? Aquele que tem o digito mais a esquerda maior, oras. Essa simples observação nos fornece um algoritmo guloso capaz de responder o problema. Se o primeiro dígito da esquerda for menor que o segundo, a decisão de apagar o primeiro dígito é ótima. Assim:

Seja num uma lista com os N digitos dados
i = num.begin()
j = i++
while i != num.end()
    if == 0
        pare
    if num[i] < num[j]
        apaga(num[i])
    else
        i++

Se conseguirmos apagar os d dígitos usando a observação do parágrafo anterior o problema está resolvido. Pode ocorrer que não consigamos fazer isso, nesse caso, os dígitos do início do número estaram em ordem estritamente decrescente. Basta então repetir o processo acima do fim para o inicio do número para apagar os dígitos que faltam.

Observe que o algoritmo acima é muito mais rápido, tendo complexidade O(N).

Implementação

Observe que em c++ list.erase(it) apaga e invalida o iterador o que nos força a função apaga para evitar problemas.

11016. Reduzindo detalhes em um mapa

Reuso de código é algo muito desejável em engenharia de software. Muitos pensam que isso não é muito comum em maratonas  de programação, mas na verdade tem uma bibliotéca com os algoritmos clássicos implementados ajuda muito.

Hoje aconteceu algo muito engraçado! Como sempre, eu peguei um problema aleatoriamente no spoj e fui resolver (o problema do post anterior :P). Levei pouquissimo tempo para encontrar a solução e quando já tinha a modelagem sabia que precisaria implementar o algoritmo de Kruskal. Eu já havia implementado ele outras vezes. Como é um algoritmo mais longo eu estava com preguiça de fazer isso de novo, então resolvi dar um grep no diretório onde guardo os problemas que já fiz e encontrei tal algoritmo para solucionar o problema 11016. Reduzindo detalhes em um mapa. Até ai tudo normal, mas a coisa engraçada é que o mesmo código (incluindo a parte de entrada e saída) resolvia o problema anterior, ou seja, reuso de código é para os fracos, bom mesmo é reuso de toda a implementação kkk.

Mas especificamente, esse problema pede que dado um mapa de cidades e rodovias que as ligam, selecione um subconjunto das rodovias tal que entre qualquer par de cidades exista uma rota ligando-as e a soma dos comprimentos das rodovias é mínimo.

Solução

Como o problema da árvore geradora mínima e o algoritmo de Kruskal estão fresquinhos em sua cabeça você deve achar esse problema moleza (se não estiverem isso pode ajudá-lo). Não é difícil perceber que o sub conjunto de rodovias pedido é uma árvore. Caso não fosse, ou seja, houvesse algum ciclo no grafo, poderíamos remover a rodovia com maior comprimento o que não causaria a perda da conectividade entre as cidades (sobra o outro caminho) e ainda diminuiria o comprimento total.

Logo a sulução do problema é soma dos pesos da árvore geredora mínima formada.

Implementação

12999. Frete da Família Silva

Olá meus amigos nerds. Hoje vamos ajudar a família Silva a comemorar sua chegada a Marte. Já que é isso que o problema 12999. Frete da Família Silva nos pede para fazer.

Tenho que cumprimentar muito o autor desse problema, ele conseguiu ser extremamente criativo. O problema em si é interessante e o cara fez uma contextualização muito engraçada usando elementos do Chapolim Colorado. Vale até o quote:

"O presidente de Pizzalândia, Lagosta da Silva, ... Resolveu, então, mandar uma família inteira para Marte. No caso, a dele mesmo, a família Silva, provavelmente a mais numerosa do planeta.

Tal família estabeleceu-se em Marte sem problemas, ainda mais com novas invenções que havia por lá. Uma delas era a pílula de nanicolina, substância descoberta naquele planeta, próximo à uma região onde existem pedras voadoras, pedras macias e até pedras falantes. Lendas dizem que algum outro ser extra-terrestre depositou a nanicolina ali num passado distante, enquanto visitava o planeta. O efeito da pílula de nanicolina é a diminuição de tamanho de quem a toma, por um determinado tempo. Tal pílula foi, então, produzida em escala industrial e hoje em dia é distribuída pelos governos marcianos aos colonos que lá residem."

Mas deixando a brincadeira de lado. Mais especificamente, nossa tarefa é determinar o valor mínimo gasto por senhor Lagosta para fazer com que todos os parentes se encontrem.

Solução

Esse é claramente um problema que pede uma modelagem utilizando grafos (colônias = vértices, caminhos = arestas). Além disso, estamos lidando com um grafo ponderado (as 'estradas' tem peso) e conexo, já que sempre existe um caminho entre quaisquer duas colônias.

A primeira coisa a perceber  é que, dada um par de cidades, devemos usar o caminho mínimo entre essas cidades para deslocar todos os colonos de uma cidade para a outra.

Como a capacidade dos ônibus é inimitada, nessa viagem podemos aproveitar para levar todos os colonos que estão nos outro vértices do caminho mínimo,  já que esse também será o caminho mínimo para eles. Disso deduzimos que nenhuma estrada será usada mais que uma vez.

Do paragrafo anterior, também podemos concluir que o sub grafo formado pelos caminhos de todos os colonos até o ponto de encontro é uma árvore. Caso houvesse um ciclo poderíamos retirar a aresta de maior peso desse ciclo e usar o outro caminho restante para levar as pessoas que estavam nos vértices que a aresta foi removida.

Logo a solução para nosso problema é a árvore que tenha o menor custo (i. e. a soma dos pesos das arestas). Esse é um problema bastante famoso em computação chamado problema da árvore geradora mínima e pode ser resolvido utilizando o algoritmo de Kruskal.

O algoritmo de Kruskal, basicamente, ordena as arestas e depois itera sobre a lista ordenada escolhendo de forma gulosa as arestas que fazem parte da árvore. Assim, a complexidade dele é O(num_arestas*log(num_arestas) + num+arestas) = O(num_arestas*log(num_arestas)). Obs: a operação dsf_union tem custo amortizado O(1). Ela é parte da implementação de um conjunto disjunto, um algoritmo capaz  de fazer find e union entre conjuntos de forma eficiente.

Implementação

Veja que, a implementação do algoritmo de Kruskal não é muito complicada. De quebra ainda ganhamos a implementação de um conjunto disjunto de árvores para uso futuro :)

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