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 nós vamos ajudar a guarda costeira a pegar um ladrão de bolsas, já que é isso que o problema GUARDCOS - Guarda costeira pede para fazer. Mais especificamente, dadas as velocidades dos barcos da guarda costeira e do ladão determinar se ele será pego.
Solução
Esse é um problema bem fácil. Como o barco do bandido se desloca perpendicularmente a costa, em direção ao limite que a guarda costeira pode prende-lo, os guardas podem simplesmente chegar lá primeiro e prender o bandido. Assim basta saber se a guarda chega nesse ponto antes do bandido ou não.
A distância que o barco da guarda costeira percorre (hipotenusa do triângulo) pode ser calculada com o teorema de Pitágoras. Como a velocidade dos barcos é constante e conhecida temos:
Se tempo_guarda < tempo_bandido responda sim, ou seja dist_guarda = sqrt(12^2 + d^2) velocidade = distância / tempo => tempo = distancia / velocidade dist_guarda/v_guarda < 12/v_bandido dist_guarda * v_bandido < 12*v_guarda
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.
Olá meus amigos nerds! Enquanto eu não consigo resolver dois problemas que vocês me pediram, para não ficar muito tempo sem escrever vamos resolver um probleminha fácil.
Hoje nós vamos brincar de somar frações, já que é isso que o problema SOMA13 - Soma de Frações pede para fazer. Mais especificamente, dadas duas frações, imprimir a soma delas.
Solução
A soma de duas frações é algo trivial. O único detalhe é que o problema pede para imprimir as frações na forma irredutível (simplificada), isto é, o numerador e o denominador do resultado devem ser primos entre si. Para simplificar uma fração basta dividir o numerador e o denominador da mesma pelo máximo divisor comum de ambos.
Olá meus amigos nerds! Hoje vamos ver que o conhecimento que adquirimos ao brincar em maratonas de programação pode nos ser útil no mundo real. Vou compartilhar com vocês um problema desafiador que tive que resolver essa semana no trabalho.
Essa semana estava trabalhando em um modelo para prever se um candidato seria uma boa indicação para uma dada vaga. Feliz ou infelizmente, o dataset que eu tinha a minha disposição é bem grande, mas a maior parte da informação contida nele está em forma de texto.
Parte da arte de se criar bons modelos de machine learning está em
escolher e usar as informações certas ao construir o modelo. Features textuais costumam conter bastante informação, entretanto extrair essa informação costuma ser problemático, já que as máquinas gostam de lidar com números.
Em particular, no modelo que eu estava criando, eu gostaria de usar as skills (descrições curtas de habilidades do candidato) presentes nos currículos. E, para minha felicidade, eu tinha a minha disposição uma tabela contendo tal informação.
Infelizmente eu não tinha essa mesma informação para as vagas, então decidi extraí-la da descrição das mesmas. Aí começa o problema.
Dada a descrição textual de uma vaga e uma tabela contendo skills (ex: mineração de dados, vendas, etc) eu gostaria de saber quais são as skills exigidas pela vaga.
O problema
Ué mas não é só dar um .find() das skills no texto e pronto? Onde está o problema desafiador? Aqui no blog já resolvemos alguns problemas de casamento de padrões mais difíceis que esse!
Bem meus amigos, o problema está na escala! Minha tabela de skills continha algo em torno de 1 milhão de registros. Além disso, eu também tinha alguns milhões de vagas o que torna a solução de força bruta inaplicável.
Problemas envolvendo escala costumam ser interessantes e esse não é diferente. Vamos ver como, mesmo algo que é simples quando lidamos com pequenos volume de dados, pode se tornar desafiador quando o tamanho dos dados realmente importa.
Para você ter uma ideia, a biblioteca de regex do python levou um ou dois minutos para compilar toda a tabela em padrões da forma p1|p2|...|pn. Além disso, o automato gerado por ela levava em torno de 1s para extrair os padrões de apenas uma vaga. 1s é o mesmo que infinito, se considerarmos que o SLA (tempo de resposta acordado) para a maioria das APIs que eu trabalho gira em torno de 200ms. Só para vocês terem uma ideia, usando-se uma máquina moderna levaríamos cerca de 10 dias só para extrair as skills de 1M vagas.
Ou seja, nosso problema é grande o suficiente para que a biblioteca padrão (consideravelmente otimizada) de uma linguagem moderna não seja suficiente.
Solução
Se todas as nossas skills fossem compostas apenas de uma palavra a solução de complexidade ótima (O(# palavras na descrição das vagas)) seria indexar nossas skills em uma tabela hash. Assim, para cada palavra na descrição da vaga, poderíamos verificar se ela esta presente no hash ou não.
O nosso problema é que as skills não são formadas apenas por uma palavra. Para contorná-lo basta criar uma árvore com as palavras das skills, onde cada nó da árvore representa uma palavra e existe uma aresta ligando dois nós se uma skill possui as duas palavras em sequência. Em outras palavras, a ideia para resolver esse problema é uma árvore de prefixos. Cada nó da árvore pode ter vários filhos, que podem ser mantidos em um hash para otimizar a busca.
Para buscar pelas skills então basta tokenizar o texto da vaga e para cada token ir andando com ele na árvore de prefixos de skills, verificando se aquele token gera ou não um match.
Implementação
Acho que essa é a primeira vez que uso uma de minhas linguagens preferidas para resolver um problema por aqui. O código Python abaixo implementa a ideia da árvore de prefixos.
Olá meus amigos nerds! Hoje nós vamos ajudar nossos amigos doutorandos a saber se eles acertaram a soma da conta do bar, já que é isso que o problema AJUDE14 - Ajude Aparecido pede para fazer. Mais especificamente, dada uma lista com n valores, verificar se os doutorandos acertaram a soma desses valores ou não.
Eu sei que esse problema é trivial, mas ele é só para eu praticar um pouquinho de Go.
Solução
Basta somar todos os números e ver se a soma bate com a soma fornecida. Mais fácil que isso, só mastigar água.
Olá meus amigos nerds! Hoje nós vamos ajudar Joãozinho a descobrir qual peça de seu quebra cabeça está faltando, já que é isso que o problema PECA7 - Peça Perdida pede para fazer. Mais especificamente, dadas n - 1 peças do quebra cabeça, numeradas de 1 a N, determinar a peça faltante.
Solução
A numeração das peças do quebra cabeça forma uma progressão aritmética, de primeiro termo 1, último termo N e razão 1. Assim, a soma de todas as numerações é N * (1 + N) / 2.
Por outro lado podemos somar as numerações das N-1 peças dadas. E se da soma total subtrairmos esse valor encontraremos o valor da peça faltante.
Olá meus amigos nerds! Hoje vos escrevo humildemente do México, infelizmente trabalhando, mesmo assim vamos brincar um pouco de resolver um probleminha fácil. Hoje vamos calcular o número de contêineres que um navio de carga suporta, já que é isso que o problema TRANSP11 - Transporte pede para fazer. Mais especificamente, dadas as dimensões do navio e dos contêineres calcular qual é o número máximo deles que podem ser acomodados no navio.
Solução
A solução do problema é bem simples. Como não podemos mudar a posição dos contêineres o máximo que podemos acomodar em uma direção é a medida do navio naquela direção dividida pelo tamanho correspondente de um contêiner. Assim basta multiplicar os valores obtidos para cada uma das três dimensões que temos nosso número máximo de contêineres.
Olá meus amigos nerds! Depois de uma longa pausa, estou de volta a ativa. Hoje vamos brincar de arredondar o troco, já que é isso que o problema MERCADO - Mercado do seu João pede para fazer. Mais especificamente, dada uma lista contendo os valores das vendas determinar o total vendido, bem como a diferença entre esse total e o total arredondando-se o valor das vendas.
A solução desse problema foi um pedido do nosso leitor Henryque Santos.
Solução
A solução do problema é bem simples. Basta ir somando os valores das compras e somando o valor arredondado em uma outra variável (aplicando o critério de arredondamento do seu João). No final é só fazer a diferença dos dois valores.
Implementação
Resolvi estudar um pouco de Go para ver se é uma boa linguagem, então vocês vão começar a ver um pouco de Go por aqui :)
Olá meus amigos nerds! Hoje vamos brincar de caça ao tesouro, já que é isso que o problema TESOUR11 - Caça ao tesouro pede para fazer. Mais especificamente, dado um mapa com pistas da localização do tesouro, verificar se é possível encontrá-lo.
Solução
A bem da verdade o problema mais parece com um jogo de campo minado do que com uma caça ao tesouro.
Pense em cada pista como um conjunto de possíveis posições para o tesouro. Para que a posição do tesouro seja determinada de maneira única é necessário que a interseção desses conjuntos tenha tamanho 1. Assim, basta para cada pista calcular as possíveis posições do tesouro e fazer a interseção de todos os conjuntos.
Olá meus amigos nerds! Hoje vamos relembrar um pouquinho de critérios de divisibilidade, já que é isso que o problema 2281. Rumo aos 9s pede para fazer. Mais especificamente, dado um número, queremos determinar se ele é divisível por nove.
Solução
O problema é bem simples, inclusive nos lembrando qual é o critério de divisibilidade por 9 (a soma dos dígitos o ser). Basta então implementar o critério dado.
Implementação
O único cuidado a ser tomado nesse problema é que o número inicial é potencialmente bem grande, tendo que ser manipulado como uma string.
Olá meus amigos nerds! Agora que já conseguiram "escutar" ondas gravitacionais vamos brincar de ajudar a NASA a determinar a temperatura média em uma certa região da Lua, já que é isso que o problema LUA - Temperatura Lunar pede para fazer. Mais especificamente, dada uma sequência de temperaturas determinar a maior temperatura média em um intervalo de tamanho m.
Solução
O problema é bem simples, basta ir iterando sobre a entrada e computando a temperatura média. É só lembrar que cada ponto do vetor é potencialmente um início para a janela de tamanho m da temperatura média.
Olá meus amigos nerds! Um dos objetivos desse blog é ser útil a quem está aprendendo, assim, hoje vamos resolver um problema a pedido por vocês.
Hoje vamos embalar tapetes, já que é isso que o problema TAPETE14 - Tapetes pede para fazer. Mais especificamente, queremos maximizar o valor da carga de tapetes dado que temos que transportar exatamente n tapetes que somam exatos l metros.
Solução
Olhando por cima esse problema parece o clássico problema da mochila, cada tenho uma mochila de tamanho n e quero enche-la com o máximo valor possível. Mas não é, uma vez que eu tenho a restrição de ter exatamente n objetos dentro dela. A solução para esse problema no entanto é mais simples.
Dado que o valor do tapete aumenta com o quadrado de seu comprimento é sempre melhor eu aumentar o tamanho de apenas um tapete, ou seja, embalar n-1 tapetes de tamanho 1 e um tapete de tamanho l - (n - 1) (correspondente ao comprimento restante da embalagem). Vou provar essa afirmação para n=2, mas ela é válida para qualquer n.
Sejam a e b os comprimentos dos dois tapetes que eu quero embalar. Logo:
a + b = l
Sendo que eu quero maximizar:
argmax(a^2 + b^2) a < l (o tamanho de todos os tapetes tem que ser maior que 0) b < l
mas a = l - b, logo:
l é uma constante. Como o coeficiente de b^2 é positivo o polinômio tem apenas um ponto de mínimo, ou seja, para maximiza-lo basta aumentar b. O maior valor possível de b é l - 1.
Assim para n qualquer teríamos a fórmula para o valor máximo = (l-n+1)^2+ (n - 1) [comprimento do maior tapete ao quadrado mais soma do valor dos n-1 tapetes de tamanho 1].
Implementação
Há um erro na indicação do tamanho da entrada. n, l <= 10^6 e não 106. Assim n^2 não cabe em 32 bits, logo temos que usar um inteiro de 64 bits (long long).
Olá meus amigos nerds! Esses dias notei que parte dos leitores do blog são iniciantes, então decidi voltar a postar soluções de problemas mais fáceis, afinal não queremos assustá-los! Não é mesmo?
Hoje vamos ver se nossos amigos corredores conseguem terminar uma maratona, já que é isso que o problema 11638. Maratona pede para fazer. Mais especificamente, dada a distância máxima que um corredor consegue percorrer, sem tomar água e a posição dos pontos onde é possível conseguir água. Determinar se ele consegue terminar a prova.
Solução
Basta ir verificando se a distância entre dois pontos de água consecutivos não é maior que a distância que o corredor consegue percorrer sem se hidratar. Após o último ponto de água também é necessário ver se o corredor consegue chegar até o final da prova. Lembrando que uma maratona tem um percurso de 42195 metros.
Olá meus amigos nerds! Hoje vamos achar o melhor lugar para uma reserva ambiental de macacos prego, já que é isso que o problema 814. Macaco-prego pede para fazer. Mais especificamente, dadas as coordenadas de várias zonas retangulares de um mapa determinar a interseção de todas elas.
Solução
No caso geral esse problema seria bem difícil, mas como só temos retângulos com os lados paralelos aos eixos ele fica mais fácil. Só saber que os retângulos se interceptam também é muito fácil, mas não basta para resolvermos o problema! Precisamos ser capazes de calcular a interseção.
Sejam A e B os dois retângulos que queremos interceptar. Construa um retângulo que contenha A e B e que tenha como pontos extremos os pontos mais distantes de cada retângulo (ou seja, ordena as coordenadas de A e B e pegue o primeiro e último elementos do vetor). Os pontos restantes da ordenação formam um segundo retângulo C que está contido no super retângulo. Esses pontos formam a interseção de A e B, caso ela exista. Para saber se a interseção existe, veja se tanto A quanto B contém o centro de C.
Olá meus amigos nerds! Hoje vamos brincar de escrever quadrados mágicos, já que é isso que o problema 11013. Quadrado mágico pede para fazer. Mais especificamente, dada uma matriz verificar se a soma de todas as suas linhas, colunas e diagonais é igual e que ela contém todos os números de 1 a n^2, sendo n a ordem da matriz.
Solução
Basta somar as linhas e colunas e ver se tem o mesmo resultado. Além disso, também é preciso verificar se todos os números de 1 a n^2 estão na matriz.
Implementação
Note que, dado o tamanho dos números da entrada, o resultado da soma pode não caber em um int.
Olá meus amigos nerds! Hoje vamos descobrir quem ganhou o mundial de Formula 1, já que é isso que o problema 8314. Fórmula 1 pede para fazer. Mais especificamente, dadas as ordens de chegada dos pilotos em diversas corridas e o sistema de pontuação determinar quem foi o campeão ao fim da temporada.
Solução
Esse é um simples problema de ordenação. Some as pontuações de cada piloto ordene o resultado e imprima aqueles que tiverem mais pontos.
Implementação
Quando olho para um código feio como esse meu de muitos anos atráz fico feliz de ver que eu melhorei pelo menos um pouquinho :P
