3776. Árvore Genealógica

Olá meus amigos nerds, passado o ano novo é hora de retomarmos nossa rotina de resolver problemas. E para vocês não dizerem que sou um cara mau, irei começar o ano com um problema fácil, porém interessante.

Hoje vamos resolver o problema 3776. Árvore Genealógica, que nos pede para, dada uma árvore genealógica, dizer quem são os parentes mais distantes.

Primeiramente, gostaria de dizer que esse problema é muito semelhante ao 11011. Desafio cartográfico, que foi o primeiro problema resolvido nesse blog. Seria isso uma coincidência de inicio de ano?

Solução

O problema define o grau de parentesco da seguinte maneira:

grau(A, B) = 0, se A = B
grau(A, B) = 1 + min(grau(pai(A), B), grau(A, pai(B))), se A != B

A recursão acima, e o fato de se tratar de uma árvore genealógica, praticamente nos implora para que modelemos esse problema utilizando grafos, onde os vértices são as pessoas e as arestas são uma relação direta de parentesco. 

Se pensarmos bem, a recursão acima nos conta que os dois parentes mais distantes são aqueles que fazem parte das extremidades do diamêtro da árvore. Isso nos conduziria a uma solução muito semelhante a do problema 11011, ou seja duas buscas em profundidade, sendo a segunda feita a partir do vértice mais distante da raiz da primeira busca.

Entretanto, é interessante notar, que o tamanho máximo da entrada é pequeno (1000) o que nos faz pensar que uma solução um pouco menos elaborada (mais força bruta) seja suficiente para resolver o problema. Bem e qual seria essa solução? Hora, para cada par A, B de pessoas calcular seu grau de parentesco e imprimir aquelas que tem o maior grau. Algoritmicamente falando:

Seja pessoas o conjunto de todos os vértices da árvore

maiorGrau = 0

for A in pessoas

  for B in pessoas

    g = grau(A, B)

    maiorGrau = max(g, maiorGrau)

Onde grau(A,B) é descrito pela recursão citada no início do problema. Observe que no caso médio a complexidade de grau(a,b) é logarítmica (altura da árvore), sendo assim meu algoritmo de força bruta tem complexidade de O(n² * log(n)) sendo n o número de pessoas. E isso é bom o suficiente para resolver esse problema. 

Observe, que caso quiséssemos modelar o problema como o diâmetro do grafo, teríamos que tratar o fato de a entrada poder ser uma floresta de árvores (um grafo desconexo). Problema que não existe no caso de uma solução por força bruta. Isso mostra a importância de entendermos os compromissos entre simplicidade e viabilidade (em ralação aos limites de entrada) de nossas soluções.

Implementação

Observem, como eu represento a floresta de árvores como um vetor, armazenando apenas o antecessor de cada nó.

Observem, também, que mesmo minha implementação tendo uma complexidade O(n³) no pior caso, ela ainda assim é aceita no spoj.

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.

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

11011. Desafio cartográfico

Primeiramente, bem vindo ao Spoj Tricks! Aqui você poderá encontrar a solução comentada para a maioria dos problemas do spoj.

Nesse post vamos falar do problema 11011. Desafio cartográfico. De modo resumido o problema pede que dado um mapa de cidades ligadas por estradas, determine a distância entre o par de cidades mais distantes.

Modelagem da Solução

O problema pede basicamente o diâmetro do grafo onde as cidades representam os vértices e as estradas as arestas.

Achar o diâmetro de um grafo qualquer não é um problema tão simples. Entretando, observando as outras restrições dadas no enunciado podemos simplificar nosso problema:

(a) todas as estradas são de mão dupla;
(b) todas as estradas possuem 1km de comprimento;
(c) toda estrada conecta apenas duas cidades,
(d) dadas duas cidades quaisquer A e B, só existe uma única maneira de chegar em A partindo de B, e vice-versa.

Ou seja, nosso grafo sempre será uma árvore, e calcular o diâmetro de uma árvore é um problema bem mais simples.

Diâmetro de uma Árvore

O diâmetro de um grafo (que no nosso caso é uma árvore) é o maior caminho mínimo do grafo. A solução mais ingênua para esse problema seria calcular todas as distâncias entre todas as folhas do grafo e escolher a maior delas. Entretanto podemos fazer muito melhor que isso. Para tanto, observe que:

O vértice mais distante de um vértice u qualquer do grafo é uma das extremidades do diâmetro do grafo.


Para simplificar, e sem perda de generalidade, vamos supor que o diâmetro do grafo é único. Ou seja, existe exatamente um par de vértices {u, v}, tal que o comprimento do caminho mínimo entre u e v seja o maior do grafo. É fácil de ver que tanto u, quanto v são folhas do grafo.

Pegue qualquer nó w, vamos mostrar (por contradição) que o vértice mais distante dele é u ou v. Suponha que o vértice encontrado é diferente, digamos z. Vamos considerar dois casos.

Primeiro suponha que w esteja no caminho de u para v. Sem perda de generalidade, suponha que o caminho wu não têm sobreposição com o caminho wz. Temos:

dist(w, z) ≥ dist(w, v). Mas sabemos que dist(w, z)  ≥ dist(w, u).
dist(u, z) = dist(u, w) + dist(w, z) ≥ dist(u, w) + dist(w, v) = dist(u, v). Isto contradiz a suposição de que d(u, v) é o diâmetro original da árvore.

Suponha agora que w não esteja sobre o caminho de u para v. Temos que ou o caminho wz se sobrepõe com o caminho uv ou está separado.

Caso existe sobreposição:
Considere o vértice y mais próximo de W e sobre a sobreposição dos caminhos. Sem perda de Assim, dist(y, z)  ≥ dist(y, v).

Como dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) = dist(u, v). O que leva novamente a uma contradição já que por hipotese {u, v} é  o diâmetro original da árvore.

Se os caminhos não se sobrepõem, tem que haver dois vértices um no caminho uv e outro no caminho wz que são os mais próximos, sejam estes vértices x e y. Assim dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) > dist(u, x) + dist(x, v) = dist(u, v). Daí a suposição de que {u, v} é o diâmetro é contrariada.

cqd.


Desse modo, o cálculo do diâmetro de uma árvore pode ser feito usando-se duas buscas em profundidade (ou em largura), uma delas (partindo de qualquer vértice) para achar o vértice mais distante, que será uma das extremidades (u ou v) do diâmetro. E a outra partindo-se do vértice encontrado (u ou v) para se calcular efetivamente o diâmetro do grafo.

Complexidade da solução

Tanto a busca em profundidade quanto em largura têm complexidade O(E), sendo E o número de arestas do grafo.

Implementação

O código abaixo implementa a solução apresentada acima.

Se você copiou e colou o código acima você foi recompensado com um grande segmentation falt. Embora correto, o código tem um problema difícil de perceber. Ele é passível de um estouro de pilha! A pilha de ativação não é infinita, na realidade ela é bem pequena, e nosso código pode no pior caso  fazer 10^6 chamadas a função dsf (lembre-se 2 ≤ N ≤ 10^6) causando assim um estouro de pilha que acaba por nos apresentar a exclarecedora mensagem de seg falt :(. O código abaixo resolve esse problema emulando uma pilha de ativação e removendo a recursão da função dsf.