11609. Foco

Olá meus amigos nerds. Hoje vamos ajudar nosso amigo fotografo a descobrir quantas fotos ele precisa tirar para ter uma foto nítida de todos os objetos de sua cena. Já que é isso que o problema 11609. Foco nos pede para fazer. Mais especificamente, dados os intervalos contendo objetos que o fotografo quer fotografar, determinar qual é o mínimo de fotos que ele tem que tirar para que haja pelo menos uma foto de cada intervalo. 

Solução

Esse problema é muito similar ao da semana passada (18553 - Janela). Vou usar o mesmo raciocínio que usei lá aqui.

O problema consiste em encontrar as interseções dos intervalos, pois assim eu posso tirar uma foto apenas da interseção dos intervalos e assim economizar fotos.

Pense nos intervalos ordenados pelo ponto em que eles terminam. Eu preciso de pelo menos uma foto do primeiro intervalo, sendo assim vou escolher tira-la no ponto onde este intervalo acaba. Dessa forma eu posso aproveitar essa foto para todos os intervalos subsequentes em que o ponto de inicio desses intervalos seja menor que o ponto que eu tirei a foto. Esse algoritmo é ótimo, pois eu necessariamente tenho que tirar uma foto do primeiro intervalo. Basta agora eu remover todos os intervalos que eu já tirei uma foto e repetir o passo anterior até que não sobre nenhum intervalo. De forma mais algorítmica teríamos:

Seja S o conjunto dos intervalos ordenados pela coordenada do seu ponto de fim
num_fotos = 0
pos_atual = 0
para cada intervalo X in S
    if X.inicio > pos_atual
        num_fotos++
        pos_atual = X.fim

Observe que pos_atual marca até que ponto da reta nós já avaliamos (pensando nos intervalos sobre uma reta), ou seja, qual é o ponto em que o intervalo anterior termina. O if evita que incrementemos num_fotos caso o inicio do intervalo se sobreponha ao intervalo anterior, o que na prática é o mesmo que remover o intervalo atual da lista.

Implementação

18553. Janela

Olá meus amigos nerds. Hoje vamos calcular a área aberta de uma janela. Já que é isso que o problema 18553. Janela nos pede para fazer. Mais especificamente, dadas as posições de vários pedaços de vidro e seus comprimentos e o comprimento total da janela determinar qual a área total da janela que está aberta. 

Solução

Devo confessar, quando comecei a ler esse problema pensei que ele seria um pouco mais difícil, mas o tamanho da entrada (3) é tão pequeno que por força bruta é possível faze-lo. Vou ignorar esse fato e mostrar como seria possível resolver esse problema, caso os vidros da janela fossem de tamanhos diferentes e em maior número.

O problema consiste em encontrar pedaços da janela que não estejam cobertos por nenhum vidro. Qual é a condição necessária e suficiente para que um pedaço da janela não esteja coberto? Se pensarmos bem, essa condição é até bem simples (depois que a vemos, é claro!). Um buraco é definido por um fim de janela e pelo inicio da primeira janela seguinte, ou seja, só pode haver um buraco se o ponto de inicio de uma janela for maior que o ponto de termino da janela anterior.

Mas como garantir que não existiram outros pedaços de vidro entre esses pontos? Isso é fácil, basta ordenar os pedaços de janela pelo ponto em que elas terminam. Pense nos pedaços i e i+1 ordenados. Não pode haver uma janela que termine em um ponto entre o fim de i e de i+1, caso contrário i e i+1 não poderiam seguir um ao outro na ordenação, deveriam ter o ponto de fim desse terceiro pedaço entre eles.

Sendo assim, a solução do problema consiste em ordenar os pedaços de vidro pelo seu ponto de fim e ir somando os espaços entre o inicio da próxima janela e o fim da anterior.

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.

18550. Troco

Olá meus amigos nerds. Hoje completa exatamente um ano que eu resolvi um problema relacionado a moedas. E para comemorar, nada melhor do que resolver outro problema do tipo. Vamos tentar verificar se é possível pagar uma conta de modo exato apenas com as moedas que estão em nosso bolso. Já que é isso que o problema 18550. Troco nos pede para fazer. Mais especificamente, dadas m moedas, determinar se é possível somar exatamente v centavos usando um subconjunto dessas moedas.

Solução

Como todo problema de programação dinâmica esse não é fácil. Uma solução que enumere todos os conjutos possíveis de moedas e verifique se eles somam v não viável.

O segredo, para resolver esse problema, esta em pensar o que acontece quando eu pego uma moeda. Suponha que eu conheça todos os valores que eu consigo somar com as moedas restantes, se a cada um desses valores, eu somar a moeda atual eu fico com um novo conjunto de valores que eu consigo somar. A união desse conjunto e do anterior forma todas as somas que eu consigo fazer até o momento.

Isso sugere uma solução usando programação dinâmica. Com 0 moedas eu só consigo somar 0. Adicionando a primeira moeda eu só consigo somar 0 e o valor da moeda. Com a segunda eu já consigo somar 0, o valor da primeira, o valor da segunda e a soma das duas... Ou seja, se eu armazenar para cada valor possível de soma (menor ou igual a v é claro) se é possível somar aquele valor, para adicionar uma moeda é só eu percorrer esse vetor de estados e ir atualizando as posições dele com as novas somas possíveis.

A ideia acima funciona pois: se já é possível somar x com um conjunto de moedas, se eu adicionar mais uma moeda ao problema, continua sendo possível eu somar x (basta eu não usar a nova moeda). Se eu consigo somar a, b e c e eu adiciono outra moeda (d) ao problema eu vou poder somar além de a, b e c, (a+d), (b+d), (c+d). Algoritmicamente falando:

somas_possiveis = {0}
para cada moeda x
    para cada soma em somas_possiveis
        novas_somas += (x+soma)
    somas_possiveis |= novas_somas

Ou considerando que somas_possiveis sera representado por um vetor
somas_possiveis[0] = True
para cada moeda x
    para i=len(somas_possiveis), i >= x, i--
        Se somas_possiveis[i-x]
            somas_possiveis[i] = True

Note que se eu posso somar i-x centavos, se eu adicionar a moeda atual eu posso somar i centavos. O loop é feito de forma decrescente para garantir que eu não use x duas vezes para uma mesma soma, já que i-x ainda não foi calculado para a moeda atual.

Note que a solução apresentada depende do valor de v, ou seja, é uma solução pseudo polinomial. Mais precisamente a complexidade dessa solução é O(v*m), como v e m são relativamente pequenos essa solução é suficiente para conseguirmos superar o time limit.

Implementação

:P O operador -- serve para alguma coisa! Observe que se invertermos a lógica do loop da linha 22 para uma lógica aditiva o programa deixa de produzir a resposta certa, pois nesse caso quebramos nosso invariante de que somas_possiveis[v-moeda] não utiliza a moeda atual para ser somado.

3242. Loop musical

Olá meus amigos nerds. Hoje vamos estudar um pouco sobre máximos e mínimos em um gráfico. Já que é isso que o problema 3242. Loop musical nos pede para fazer. Mais especificamente, dado um conjunto de pontos formando um gráfico, determinar quantos mínimos e máximos locais esse gráfico possúi.

Solução

Para quem se lembra das aulas de cálculo, esse é um problema fácil. Mínimos e máximos locais são pontos de inflexão do gráfico, isto é pontos em que a derivada é nula. Isso significa que, dados três pontos, existe pelo menos um mínimo (ou máximo) local entre esses pontos se o sinal da derivada se alterar entre eles. Para que isso ocorra, basta que o ponto do meio seja mais alto, ou mais baixo, que os outros dois pontos.

Então basta testar se isso ocorre e lembrar que no problema os pontos formam um loop, ou seja, o primeiro ponto segue o último ponto.

Implementação

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 :)