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:
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
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:
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.
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.
Nenhum comentário:
Postar um comentário