11753. Investindo no mercado de ações 1

Olá, desculpem-me meus amigos nerds mas essa semana não tive tempo de resolver nenhum problema junto com vocês (problemas mais desafiadores me atacaram). Mesmo assim, para não deixar passar em branco a semana mais divertida da copa (valeu Costa Rica e Chile), passei aqui para resolver mais um probleminha.

Investir no mercado de ações não é algo simples, normalmente exige tempo e atenção. Mesmo assim, nesse problema, vamos ter a oportunidade de ver como nosso amigo João investe de uma forma engraçada e peculiar. O problema 11753. Investindo no mercado de ações 1 nos pede para ajudar João a determinar em quantas partes ele deve dividir seu dinheiro para que ele obtenha um investimento mais seguro (pelo menos na opinião dele).

Modelagem

O problema nos pede para contar em quantas partes precisamos dividir N reais até que tenhamos apenas partes de no máximo k reais. Sendo que a divisão deve ser feita recursivamente em duas partes iguais a ⌊N/2⌋ e ⌈N/2⌉, até restar apenas partes de no máximo k reais.

Observe que, uma leitura atenta do problema já nos indica um algoritmo para resolvê-lo. Seja conta(N), o número de partes que devemos dividir N, assim temos nossa recursão:

conta(N) = conta(⌊N/2⌋) + conta(⌈N/2⌉) se N > k
conta(N) = 1                           se N <= k

Pronto, basta implementar essa recursão e o problema de João está resolvido. Sem graça, né? Então, vamos explorar um pouco mais esse problema? Vamos brincar de derivar a complexidade da nossa solução?

É possível achar uma fórmula fechada para essa recursão, entretanto fazer isso é complicado, pois teríamos que lidar com ⌊N/2⌋, o que não é simples. Observe, entretanto que a solução para um problema de tamanho N depende da solução de um problema de tamanho N/2, então a complexidade de nossa recursão é provavelmente logarítmica.

Para comprovar nossa hipótese de que o número de passos de nossa recursão é logarítmico, suponha que N seja uma potência de 2 (N=2^h), assim ⌊N/2⌋ e ⌈N/2⌉ serão iguais, logo temos:

conta(N)         = 2*conta(N/2) <=> conta(N/2^0) = 2*conta(N/2^1)
conta(N/2)       = 2*conta(N/4) <=> conta(N/2^1) = 2*conta(N/2^2)
...
conta(N/2^(h-1)) = 2*conta(N/2^h)

logo nossa recursão terá profundidade h. Mas h = log2(N). Assim a complexidade do nosso algoritmo é logarítmica. E como você já deve ter ouvido, em algum lugar, que algoritmos de complexidade logarítimica são eficientes vamos implementá-lo, então!

Implementação

O código abaixo, implementa nossa solução. Observe que ⌊N/2⌋ e ⌈N/2⌉ são simples de calcular (basta saber se N é par ou ímpar!).

1331. Dominó

Olá, hoje vamos comemorar a estreia do Brasil na copa resolvendo mais problemas de maratona! Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em sequência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo do problema 1331. Dominó é justamente esse: determinar se é possível formar uma sequência com todas as peças de dominó fornecidas.

Modelagem

Antes de resolver esse problema, irei fazer uma breve revisão sobre grafos. Falarei apenas do necessário para solucionar esse problema. Se você não sabe o que são grafos, eu sugiro fortemente que você estude um pouco sobre isso já que eles são uma ferramenta muito poderosa na resolução de problemas.

Em teoria de grafos, diz-se que um grafo possui um caminho euleriano se existe um caminho que visita cada aresta apenas uma vez. Com caso especial, um circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg.

Em um grafo euleriano G todos os vértices têm grau par.

Prova: Seja G um grafo euleriano. Logo, por definição, ele contém um circuito euleriano. Assim, por cada vértice desse circuito, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas que passam por cada vértice é par.

Se removermos uma aresta de um grafo euleriano, ele deixara de ser euleriano, mas ainda conterá um caminho euleriano (é só começar e terminar o caminho nos vértices correspondentes as arestas removidas). Isso significa que um grafo que contém um caminho euleriano pode ter dois vértices de grau ímpar.

Voltando aos dominós, ligar peças, montar caminhos, é um forte indicio de que nosso problema pode ser resolvido usando-se grafos. Seja o seguinte grafo: G, onde os vértices são os números 0..6 e as arestas são os dominós. Será possível montar uma sequência com todos os dominós se, e somente se, G contiver um caminho euleriano. Em outras palavras, uma sequência de dominós não é nada mais do que um caminho euleriano onde eu peguei as arestas do grafo (os dominós) e enfileirei.

Note que os dominós podem formar um grafo que não é conexo, mas que possui dois sub grafos conexos e eulerianos, assim é necessário testar isso (com uma busca em profundidade por exemplo) para garantir que os dominós formem uma sequência única.

Implementação

8776. Batalha naval

Olá, estamos aqui de novo para resolver mais problemas! Hoje vamos falar de batalha naval e nos divertir um pouco contando quantos navios conseguimos afundar nesse conhecido jogo, já que é isso que o problema 8776. Batalha naval nos pede. 

Modelagem

Mais especificamente, esse problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determine o número de navios do outro jogador que foram destruídos.

A entrada do problema já nos dá uma boa ideia de como resolvê-lo, basta armazenar o tabuleiro em uma matriz e contar quantos navios foram afundados. Cada posição da matriz pode ser de três tipos: água, navio intacto ou navio avariado por um disparo. Observe que não precisamos armazenar a informação sobre os tiros que acertaram a água.

A restrição de que dois navios não podem ter arestas em comum nos permite aplicar uma busca em largura ao tabuleiro e ir contando quantos navios foram afundados. Não vou explicar, aqui, o que é uma busca em largura já que esse assunto é extensamente abordado em qualquer estudo sobre grafos. Veja que estou apenas pegando emprestada a ideia da busca em largura, mas não estou modelando o problema usando grafos.

Complexidade

Dado um tabuleiro de N x M nossa solução avalia cada posição da matriz uma vez, assim sendo nossa solução é O(N*M).

Implementação

Abaixo uma implementação em c++ do problema. Infelismente, não estou muito inspirado para falar sobre ela já que, como você deve ter visto, o problema é bem simples.

18285. Ano Novo

Para você que gostou de nossa últama postagem, estamos aqui de novo para resolver mais problemas!

Nem só de problemas complexos vive o spoj e hoje vamos falar de um problema, que se você não for capaz de resolver com facilidade, você deve pensar seriamente em parar de ler esse blog. Nesse post vamos falar do problema 18285. Ano Novo. De modo resumido o problema pede que, dada a hora atual, você responda quantos segundos faltam para meia noite.

Modelagem da solução

Converta a entrada para segundos e faça a subtração (eu falei que era simples).

Implementação

Uma dica que pode servir em outros problemas, sempre use printf e scanf eles são bem mais rápidos que cin/cout e além disso, é possível ler entradas mais complexas de forma mais simples.

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.