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!