Esse blog se destina a todos os nerds que não têm tempo para uma boa vida social, pois são atormentados por não conseguirem resolver os problemas do spoj. Aqui você poderá encontrar soluções comentadas para uma grande variedade de problemas relacionados a competições de programação.
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
Olá meus amigos nerds. Hoje vamos fazer um algoritmo para detectar se dois retângulos se interceptam ou não. Já que é isso que o problema 19958. Detectando Colisões nos pede para fazer. Mais especificamente, dados dois retângulos, que tem seus lados paralelos aos eixos, determinar se há alguma interseção entre eles.
Solução
O caso geral desse problema, que é determinar se dois polígonos tem pontos de interseção é bem complexo. Para nos ajudar, o problema trata apenas de retângulos e ainda fixa que seus lados são paralelos aos eixos. Ai fica fácil né!
O problema nos fornece os cantos inferior esquerdo e superior direito de cada retângulo. Vamos tentar estabelecer as condições para que os dois retângulos não possam se interceptar.
Caso o canto superior direito de um dos retângulos esteja 'atráz' do canto inferior esquerdo do outro não há como haver interseção pois nesse caso um retângulo 'termina' antes que o outro comece. Da mesma forma, se o canto superior direito de um dos retângulos estiver 'abaixo' do canto inferior esquerdo do outro um dos retângulos terá 'terminado' antes do outro começar. Pensando nas coordenadas x,y desses pontos teríamos (sendo a e b os retângulos):
if (a_sup_dir_x < b_inf_esq_x || a_sup_dir_y < b_inf_esq_y || b_sup_dir_x < a_inf_esq_x || b_sup_dir_y < a_inf_esq_y ) responda não
A condição acima é necessária. Agora vou mostrar que ela é suficiente. Observe que na situação dos dois cantos superiores da direita estarem no sub espaço acima e a direita dos cantos inferiores, os seguimentos (a_inf_esq, a_sup_dir) e (b_inf_esq, b_sup_dir) seriam tanto diagonais do retângulo formado pelos pontos (a_inf_esq, b_sup_dir, a_sup_dir, b_inf_esq) quanto dos retângulos originais, mas como as diagonais de um retângulo sempre se interseptam, resulta que esse ponto pertencerá a uma diagonal de cada um dos retângulos a e b e assim eles também se interceptam.
Olá meus amigos nerds. Esse mês demorei um pouco a dar as caras por aqui, mas foi por uma boa causa, estava escrevendo um paper :P algo que eu não fazia há muito tempo. E não seria um paper se eu não tivesse que ficar escrevendo e reescrevendo tudo até de madrugada. Vocês não acham? kkk.
Hoje ajudar vamos ajudar nossos amigos da obi a vender algumas casas. Já que é isso que o problema 18543. Vende-se nos pede para fazer. Mais especificamente, (por culpa da Dilma) a obi precisa vender alguns de seus imóveis e quer que os que restarem estejam o mais próximos possível, ou seja, que a distância entre o primeiro e o último prédios restantes deve ser a menor possível.
Solução
Devo dizer que esse é um problema fácil e quase não tive vontade de escrever sobre ele. Mas esse foi o único problema que eu resolvi essa semana. Então vai ter que servir.
Devemos perceber que as casas restantes serão necessariamente consecutivas (pensando na distância para o início da rua). É só você pensar que para vender uma casa no 'meio' das que restaram, uma casa fora da sequência não poderia ser vendida, mas a distância dessa casa para a casa do canto oposto das que sobraram aumentaria.
Assim basta ordenar as casas pela distância. E percorrer a lista de casas computando a distância pedida.
Implementação
Me desculpem pelo código feio, mas é que eu o fiz enquanto assistia uma palestra chata sobre devops :P
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.
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.
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.
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.
