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.