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 :)

Dica Nerd - A Arte do Debuging

Olá meus amigos nerds, gostaram do pequeno desafio de debugging que eu deixei em minha última postagem? Segue ai a solução:

Vocês provavelmente não tiveram dificuldades e não devem ter gastado mais do que 5 minutos para resolver o desafio. Mesmo assim, hoje vou deixar uma dica bastante útil a esse respeito. A Udacity tem um excelente curso sobre debugging (e o melhor, ele é gratuito). Eu mesmo já fiz o curso e achei que ele me foi muito útil. O curso  começa bem básico, mas vai aumentando sua profundidade chegando a falar de algumas técnicas avançadas de debugging como por exemplo o delta debugging. Se você tentou e teve dificuldade em resolver o desafio da última postagem, esse curso pode ser muito útil para você. O Udacity, se você não sabe, é uma plataforma de educação online que oferece cursos de qualidade em várias áreas do conhecimento. Vale a pena conferir!

1824. Monitorando a Amazônia

Olá meus amigos nerds, vocês acharam que essa semana não ia ter um probleminha? Se sim, se enganaram! Eu queria ter postado esse probleminha na quarta, mas vocês hão de convir comigo que seria uma pena perder os jogos dos dois melhores times do Brasil da atualidade... Deixando de papo furado, que a diversão comece!

Hoje vamos resolver o problema 1824. Monitorando a Amazônia, que nos pede para verificar se é possível enviar uma mensagem de uma estação de comunicação central para todas as outras estações de comunicação espalhadas pela amazônia. Sendo que, cada estação se comunica apenas com as duas estações mais próximas a ela.

Solução

Conceitualmente esse não é um problema difícil. Se pensarmos a rede de comunicação como sendo um grafo (direcionado), basta verificarmos se todos os vértices são alcançáveis, a partir do vértice que representa a estação central. Isso pode ser feito, facilmente, usando-se uma busca em profundidade. 

Note que, o problema pede apenas para verificar se é possível enviar uma mensagem a partir da estação central. Caso se pedisse para verificar a viabilidade da comunicação entre qualquer par de estações, o problema seria um pouco mais complexo. Nesse caso teríamos que verificar se o grafo possuía apenas um componente fortemente conectado, o que poderia ser feito usando-se o algoritmo de Tarjan.

O seguinte algoritmo resolve o problema

calcule a distância entre cada par de estações
Seja G um grafo onde os vértices representam as estações
para cada estação
    Sejam a e b as estações mais próximas a est
    adicione a aresta est -> a a G
    adicione a aresta est -> b a G
faça uma busca em profundidade a partir do vértice que representa a estação principal marcando todos os vertices visitados
if todos os vértices foram marcados
    print "All stations are reachable."
else
    print "There are stations that are unreachable."

Implementação

Observe que evitamos o uso de números de ponto flutuante trabalhando com o quadrado da distância. Em alguns problemas isso pode ser bem útil.

Observe ainda, que abrimos mão de alguma elegância no código em favor de não armazenar as distâncias entre cada par de estações. Sendo assim vou aproveitar e deixar um pequeno desafio para você: o código abaixo contém 2 bugs, quanto tempo você levaria para encontrá-los?

Obs: Caso você tenha dificuldade em encontrar os bugs use o diff :)

1747. Números de Dinostratus

Olá meus amigos nerds, hoje irei falar de um problema bastante divertido, principalmente se você gosta de coincidências arqueológicas.

Existe uma classe de números conhecidos como números de Dinostratus, que aparecem em várias ruínas antigas. No problema 1747. Números de Dinostratus, iremos aprender a identificar se um número é ou não é um número de Dinostratus.

Mais especificamente, um número n é um número de Dinostratus se existe uma matriz M de dimensão 3 x 3 formada por 9 inteiros distintos com a propriedade que para toda posição (i,j) com i=1,...,3 e j=1,...,3 da matriz o elemento mi,j é múltiplo dos seus vizinhos mi-1,j, mi-1,j-1 e mi,j-1 (quando existirem) e  m3,3 = n.

Um exemplo de um número de Dinostratus é 36 pois:

1   2   4

3   6   12

9   18  36

Solução

O exemplo acima nos dá uma pista de como resolver o problema. Observe que, todos os números dá matriz devem ser necessariamente formados por fatores primos de n (ex: m(3,3)=36 tem que ser múltiplo de  m(2,2)=6 que por sua vez deve ser múltiplo de m(2,1)=3 e m(1,2)=2). Observe ainda que:

|2^0 * 3^0 =1   |  2^1 * 3^0 =2   |  2^2 * 3^0 =4  |

|2^0 * 3^1 =3   |  2^1 * 3^1 =6   |  2^2 * 3^1 =12 |

|2^0 * 3^2 =9   |  2^1 * 3^2 =18  |  2^2 * 3^2 =36 |

Vamos então tentar a seguinte hipótese: a solução do problema depende de alguma propriedade relacionada ao número de fatores primos de n. Se isso é verdade então é possível classificar um número como sendo de Dinostratus baseado no número de fatores primos. 

Bem, já sabemos que se temos 2 fatores primos e ambos tem expoente igual a dois então n é um número de Dinostratus. Ex: 36 = 4 * 9 = 2^2 * 3^2  (observe que eu poderia trocar o 2 e o 3 por outros números e mesmo assim a propriedade da matriz formar um número de Dinostratus se manteria, experiente para ver)

O que eu vou fazer agora é estabelecer se n é um número de Dinostratus quando n tem 1, 2, 3, 4, 5 ... fatores distintos, farei isso através de exemplos.

n tem 1 fator distinto

ex: 256 = 2^8

1  2   4

8  32 128

16 64 256

Então o expoente do fator tem que ser >= 8

n tem 2 fatores 

do número 36 já sabemos que ambos os fatores tem que ter expoente mair ou igual a 2, por outro lado

96 = 32 * 3 = 2^5 * 3 também é um número de Dinostratus.

1  2  4

3 12 24

6 48 96

Então se um dos expoentes for maior ou igual a 5 n também será um número de Dinostratus.

n tem 3 fatores 

ex: 60 = 4 * 3 * 5 = 2^2 * 3 * 5 = 60

1  2  4

3  6  12

15 30 60

Então o expoente de pelo menos um fator tem que ser >= 2.

n tem 4 ou mais fatores

ex: 210 = 2 * 3 * 5 * 7

1  2  14

3  6  42

15 30 210

Então n sempre será um número de Dinostratus.

Do exposto acima retiramos o seguinte algoritmo

fatore n

if n tem 4 ou mais fatores responda sim

if n tem 3 fatores e um deles tem expoente maior que 1 responda sim

if n tem 2 fatores e um deles tem expoente maior que 4 responda sim

if n tem 2 fatores e ambos tem expoente maior que 1 responda sim

if n tem 1 fatores e um deles tem expoente maior que 7 responda sim

else responda não

Implementação

1737. Mesa da Sra Montagny!

Olá meus amigos nerds, enquanto alguém não inventar um remédio mágico para garganta inflamada (minha garganta agradeceria) vamos resolver mais problemas.

O problema de hoje é o 1737. Mesa da Sra Montagny! e nele vamos ajudar a sra Montagny a decidir se é possível dispor todos os seus convidados numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.

Solução

Como não vejo a hora de me deitar para descansar vou resolver problema de forma bem rápida. O problema nos fornece as relações de amizade dos convidados, isso sugere fortemente que a utilização de grafos é uma boa ideia para o problema.

Para que seja possível dispor os convidados, não pode haver um convidado que possua amigos dos dois lados da mesa. Se pensarmos os lados da mesa como conjuntos de vértices, qual tipo de grafo tem essa propriedade? Grafos bipartidos. Então o problema nos pede para identificar se o grafo é bipartido. Caso o grafo formado pelas relações de amizade seja bipartido, a sra Montagny poderá dispor seus convidados na mesa, caso contrário não.

Identificar se um grafo é bipartido é fácil. Basta fazer uma busca em profundidade, marcando os vértices de um dos conjuntos de uma cor e os do outro conjunto com outra. Caso eu encontre um vértice que deveria ter uma cor mas ele tem outra então o grafo não é bipartido, caso contrário ele é.

P.S. prometo que semana que vem falo de um problema mais interessante, mas hoje minha garganta me pede para fazer outras coisas rsrs

Implementação

6291. Problem

Olá meus amigos nerds, vocês devem estar se perguntando o que eu estou fazendo aqui agora, já que eu já postei um problema hoje. É que eu vi um problema tão legal que eu não consegui me segurar.

O problema em questão é o seguinte 6291. Problem e o legal nele é que ele não tem enunciado! Você conseguira resolve-lo?

Solução

Olhe bem para a entrada e tente encontrar algum padrão. Dê uma de Mcgiver e improvise! Tenho certeza que você conseguirá matar a charada. Esse problema é tão divertido que eu vou esconder a solução para não perder a graça...

9002. Bingo!

Olá meus amigos nerds, ainda não é hoje que vou apresentar a vocês meu recomendador de problemas (quero melhorar o algoritmo de recomendação um pouco mais primeiro). Mesmo assim, hoje vou resolver um outro problema que foi recomendado por ele.

Hoje vamos brincar de bingo, já que é isso que o problema 9002. Bingo! nos pede. Albert, Charles e Mary (ACM rsrs) resolveram criar um novo tipo de bingo, nesse jogo são sorteadas, com reposição, duas bolas e o número sorteado é a diferença absoluta desses números. Como ACM não são bons de matemática eles nos pediram para verificar se dado um conjunto de bolas é possível se sortear todos os números.

Solução

Ao ler esse problema pensei que ele poderia ser interessante, mas ao olhar os limites da entrada fiquei decepicionado (n <= 90), ou seja, qualquer algoritmo de força bruta seria bom o suficiente.

Resolver esse problema usando força bruta é trivial. O seguinte algoritmo (com complexidade O(n^2)) faz isso:

para cada par (x, y) de bolas
    compute a diferença entre x e y
    armazene essa diferença

verifique se os números de 0 a N estão no conjunto das diferenças armazenadas

Implementação

Essa dica é meio trivial, mas vai lá assim mesmo: Observe como eu usei o vetor possiveisDiffs para armazenar todas as diferenças de modo mais eficiente.

3597. Par ou Ímpar

Olá meus amigos nerds, tenho boas notícias para hoje. Vocês se lembram que eu comentei aqui que eu estava implementando um recomendador de problemas, para facilitar a vida de quem usa o spoj. Pois é, essa semana consegui dar mais um pequeno passo e implementar alguns algoritmos mais simples para fazer isso. E nada melhor do que testar um algoritmo implementando outro, não é verdade? Assim o problema que vamos resolver hoje nos foi sugerido por um dos algoritmos de recomendação que implementei. Não vou falar do recomendador hoje, pois pretendo dissecar esse assunto mais a fundo nas próximas semanas.

O problema de hoje é o 3597. Par ou Ímpar e ele nos pede que ajudemos Joaõzinho e Maria a resolverem a confusão que eles fizeram em uma brincadeira de par ou ímpar. Eles jogaram muitas vezes par ou ímpar e anotaram os resultados em cartões. Em todos os jogos João escolheu ímpar (e, conseqüentemente, Maria escolheu par). Durante os jogos cada jogador escreveu nos cartões quantos dedos ele/ela mostrou, usando uma carta para cada jogo. O objetivo deles era ser capar de re-checar os resultados depois, procurando pelos cartões de cada jogo. Entretanto, no fim do jogo os cartões de cada jogador estavam fora de ordem o que impedia que eles contassem exatamente quantas partidas cada um ganhou.

Mais especificamente, o problema nos pede que dado o conjunto de números escritos nos cartões,  determinar o número mínimo de jogos que Maria certamente ganhou.

Solução

Observe que é impossível saber quantos jogos cada um ganhou exatamente. Entretanto, independente de quantos jogos cada um ganhou o seguinte invariante deve se manter:

jogos_ganhos_maria + jogos_ganhos_joao = n

onde n é o total de jogos disputados.

Como é muito difícil calcular diretamente o número mínimo de jogos que Maria ganhou, vou resolver o problema reverso: calcular qual é o máximo de jogos que João pode ganhar. Esse tipo de abordagem as vezes é bem útil, sendo aplicada em vários problemas de otmização.

Na situação que Maria ganha o mínimo de jogos possíveis, João necessariamente deve ganhar o maior número de jogos possíveis, assim:

min_jogos_ganhos_maria + max_jogos_ganhos_joao = n

ou

min_jogos_ganhos_maria  = n - max_jogos_ganhos_joao


Só um lembrete:
par + par = par
par + ímpar = impar
ímpar + par = impar
ímpar + ímpar = par

Maximizar o número de jogos ganhos é fácil. Lendo o lembrete acima, você provavelmente já matou ou problema. Basta pensar que cada vez que João colocou um número par, Maria colocou um ímpar, e vice versa. Assim:

max_jogos_ganhos_joao = max_casamentos(joao_par, maria_impar) + max_casamentos(joao_impar, maria_par)

max_casamentos(joao_par, maria_impar) é fácil de calcular, e é igual ao mínimo entre joao_par e maria_impar. Assim:

max_jogos_ganhos_joao = min(joao_par, maria_impar) + min(joao_impar, maria_par)

logo

min_jogos_ganhos_maria  = n - min(joao_par, maria_impar) - min(joao_impar, maria_par)

E essa é justamente a solução do problema.

Implementação

1745. Recuperação

Olá meus amigos nerds, hoje estou com preguiça então falarei de um problema fácil. Mentirinha, estou é fazendo um recomendador de problemas para o spoj, em breve falarei mais sobre ele. 

Por incrível que pareça existem dezenas de problemas fáceis no spoj. E o problema 1745. Recuperação é um deles. Nesse problema, é pedido que dado uma lista de inteiros se encontre um inteiro nessa lista tal que ele seja igual a soma dos outros inteiros que o antecedem na lista.

Solução

De forma mais formal queremos um número a[k] tal que:

a[k] = a[1] + a[2] + ... + a[k-1]

Então basta percorrer a lista e testar essa propriedade. É o que o algoritmo abaixo faz:

soma = 0
for cada elemento a[i] da lista
    if  a[i] == soma
        numeroPedido = a[i]
        break;
    soma += a[i]

Basta então imprimir numeroPedido

Implementação

Observe que  numeroPedido deve ser inicializado com um valor inválido (menor que a menor soma possível, ou maior que a maior soma possível), se você usar numeroPedido = -1 (eu fiz isso da primeira vez :P) você vai levar merecidamente um belo de um wrong answer.

2616. Caixeiro-Viajante B

Olá meus amigos nerds, mesmo estando com um pouco de calos nos olhos devido ao jogo de ontem da seleção, estou aqui hoje para resolver um probleminha com vocês.

Hoje vamos falar do problema 2616. Caixeiro-Viajante B que nos pede para traçar a rota de um caixeiro viajante de modo que ele gaste o mínimo possível com passagens de trem para visitar todos os seus clientes. Mais especificamente, o problema só nos pede o valor mínimo gasto com as passagens.

Solução

O primeiro ponto a destacar, é que esse não é o clássico problema do caixeiro viajante, tão estudado quando se fala em problemas NP. Ainda bem, já que isso facilita bastante as coisas.

Como em outros problemas que já resolvemos aqui, vamos pensar em uma modelagem usando grafos. Nesse problema isso é bem simples, as cidades seriam os vértices e as ferrovias as arestas.

O problema nos afirma que há apenas um caminho ligando cada par de cidades, então nosso grafo é, na realidade, uma árvore. Cada cidade em que há um cliente do caixeiro precisa ser visitada, isso significa que cada ferrovia que o caixeiro passar será usada 2 vezes (ida e volta).

A forma de minimizar o gasto com passagens é não percorrer uma ferrovia mais do que uma duas vez (ida e volta), já que há apenas 1 caminho entre qualquer par de cidades. Isso significa que, cada vez que o caixeiro chegar a uma "encruzilhada" que tem caminhos para mais do que uma cidade ele deve visitar a primeira delas, voltar até a encruzilhada e partir dali direto para a próxima cidade. Observe que o que acabei de descrever é simplesmente percorrer o grafo em uma busca em profundidade.

Problema resolvido? Não! Pode haver cidades que não possuem clientes do caixeiro e que não estão no caminho de outras cidades, ou seja, que não precisam ser visitadas, mas que provavelmente seriam contadas caso você fizesse uma busca em profundidade simples. Mas isso é simples de resolver. Para contornar esse pequeno detalhe basta fazer a busca em profundidade primeiro (enraizando a árvore pelo nó que representa a cidade inicial do caixeiro) e ir percorrendo os caminhos das cidades de destino para a raiz (ou seja, fazendo o caminho oposto), marcando as arestas para que elas não sejam contadas novamente.

Implementação

1389. Pedido de Desculpas

Olá meus amigos nerds, hoje falaremos um pouco de um dos problemas mais clássicos de programação dinâmica, o problema da mochila. E isso, graças ao nosso amigo Cuca, que saiu para jogar futebol e se esqueceu de se encontrar com sua namorada. 

Mais especificamente, o problema 1389. Pedido de Desculpas nos pede que ajudemos Cuca a escrever um pedido de desculpas com o maior número de repetições da palavra desculpa. Para isso Cuca nos forneceu um conjunto pré escolhido de frases e quer usar essas frases para preencher um cartão de desculpas que cabe apenas um número limitado de caracteres.

Solução

O problema aqui é bastante simples, apenas se você já estudou um pouco de algoritmos (e consequentemente, conhece o problema da mochila booleana). Observe que podemos mapeá-lo da seguinte forma:

cartão = mochila
tamanho das frases = peso dos objetos
# de desculpas por frase = valor ($) dos objetos

Mochila Booleana

O problema da mochila é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.

O problema da mochila é um dos 21 problemas NP-completos de Richard Karp. Isso quer dizer que sua solução tem complexidade O(2^n). Observe que, esse problema pode ser resolvido como um problema de decisão, ou seja, para cada objeto, decida se ele deve ou não ser colocado na mochila. Uma forma simples de se decidir pela adição ou não de um objeto é gerando todos os subconjuntos de objetos e escolhendo o subconjunto de maior valor:

melhorSolucao=0
foreach subconjunto dos objetos
    valor = calcule o valor desse subconjunto
    if valor > melhorSolucao
         melhorSolucao = valor

Felizmente, existe uma solução pseudo polinomial para o problema. Suponha que temos n objetos, sendo que o i-ésimo objeto tem valor v[i] e peso p[i]. Podemos usar uma estrutura recursiva para resolver o problema da mochila booleana por programação dinâmica. A ideia é guardar em uma tabela (mochila) as soluções das (sub)instâncias do problema. A tabela é definida como:

mochila[# de objetos][capacidadeMáximaMochila] =  maior valor alcançado com uma mochila de capacidade capacidadeMáximaMochila  e itens 1,...,# de objetos

Lembrando que ou um item é necessário para alcançar o valor ótimo, ou não é, então podemos expressar o valor dos elementos de nossa tabela como:

mochila[i][peso] = max(
               mochila[i-1][peso], //o elemento i não é usado pela solução ótima
               v[i] + mochila[i-1][peso-p[i]] //o elemento i é usado pela solução ótima
              )

como condição de contorno caso p[i] > peso => mochila[i][peso] = mochila[i-1][peso]

Observe que essa solução tem complexidade O(# de objetos * capacidadeMáximaMochila). Mas, anteriormente eu não afirmei que o problema da mochila é NP-completo? Se você ficou curioso a esse respeito aqui e aqui você poderá encontrar a justificativa.

Dei aqui apenas uma explicação superficial sobre o problema da mochila, se você não o conhecia e achou interessante uma ótima referência para uma leitura mais aprofundada é o livro do Cormen (Introduction to Algorithms).

Implementação

1890. Mário

Olá meus amigos nerds, hoje iremos ajudar nosso amigo Mário a resolver seus problemas. Não me pergunte, que Mário? Pois, não resistirei fazer aquela piadinha infame, ainda mais que o problema de hoje fala de armários.

O problema 1890. Mário nos pede para ajudar nosso amigo Mário a organizar seus armários, de modo a atender de melhor seus clientes. Mais especificamente, dado um conjunto de armários livres e numerados (e com rodinhas) nos é pedido que calcule qual é o menor número de movimentações de armários que deve ser feito para que esses armários livres sejam dispostos de modo a haver n armários livres em sequência.

Solução

Esse é um problema interessante, pois a princípio ele parece bem difícil, mas na realidade é fácil. Observe, inicialmente, que o número de movimentos (trocas) necessários para dispor n armários vazios em sequência é menor que n (pelo menos um armário vazio já estará no lugar). Observe ainda, que a sequência de armários vazios necessariamente começará em um dos L armários (obvio). Se decidirmos começar nossa sequência de armários a partir do armário i, teremos que trocar de posição todos os armários ocupados a partir de i até (i+n). Assim, se contarmos quantos armários ocupados existem a partir de cada i em L e escolhermos o menor desses números teremos nossa resposta. Essa  é precisamente a ideia do algoritmo abaixo, onde contamos o número de armários desocupados (que é complementar ao número de armários ocupados) uma vez que essa é a informação que a entrada do problema nos fornece.

maiorNumArmariosDesocupados = 0

for i in (L-n) //L-n é a última posição em que eu posso iniciar uma sequência de n armários

    Seja x o número de armários desocupados existentes dentro da janela [i, i+n]
    if x > maiorNumArmariosDesocupados
        maiorNumArmariosDesocupados = x

numTrocas = n - maiorNumArmariosDesocupados

Implementação

Observe que em minha implementação eu armazeno apenas as posições dos armários vazios. Isso me permite otimizar um pouco o meu for.

19960. Telemarketing

Olá meus amigos nerds, em primeiro lugar desculpem-me por meu hiato, na última semana estive trabalhando, juntamente com alguns amigos, em um sistema de recomendação de problemas para o spoj e acabei ficando sem tempo de conversar com vocês.

Hoje vamos contar quantas ligações faz um atendente de telemarketing, já que é isso que o problema 19960. Telemarketing nos pede.

O problema nos fornece uma lista de ligações que devem ser feitas na ordem fornecida, juntamente com o tempo necessário para se fazer cada ligação e nos pede que contemos quantas ligações cada um dos n atendentes de telemarketing devem fazer.

Solução

Lendo o problema, é possível perceber que para saber quantas ligações cada atendente fez é necessário simularmos as ligações feitas. O problema então reside em fazer essa simulação de modo eficiente.

Uma forma simples de simularmos as ligações é simularmos o que ocorre em cada instante de tempo, obviamente simular cada instante de tempo além de ser desnecessário é muito custoso. Felizmente, podemos restringir nossa simulação a dois momentos:

• inicio de uma ligação - momento que um vendedor se torna indisponível
• fim de uma ligação - momento em que um vendedor se torna ocioso

O seguinte algoritmo realiza a simulação, onde uma fila de prioridades é usada para manter de modo eficiente qual será o próximo vendedor ocioso (e portanto o responsável por fazer a ligação)

Seja Ti o tempo gasto em ligações pelo vendedor i.
para cada vendedor
   Ti = 0
Adicione cada vendedor a fila de prioridade f, ordenada pelo tempo Ti
para cada ligação
   Seja v o vendedor que está no topo da fila
   Esse vendedor realiza essa ligação (incremente o número de ligações que ele fez)
   Seja Tl o tempo da ligação
   Ti += Tl

Esse tipo de simulação apresentada no algoritmo acima é conhecida como simulação de eventos discretos (você pode saber mais sobre ela aqui).

Implementação

Observe que usei apenas inteiros nessa simulação, já que 30*1.000.000 cabe em 32 bits (int).

3830. Soma

Olá meus amigos nerds, como é costume, estou aqui hoje para resolver nosso problema da semana. Infelizmente, o problema que vamos resolver é muito fácil, mas como nosso objetivo é resolver todos os problemas do spoj isso não importa muito. Não é mesmo?

Hoje vamos somar números, já que é isso que o problemas 3830. Soma nos pede para fazer. Mais especificamente, esse problema nos pede que, dada uma lista de N inteiros, encontre a soma de todos eles.

Fácil não, um simples for resolve...

Vamos brincar um pouco mais?  Será que é possível resolver esse problema se a tecla + do seu computador estivesse estragada? Certamente que sim, e é o que eu vou mostrar agora.

Modelagem

O segredo para resolver esse problema é lembrar que soma e subtração podem ser feitas usando se operações lógicas. Vamos dividir o nosso problema de somar em dois problemas:

1. Somar sem considerar o vai 1
2. Calcular e somar o vai 1

Vamos tentar somar dois números de 1 bit sem considerar o vai 1. Sejam a e b esses números:

a     b     a+b sem vai 1
1     1              0
1     0              1
0     1              1
0     0              0

É possível perceber que o resultado a+b é igual a 1 quando ou exclusivamente a ou ou exclusivamente b forem 1. Assim a soma sem se considerar o vai 1 pode ser feita como a xor b.

Calcular o vai 1 pode ser feito da mesma forma:

a     b     vai 1
1     1       1
1     0       0
0     1       0
0     0       0

Ou seja o vai 1 pode ser representado como a and b.

Pronto agora é só somar o a+b sem vai 1 com o vai 1. Opa, mas voltamos ao mesmo problema de antes. Para contornar esse empecilho, podemos usar recursão, como feito no pseudocódigo abaixo.

soma_recursivo(a, b)
    if (b == 0) return a //condição de parada
    somaSemVai1 = a xor b
    vai1 = a and b
    vai1 = vai1<<1 //o vai 1 sempre deve ser somado ao próximo bit
    return soma_recursivo(somaSemVai1, vai1)

Implementação

Dica do Peão Programador - Hibernate e Cache

Olá meus amigos nerds, hoje estou aqui para falar de problemas do mundo real, que vocês podem ter que lidar quando estiverem desenvolvendo algum sistema de grande porte.

Outro dia eu precisava fazer uma atualização em algumas tabelas de um banco de dados, para acomodar algumas melhorias em um dos sistemas que eu ajudo a desenvolver.

Eu tinha a opção de gerar o sql de atualização na unha ou usar o Hibernate para isso. Como a atualização não era simples, optei por fazê-la usando o Hibernate (sou preguiçoso como todo bom cientista da computação)

(Se você não conhece o Hibernate, ele é um framework muito útil para desenvolvimento de aplicações (java) que precisam se comunicar com bancos de dados relacionais. A grosso modo, ele faz o mapeamento dos objetos da sua aplicação para as tabelas do seu banco de dados, gerando para você o sql das consultas de modo transparente.)

Você deve estar se perguntando qual o problema. Isso qualquer peão programador consegue fazer. O problema estava no número de objetos (linhas das tabelas) que eu tinha que atualizar (alguns milhares). É claro que, como um bom nerd, eu estava atento a esse fato. E para evitar problemas de memória, eu havia implementado meu código de modo a fazer a atualização de forma paginada, ou seja, eu carregava apenas uma parte dos objetos a serem atualizados de cada vez na memória. 

Testei meu código usando um dump do banco de dados e para minha surpresa ele começou a demorar muito a executar. Meu instinto nerd me dizia, deu merda! Então eu voltei ao código e o instrumentei (adicionei informações de tempo ao log da execução) de modo a obter informações de onde estava o problema. Eis que encontrei o seguinte comportamento:

Tempo de execução do método de atualização sobre a 1ª página de dados 1s

Tempo de execução do método de atualização sobre a 2ª página de dados 2s

Tempo de execução do método de atualização sobre a 3ª página de dados 4s

Tempo de execução do método de atualização sobre a 4ª página de dados 6s

...

Você é capaz de me dizer onde está o problema? Tanto o tamanho das páginas, quanto a natureza dos dados que o método de atualização lidava não mudavam. Sendo assim, o tempo de execução de uma página deveria ser mais ou menos constante. Então como explicar esse resultado? Além do mais, não poderia ser problema de paginação de memória, já que eu havia tomado esse cuidado de antemão. Correto? Então o que poderia ser?

Minha análize do problema me dizia: isso cheira a problema de memória! Para confirmar ou refutar essa hipótese, verifiquei o consumo de memória do java. Estava mais alto do que seria esperado! Era problema de memória. Mas não deveria ser meu código que o está causando o problema, pois eu havia sido cuidadoso, inclusive eu havia incluído instruções de flush para garantir que eu teria apenas os dados de uma página na memória. 

Então formulei a seguinte hipótese: O Hibernate esta se tornando mais lento ao executar uma página, pois ele não deve estar fazendo o flush dos objetos já atualizados. Para confirmar ou refutar essa hipótese, recorri ao google e pesquisei o comportamento do Hibernate. Eis que em algum site eu encontrei a informação de que se você der um flush no Hibernate, fica a critério dele liberar memória ou não! Se eu quisesse forçar o Hibernate a fazer o flush e limpar sua memória interna eu deveria usar o método session.clear().

Adicionei uma chamada a session.clear(), testei novamente meu atualizador e voilá. Problema resolvido! 

Lembra da primeira execução do meu atualizador, pois é, ela ainda estava rodando quando terminei de resolver o problema. Ela gastou no final das contas uma hora e pouco para executar, enquanto a versão corrigida gastou menos de um minuto. (Deixei terminar de executar só para poder me gabar depois do speedup da alteração que eu fiz no código do meu atualizador :P)

A lição que fica aqui é que você sempre deve conhecer a arquitetura interna dos frameworks, bibliotecas, etc, que você usa. Esse conhecimento salva vidas e te poupa muita dor de cabeça.

P.S.: Observe que em nenhum momento eu saí colocando breakpoints no meu código e dando step in ou step out em algum debuger visual. A técnica de debug que eu usei para resolver esse problema (de fazer suposições, colher dados e rejeitar ou confirmar as suposições até encontrar o bug) é muito útil na solução de diversos problemas. Em uma outra oportunidade irei falar mais sobre ela.

12930. Pizza

Olá meus amigos nerds, hoje escolhi resolver um problema especialmente saboroso. Hoje vamos falar  de pizza. Já que o problema 12930. Pizza, nos pede para ajudar nosso amigo Rodrigo a escolher o maior número de pedaços de pizza que ele pode comer.

As pizzas de nosso problema tem dois ingredientes, um que Rodrigo gosta (cebola) e outro que ele não gosta (azeitona). Rodrigo deseja pegar fatias consecutivas da pizza de tal forma que estas contenham a maior diferença possível entre as quantidades de cebolas e azeitonas. Para isso, ele contou quantas cebolas e quantas azeitonas haviam em cada fatia e subtraiu os dois valores, nessa ordem. Assim, sempre que uma fatia contiver mais cebolas que azeitonas, ela recebe um número positivo, e caso contrário, um número negativo. Uma fatia cujo número seja zero contém o mesmo número de cebolas e azeitonas. Nossa tarefa nesse problema é maximizar essa diferença com a condição de que Rodrigo pode escolher apenas fatias consecutivas.

Solução

Resolver esse problema de modo eficiente é rasoavelmente difícil. Tão difícil, que eu planejava falar dele na semana passada, mas não consegui resolvê-lo de forma eficiente no tempo que eu dispunha para lidar com ele.

A dificuldade desse problema está no fato da pizza ser circular. Se assim não fosse a solução seria computar a soma máxima (um problema bem clássico de programação dinâmica).

O que nos impede de mapear esse problema para o problema da soma máxima é que não sabemos como escolher o início do array de modo que todos os pedaços de pizza que compõe a soma máxima sejam consecutivos, já que a pizza é circular.  Observe o exemplo abaixo:

Na pizza {1, -2, 3} as fatias  3 e 1 são consecutivas, mas não aparecem em elementos consecutivos do array. Se rodarmos o algoritimo da soma máxima sobre esse vetor encontrariamos a soma 3 que é menor que a maior soma possível que é 4 (é só computar a soma máxima desse vetor {-2, 3, 1}, que representa o mesmo vetor circular inicial). 

Observe, entretanto, que se conseguirmos adaptar o algoritmo da soma máxima para trabalhar com um vetor circular nosso problema está resolvido.

Uma primeira observação é que, necessariamente há uma fatia que se escolhida como primeiro elemento  do array faz com que todos os pedaços pertencentes a soma máxima sejam consecutivos (no exemplo acima basta escolher -2 ou o 3 como início do array). Lembre-se, os pedaços de pizza são consecutivos, o que faz com que eles pareçam não consecutivos é a nossa escolha de como linearizar a pizza.

A escolha de por qual pedaço de pizza começamos nosso array pode ser feita por foça bruta, ou seja, tentando cada pedaço da pizza como sendo o início do array. Isso conduz a uma solução correta para o problema, uma vez que se a soma pedida será a soma máxima de um dos n arrays, mais precisamente, a resposta será a maior das somas máxima. Essa solução tem complexidade quadrática (lembre-se soma máxima pode ser resolvido em O(n) usando-se programação dinâmica). Infelismete, uma solução O(n^2) não é factível para o problema, devido ao tamanho da entrada (10^5^2 é um bocado de tempo).

Então a pergunta é: dá para fazer melhor que isso? Dá sim, abaixo vou mostrar uma solução linear para o problema. E a ideia dessa solução é que não precisamos do passo de força bruta do algoritmo apresentado acima.

Soma máxima em um array circular

Dado um conjunto contendo n números (positivos e negativos) arranjados de forma circular, encontrar a maior soma obtida a partir de elementos consecutivos desse conjunto.

Considere o seguinte array circular {a1, a2, ...,ai,..., aj,..., a(n-1), an}, e suponha que todos os elementos entre ai e aj pertencem a soma máxima. Então a soma máxima nesse vetor será:

ai + a(i+1) + ... + a(j-1) + aj (1)

ou será

aj + a(j+1) + ... + an + a1 + ... + ai (2)

A soma em (1) pode ser obtida usando-se o algoritmo clássico (para um vetor comum) da soma máxima.

A soma em (2), é um pouco mais complicada, mas pode ser calculada da seguinte forma.  Seja S a soma de todos os elementos do array. Multiplique todos os elementos do array por -1 (observe que isso não altera o modulo de nenhuma soma, apenas o valor absoluto dela). Sendo assim, se aplicarmos o algoritmo clássico da soma máxima nesse novo vetor teremos como resultado - (a(i+1) + a(i+2) + ... + a(j-1))*. Se da soma de todos os elementos do array original, nós subtrairmos * obteremos a soma (2).

Finalmente, a soma máxima dos elementos do array circular será max((1), (2)).

Uma explicação mais detalhada dessa solução pode ser encontrada aqui.

Implementação