Pesquisa do Mestre Pardal - Um recomendador de problemas para o Spoj

Olá meus amigos nerds, para fechar esse ano com chave de ouro, hoje eu trago um grande presente de Natal para vocês.

Você, que resolve problemas de maratona freqüentemente, em algum momento já deve ter se aborrecido por tentar resolver problemas que são muito fáceis ou muito difíceis para o seu nível atual. 

Quando se está treinando para competições, o ideal é resolver problemas que estão um pouco acima do seu nível atual. Problemas muito fáceis não acrescentam quase nada, já os muito difíceis acabam te desmotivando um pouco. 

Infelizmente, no spoj, por exemplo, o único jeito de você saber se um problema está a sua altura é tentando resolve-lo. Assim, na busca por problemas interessantes, você acaba tendo que ler vários problemas inúteis, o que consome considerável tempo. 

Aplicações web que possuem grande quantidade de itens, sendo que apenas alguns poucos são do interesse do usuário (por exemplo o Netflix ou a Amazon) costumas possuir a funcionalidade de um sistema de recomendação para auxiliar o usuário. Pensando nisso e na espereça de contribuir com o aprendizado geral da nação de nerds cientistas da computação, eu decidi construir um recomendador de problemas para o spoj. Você que acompanha o blog regularmente já deve saber disso, já que eu já havia citado isso aqui. 

Hoje eu tenho o prazer de anunciar o Spojrec meu sistema de recomendação de problemas para o spoj.

Como funciona o Spojrec?

Depois de ter testado o recomendador de problemas, você curioso nerd cheio de sede por conhecimento deve estar se perguntando: mas como ele funciona?

Para matar um pouco da sua curiosidade. Vou falar um pouco dos dois algoritmos de recomendação que rodam por traz do spojrec.

O algoritmo de recomendação principal do spojrec usa a seguinte ideia:

a) Usuários de alto nível resolvem problemas difíceis

b) Problemas difíceis só são resolvidos por usuários de alto nível.

Como você deve ter observado, meu jovem padawan, a recorrência acima é circular, para achar os usuários de alto nível eu preciso saber quais são os problemas difíceis e para saber quais são os problemas difíceis eu preciso dos usuários de alto nível. Então como resolver esse problema?

Podemos pensar no problema, como um problema de grafos, onde os usuários e problemas formam um grafo bipartido. Nesse grafo uma aresta representaria uma tentativa acertada de solução e  os vértices seriam os problemas e usuários. Problemas apontados por muitos usuários fortes seriam problemas difíceis, inversamente usuários de alto nível seriam aqueles que conseguiram resolver problemas   difíceis. Como você pode observar a indagação anterior persiste, eu só descrevi o problema de uma forma mais algorítmica.

Mas o que eu ganho em descrever o problema dessa forma. A resposta está em um parente próximo do page rank (o famoso algoritmo responsável pelo surgimento do google). O Hits um algoritmo que é capaz de lidar com essa recorrência circular e atribuir pesos aos problemas e usuários. Em outras palavras, o algoritmo principal do spojrec é o uso do hits aplicado ao grafo descrito acima :)

Pensando também nos iniciantes o spojrec implementa um segundo algoritmo de recomendação, um pouco mais simples que o primeiro. A ideia desse algoritmo é resolver a recorrência acima de uma outra forma. Ele utiliza como medida da dificuldade de um problema o número de usuários que o resolveram corretamente. Na hora de recomendar ele seleciona os problemas mais próximos da média dos 10 problemas mais difíceis que o usuário já resolveu.

Se você ainda está curioso e quiser ver o código fonte, me mande uma mensagem ou deixe um comentário que eu ficarei feliz de compartilha-lo com você.

Bem espero que tenham gostado! Maratonistas usem e abusem dessa nova ferramenta que eu fiz com carinho para vocês! Um feliz Natal e próspero ano novo para todos!

11762. Poodle

E aqui estamos para resolver o segundo problema fácil do dia. E por sinal, um problema bem engraçado, já que ele é uma paródia do google.

O problema 11762. Poodle nos pede para escrever poodle com tantas letras O quantas são as páginas encontradas na busca de uma máquina de busca imaginária chamada poodle (qualquer semelhança é mera coincidência rsrsrs).

Solução

Calcule o número de páginas e imprima o poodle.

Implementação

2928. Ele está impedido

Olá meus amigos nerds, depois de um pequeno hiato estou aqui de volta para resolver mais problemas.

Hoje vamos resolver dois problemas fáceis. O primeiro deles é o problema 2928. Ele está impedido que nos pede para verificar se existe um jogador impedido, sendo que são dadas as posições dos atacantes e defensores.

Solução

Basta achar a posição do penúltimo defensor e comparar essa posição com a posição de cada atacante. Se o atacante estiver mais próximo da linha do gol que o penúltimo defensor ele está impedido.

Implementação

817. Dobradura

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.