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.

11611. Homem, elefante e rato

Olá meus amigos nerds, hoje o bicho vai pegar. Como prometido, essa semana, humildemente, trago a vocês um problema bem interessante. 

Hoje vamos brincar de Homem, Elefante e Rato nome que os criativos Nlogôlianos deram para nosso famoso pedra, papel, tesoura, já que é isso que o problema 11611. Homem, elefante e rato nos pede. Mais especificamente, o problema pede que computemos a frequência de cada símbolo (homem, elefante, rato) após cada rodada do jogo. Parece fácil, não é, mas há uma particularidade: Os habitantes da Nlogônia, que são estrategistas natos de Homem (pedra), Elefante (papel) e Rato (tesoura), utilizam a seguinte técnica no campeonato nacional, realizado todos os anos: começam sempre jogando Homem até o momento em que este símbolo causa empates com a maioria dos oponentes. Eles então trocam sua estratégia para o símbolo que ganha daquele que usavam anteriormente. Assim, os jogadores vão mudar de Homem para Elefante, depois para Rato, depois de volta a Homem. Nossa tarefa é contabilizar quantos jogadores irão utilizar cada símbolo após cada rodada.

Solução

Após ter lido o problema, você deve estar pensando: seu nerd burro esse problema é extremamente fácil! Basta eu ter um array com a opção atual de cada jogador e simular o que acontece a cada rodada e pronto.

Seja opcaoJogador um array em que cada elemento representa a opção (pedra, papel, tesoura) atual do jogador

Seja operacoes as operações que temos que simular a cada rodada

for operacao in operacoes

  Sejam inf e sup os limites, inferior e superior

   if operacao == mostra

     imprime  a frequencia de homem, elefante rato em opcaoJogador[inf : sup]

   else

     for i de inf a sup

       atualiza opcaoJogador[i]

Você está certo! Eu sou burro! O código acima realmente resolve o problema. Mas ele não leva em conta um detalhe muito importante: escala! Analisar o tamanho da entrada que seu algoritmo é capaz de lidar é de extrema importância. Uma rápida olhada, em nosso pseudo código, nos mostra que ele tem complexidade O(#operacoes * len(sup-inf)). Agora vamos supor, que nosso código vai ser rodado em uma máquina que consegue executar 10^9 operações por segundo, como len(#operações) = 10^5 e len(sup-inf)=10^6 nosso computador imaginário levaria mais ou menos uns 100s para rodar nosso código, ou seja, não passariamos no limite de tempo 1s (TLE).

Uma pequena divagação, se pararmos para pensar muitos dos problemas interessantes que as grandes empresas de TI, como Google e Microsoft, enfrentam não são complicados, o que torna esses problemas desafiadores muitas vezes é a escala monstruosa do tamanho dos dados que eles tem que lidar.

Voltemos ao nosso problema! A escolha correta da estrutura de dados a ser usada pode transformar um problema impossível em um problema trivial. E é isso que eu vou fazer agora. Existe uma estrutura de dados chamada segment tree que é capaz de executar as operações de consulta em um intervalo e atualização de um intervalo em O(log n). Se substituirmos o array opcaoJogador, no pseudo código acima, por uma segtree nosso problema com TLE está resolvido. Isso mesmo, a alteração de uma estrutura de dados nos levaria a uma otimização de 100x no tempo de execução de nosso problema!!

Esse seria o momento em que eu explicaria o que é uma segtree e como implementá-la. Mas essa é uma estrutura por demais interessante, que certamente merece umas duas ou três horas do seu tempo para estudá-la. Então vamos fazer o seguinte, vou deixar para você como desafio estudar um pouco sobre uma segtree e tentar resolver esse problema. No fim da semana vou postar uma explicação detalhada de como se implementar uma segtree. Mas só para não te deixar muito no ar:

Uma segtree é uma árvore binária, cada uma de suas folhas representa um intervalo que tem alguma propriedade que pode ser compartilhada com outros intervalos. Cada nó interno representa a união de alguns intervalos folhas e é capaz de sumarizar os intervalos folhas. Uma segtree é capaz de realizar duas operações importantes para o nosso problema:

• Buscar o estado de um intervalo. Por exemplo, no nosso problema, eu poderia perguntar a segtree qual é a frequência de Elefantes no intervalo do primeiro ao último participante. Essa pergunta seria respondida em O(log n).
• Atualizar o estado de um intervalo inteiro. Por exemplo, no nosso problema, eu poderia pedir a segtree que alterasse a figura colocada de Elefante para Rato, de todos os participantes no intervalo do primeiro participante ao participante n/2. Essa operação, também, seria realizada em O(log n).

Implementação

É claro que eu não deixaria você sem a implementação do problema de hoje. Observe como o código da segtree é delicado, qualquer erro é bastante difícil de ser debugado.

Veja também a pequena otimização com o uso da macro __attribute__((always_inline)); para forçar algumas funções a ser inline. Além disso, observe a alocação estática de memória, também com o objetivo de ganhar tempo.

Pensei em implementar a segtree de modo genérico (template) mas isso geraria mais um nível de complexidade, então para tornar o código mais simples não fiz isso.

8776. Batalha naval

Olá meus amigos nerds, hoje eu peço desculpas a vocês, mas falarei rapidamente sobre um probleminha fácil. Afinal daqui a pouco começa o melhor jogo do ano, a final da Copa do Brasil entre Cruzeiro e Atlético. E como todo bom brasileiro, eu não quero perder essa. Semana que vem, prometo que trago um problema bem mais interessante.

Enquanto esperamos o jogo vamos brincar um pouco de batalha naval? Uma vez que é isso que o problema 8776. Batalha naval nos pede para fazer.  Mais especificamente, o problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determinar o número de navios do outro jogador que foram destruídos.

Solução

Esse problema é bem simples. Para cada posição do mapa, é só verificar se há um navio afundado naquela posição e contar esse navio. Mais algoritmicamente, temos:

cnt = 0
para cada posição do mapa
    if há um navio afundado que ainda não foi contado
        cnt += 1

Para verificar se há um navio afundado em uma posição do mapa é suficiente fazer uma busca em largura a partir daquela posição, ou seja:

vizinhos = fila([posição atual])
afundou = true
while vizinhos não está vazio
    noAtual = vizinhos.top()
    if noAtual não está dentro do mapa
        continue
    if noAtual está intácto
        afundou = false
    else if noAtual recebeu um tiro
        marcar noAtual como visitado
        vizinhos += vizinhos do noAtual 

Implementação

11646. Olimpíadas

Olá meus amigos nerds! Vendo os problemas que nós já resolvemos aqui no blog, nesses seis meses, descobri que não tínhamos resolvido sequer um único problema de ordenação. E como ordenação é um dos temas mais importantes e úteis de computação resolvi fazer esse post para amenizar nossa falha.

Hoje vamos falar de olimpíadas, já que o problema 11646. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas de ouro. Se houver empate entre países no número de medalhas de ouro, o melhor colocado entre esses é o país que conseguiu o maior número de medalhas de prata. Se houver empate também no número de medalhas de prata, o melhor colocado entre esses é o país que recebeu o maior número de medalhas de bronze. Se ainda assim houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.

Solução

Esse é um típico problema de ordenação, basta ordenar os países de acordo com a regra dada e pronto. O único cuidado que devemos ter é usar um algoritmo de ordenação rápido, isto é, um algoritmo com complexidade O(n*log n) para não recebermos um TLE.

Esse problema não teria graça nenhuma, caso não falássemos um pouco sobre os algoritmos de ordenação. Sendo assim decidi explicar um pouco sobre o Quicksort (principal e mais rápido algoritmo de ordenação para a maioria dos problemas de ordenação).

O Quicksort é um algoritmo de divisão e conquista. Sua estratégia consiste em rearranjar os elementos de modo que os elementos "menores" que um dado elemento, chamado pivô, precedam esse elemento, enquanto os elementos "maiores" que o pivô o sucedam. Em seguida o Quicksort ordena recursivamente as duas sublistas definidas pelo pivô e as extremidades do array.

De forma mais algorítmica:

1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

O Quicksort é um algoritmo tão famoso que nós deveríamos, não só entende-lo, como também, ser capazes de implementá-lo. Se você nunca tentou implementar o Quicksort, eu o convidaria a tentar.

Uma boa referência, não só a respeito de ordenação, mas também de algoritmos e estruturas de dados de um modo geral é o livro do Cormem. Se você quer se aprofundar um pouco no assunto, eu recomendaria a leitura do capítulo 2 desse livro.

Implementação

Observe como o problema fica simples usando o sort da lib algorithm :)