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.