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 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. Quando se mora sozinho, cozinhar passa a ser um problema, principalmente se você não gosta de jogar comida fora e não tem muito tempo livre (eu que o diga kkk). Uma solução para isso é comer besteiras, tipo miojo. Como somos muito bonzinhos, hoje vamos ajudar o pobre do João a preparar miojos. Já que é isso que o problema 3826. Miojo nos pede para fazer. Mais especificamente, dadas duas ampulhetas (os únicos 'relógios' que ele tem), capazes de medir tempos a e b diferentes e o tempo T necessário para se fazer o miojo, determinar qual será o tempo total gasto para preparar o miojo, incluindo o tempo gasto esperando as ampulhetas estarem em um estado capaz de medir o tempo exato do cozimento do miojo.
Solução
Podemos pensar nesse problema como um problema de decisão. Qual das ampulhetas deve ser virada em seguida para que sejamos capazes de medir exatamente T minutos? Como não podemos inferir a resposta para essa questão, temos que tentar todas as possibilidades e ver qual delas resulta em um menor tempo total.
Os únicos instantes que nos interessam seriam os momentos em que viramos uma ampulheta. Podemos começar virando a ampulheta a, a ampulheta b, ou ambas ao mesmo tempo. Quando uma ampulheta acaba de contar, temos duas opções: (1) vira-la e deixar que ela recomece a contar ou (2) virar as duas ampulhetas, assim a outra ira contar o tempo correspondente a parte da areia que já caiu em seu compartimento inferior. Fazendo-se um backtracking, baseado nessas condições somos capazes de calcular o tempo total.
A condição de parada é que uma das ampulhetas seja capaz de medir exatamente T minutos com a areia remanescente em sua parte superior.
Possivelmente esse problema possui uma solução mais elaborada usando-se teoria dos números (mmc, mdc, etc), mas como a solução por força bruta não é difícil de implementar, resolvi testa-la primeiro e ela se mostrou suficientemente boa para o problema receber um acept.
Olá meus amigos nerds, vocês sabiam que há uma lenda que diz que quando alguém conseguir resolver o problema das torres de Hanói usando 64 discos o mundo acabará? Hoje, vamos descobrir se essa lenda é verdadeira ou não ao resolver o problema 842. Torres de Hanói.
O conhecido quebra-cabeça consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.
Na realidade esse problema não nos pede para resolver o desafio das torres de hanói, inclusive ele nos apresenta a solução do mesmo e nos pede para que computemos o número de operações necessárias para solucionar o quebra cabeça.
Hanoi(N, Orig, Dest, Temp)
se N = 1 então
mover o menor disco do pino Orig para o pino Dest;
senão
Hanoi(N-1, Orig, Temp, Dest);
mover o N-ésimo menor disco do pino Orig para o pino Dest;
Hanoi(N-1, Temp, Dest, Orig);
Solução
Do algorítimo acima tiramos a seguinte relação de recorrência:
Observe que, após "resolvermos" a expressão acima i vezes ela poderia ser escrita da seguinte forma:
Hanoi(N) = 2^i * Hanoi (N - i) + [sum 2^(x - 1) para x de 1 a i]
quando i == N temos:
Hanoi(N) = 2^N * Hanoi (0) + [sum 2^(x - 1) para x de 1 a N]
Mas Hanoi(0) = 0 já que se não houver peças não precisamos mover nada. Por outro lado [sum 2^(x - 1) para x de 1 a N] = 2^(N-1) - 1. Logo:
Hanoi(N) = 2^(N-1)
É interessante notar, que há uma outra solução bem obvia para o problema: Implementar e instrumentar o algoritmo acima e contar o número de movimentos na força bruta. Como você pode ver, pela ordem de grandeza do número de operações, essa solução certamente seria muito ineficiente e receberia um TLE.
Só por curiosidade, a lenda é verdadeira, se alguém gastasse 1 segundo para mover um disco, 2^64 = 1.8446744e+19 segundos é muito mais tempo que a idade do universo.
Olá meus amigos nerds, hoje vamos brincar de estudar uma função recursiva, já que é isso que o problema 1831. f91 nos pede. Mais especificamente o problema nos fornece uma função recursiva e pede que computemos o resultado.
Solução
Você deve estar se perguntando o que tem de interessante nesse problema. Sim, esse é um problema razoavelmente fácil, mesmo assim tem alguns detalhes legais que podemos explorar. O problema define a seguinte função:
Se N ≤ 100, então f91 (N) = f91 (f91 (N + 11));
Se N ≥ 101, então f91 (N) = N - 10
Obviamente se implementarmos essa função já temos o problema resolvido:
f91(n) if n > 100 return N-10 else return f91(f91(N+11))
Agora vamos tentar ser um pouco mais espertos e deduzir analiticamente o resultado dessa recursão. É ai que essa função fica divertida, pois ela sempre retorna 91 para todos os números menores ou iguais a 101. Desenvolvendo a função temos:
Observe que n+11, n+2*11, n+3*11 é uma sequência extritamente crescente. Em algum momento, o valor dessa sequência ultrapassara 100 mas será menor ou igual a 111 (estamos somando 11). Nesse momento começaremos a subitrarir 10 e somar 11 a esse número, ou seja, duas chamadas consecutivas dessa função terão o efeito de somar 1 ao número (que ainda será menor que 100), exemplo:
Olá meus amigos nerds, hoje vamos ajudar o diretor de uma escola a montar uma comissão para realização de sua tradicional festa junina, já que é isso que o problema 1353. Festa Junina nos pede para fazer.
Mais especificamente, dada uma lista de alunos e as relações de ódio entre eles (que triste rsrs), determinar qual é o número máximo de integrantes que a comissão da festa pode ter, se ela for formada pelos alunos da lista.
Solução
Esse é um problema bastante interessante. Uma solução baseada em testar todos os conjuntos de alunos possíveis é bem fácil de ser pensada, entretanto apresenta o problema de o número de partições de um conjunto ser exponencial (2^n). Tentemos então encontrar soluções melhores!
Vamos resolver esse problema usando uma modelagem por grafos. Cada vértice do grafo representa um aluno da lista. Existe uma aresta entre dois vértices, caso um dos alunos que aqueles vértices representam odeio o outro. Em outras palavras, esse grafo representa as relações de ódio entre os alunos. Observe que para uma comissão ser válida não podem haver arestas no grafo que liguem os membros da comissão, ou seja, as comissões válidas são os conjuntos independentes existentes no grafo. Logo o problema se resume a achar o conjunto independente máximo do grafo.
Achar o conjunto independente máximo é o problema dual de achar a clique máxima (um conjunto independente é uma clique (sub grafo completo) no grafo complementar). Mas por que eu estou falando isso? Se você já estudou um pouco de teoria de complexidade, você já deve ter ouvido falar que o problema da clique máxima é NP-completo. Sendo assim, estamos diante de um problema que a melhor solução que conhecemos tem complexidade exponencial.
Assim a ideia que mencionei no primeiro parágrafo apesar de ineficiente é ótima. Observando que o tamanho máximo da entrada é 20 mesmo uma solução assim é capaz de passar no tempo no spoj. O seguinte algoritmo implementa tal ideia:
construa o grafo de relações de odio entre os alunos tamanhoMaximoGrupo = 0 para cada conjunto de alunos Seja S esse conjunto para cada a em S para cada b em S se existe a aresta a->b ou b->a no grafo conjunto invalido tamanhoMaximoGrupo = max(tamanhoMaximoGrupo, |S|)
Implementação
A solução abaixo utiliza um backtracking para implementar o algoritmo acima. Ela é basicamente, um algoritmo de enumeração de conjuntos.
Uma ideia um pouco mais elaborada é utilizar um bitset para representar os conjuntos. A implementação abaixo é baseada nisso. A ideia é iterar de 1 a 2^n e utilizando a representação binária do iterador como a representação do conjunto. Embora um pouco mais eficiente ela também é mais propícia a erros, já que operações com bits as vezes são traiçoeiras.
Olá meus amigos nerds, passado o ano novo é hora de retomarmos nossa rotina de resolver problemas. E para vocês não dizerem que sou um cara mau, irei começar o ano com um problema fácil, porém interessante.
Hoje vamos resolver o problema 3776. Árvore Genealógica, que nos pede para, dada uma árvore genealógica, dizer quem são os parentes mais distantes.
Primeiramente, gostaria de dizer que esse problema é muito semelhante ao 11011. Desafio cartográfico, que foi o primeiro problema resolvido nesse blog. Seria isso uma coincidência de inicio de ano?
Solução
O problema define o grau de parentesco da seguinte maneira:
grau(A, B) = 0, se A = B
grau(A, B) = 1 + min(grau(pai(A), B), grau(A, pai(B))), se A != B
A recursão acima, e o fato de se tratar de uma árvore genealógica, praticamente nos implora para que modelemos esse problema utilizando grafos, onde os vértices são as pessoas e as arestas são uma relação direta de parentesco.
Se pensarmos bem, a recursão acima nos conta que os dois parentes mais distantes são aqueles que fazem parte das extremidades do diamêtro da árvore. Isso nos conduziria a uma solução muito semelhante a do problema 11011, ou seja duas buscas em profundidade, sendo a segunda feita a partir do vértice mais distante da raiz da primeira busca.
Entretanto, é interessante notar, que o tamanho máximo da entrada é pequeno (1000) o que nos faz pensar que uma solução um pouco menos elaborada (mais força bruta) seja suficiente para resolver o problema. Bem e qual seria essa solução? Hora, para cada par A, B de pessoas calcular seu grau de parentesco e imprimir aquelas que tem o maior grau. Algoritmicamente falando:
Seja pessoas o conjunto de todos os vértices da árvore
maiorGrau = 0
for A in pessoas
for B in pessoas
g = grau(A, B)
maiorGrau = max(g, maiorGrau)
Onde grau(A,B) é descrito pela recursão citada no início do problema. Observe que no caso médio a complexidade de grau(a,b) é logarítmica (altura da árvore), sendo assim meu algoritmo de força bruta tem complexidade de O(n² * log(n)) sendo n o número de pessoas. E isso é bom o suficiente para resolver esse problema.
Observe, que caso quiséssemos modelar o problema como o diâmetro do grafo, teríamos que tratar o fato de a entrada poder ser uma floresta de árvores (um grafo desconexo). Problema que não existe no caso de uma solução por força bruta. Isso mostra a importância de entendermos os compromissos entre simplicidade e viabilidade (em ralação aos limites de entrada) de nossas soluções.
Implementação
Observem, como eu represento a floresta de árvores como um vetor, armazenando apenas o antecessor de cada nó.
Observem, também, que mesmo minha implementação tendo uma complexidade O(n³) no pior caso, ela ainda assim é aceita no spoj.
Olá meus amigos nerds, não se preocupem que eu ainda não esqueci que estou devendo a vocês um post explicando melhor o funcionamento de uma segtree. Como ainda não consegui fazer um post que me agradasse isso vai ficar na minha todo list por mais um tempo.
Enquanto isso, vamos brincar de dobraduras? Hoje vamos ajudar os amigos de Zezinho a resolver o desafio proposto por ele. Como Zezinho gosta muito de matemática, resolveu inventar um quebra-cabeça envolvendo dobraduras. Zezinho definiu uma operação de dobradura D que consiste em dobrar duas vezes uma folha de papel quadrada de forma a conseguir um quadrado com 1/4 do tamanho original. Depois de repetir N vezes esta operação de dobradura D sobre o papel, Zezinho cortou o quadrado resultante com um corte vertical e um corte horizontal e desafiou seus colegas a dizer em quantos pedaços o papel ficou dividido.
Solução
Nesse tipo de problema, geralmente, é possível deduzir uma fórmula fechada para a resposta. E é precisamente isso que vamos fazer agora. Para isso, vamos usar uma técnica que você, provavelmente, já ouviu falar em suas aulas de algoritmos: indução finita.
para N = 0 => 4 pedaços (o papel não é dobrado)
para N = 1 => 9 pedaços para N = 2 => 25 pedaços
...
Agora vem a parte difícil, que é sacar qual é o padrão oculto nessa sequência de números. A pergunta é: o que 4, 9 e 25 tem em comum. Bem em primeiro lugar eles são quadrados perfeitos. Ok, mas qual a relação deles com n? Ou melhor, qual seria a relação de 2, 3 e 5 com 0, 1 e 2?
Observe que a cada dobra do papel o número de pedaços de papel dobra. Isso sugere que a relação existente tem que ser uma relação exponencial. Depois de pensar um pouco (ou melhor, depois de esperimentar muito) a gente chega a seguinte relação:
f(n) = (2^n + 1)^2
Agora é que começa a aplicação da indução finita. Observe que a fórmula acima vale para N = 0, pois:
f(0) = 4 = (2^0 + 1)^2
... Poderíamos continuar supondo que a fórmula vale para N e tentando a partir disso resolver a fórmula para N+1. Entretanto, nesse problema isso é bem difícil e eu vou deixar isso para vocês pensarem (dica: comece pensando em quantos pedaços o papel fica dividido após as dobras e depois pense me quantos pedaços cada dobra é dividida quando cortamos o papel). Em uma maratona de programação, o que você faria se tivesse boa confiança na sua fórmula mas não conseguisse prova-la formalmente? Sim, isso mesmo, você implementaria o problema já que ele não é difícil de implementar e submeteria. Nesse caso, se você fizer o mesmo, você será recompensado com uma resposta certa.
Implementação
Observe que, como a entrada é pequena, podemos pré calcular todos os valores e armazena-los em um vetor. Nesse problema isso não faz diferença, mas em outros problemas com tempo de execução mais apertado isso pode ser a diferença entre seu problema passar ou tomar TLE.
Olá, desculpem-me meus amigos nerds mas essa semana não tive tempo de resolver nenhum problema junto com vocês (problemas mais desafiadores me atacaram). Mesmo assim, para não deixar passar em branco a semana mais divertida da copa (valeu Costa Rica e Chile), passei aqui para resolver mais um probleminha.
Investir no mercado de ações não é algo simples, normalmente exige tempo e atenção. Mesmo assim, nesse problema, vamos ter a oportunidade de ver como nosso amigo João investe de uma forma engraçada e peculiar. O problema 11753. Investindo no mercado de ações 1 nos pede para ajudar João a determinar em quantas partes ele deve dividir seu dinheiro para que ele obtenha um investimento mais seguro (pelo menos na opinião dele).
Modelagem
O problema nos pede para contar em quantas partes precisamos dividir N reais até que tenhamos apenas partes de no máximo k reais. Sendo que a divisão deve ser feita recursivamente em duas partes iguais a ⌊N/2⌋ e ⌈N/2⌉, até restar apenas partes de no máximo k reais.
Observe que, uma leitura atenta do problema já nos indica um algoritmo para resolvê-lo. Seja conta(N), o número de partes que devemos dividir N, assim temos nossa recursão:
conta(N) = conta(⌊N/2⌋) + conta(⌈N/2⌉) se N > k
conta(N) = 1 se N <= k
Pronto, basta implementar essa recursão e o problema de João está resolvido. Sem graça, né? Então, vamos explorar um pouco mais esse problema? Vamos brincar de derivar a complexidade da nossa solução?
É possível achar uma fórmula fechada para essa recursão, entretanto fazer isso é complicado, pois teríamos que lidar com ⌊N/2⌋, o que não é simples. Observe, entretanto que a solução para um problema de tamanho N depende da solução de um problema de tamanho N/2, então a complexidade de nossa recursão é provavelmente logarítmica.
Para comprovar nossa hipótese de que o número de passos de nossa recursão é logarítmico, suponha que N seja uma potência de 2 (N=2^h), assim ⌊N/2⌋ e ⌈N/2⌉ serão iguais, logo temos:
logo nossa recursão terá profundidade h. Mas h = log2(N). Assim a complexidade do nosso algoritmo é logarítmica. E como você já deve ter ouvido, em algum lugar, que algoritmos de complexidade logarítimica são eficientes vamos implementá-lo, então!
Implementação
O código abaixo, implementa nossa solução. Observe que ⌊N/2⌋ e ⌈N/2⌉ são simples de calcular (basta saber se N é par ou ímpar!).
