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.
