Tetraedro

[Bruno Oliveira]

Uma formiga extremamente activa, está no vértice D de um tetraedro, como o mostrado abaixo.

A uma dada altura, a formiga viaja de um vértice para outro através de uma das várias arestas do tetraedro, e a tarefa apresentada não envolve muitos cálculos.

Simplesmente, calculem o número de maneiras em que a formiga pode ir do vértice inicial D, de volta a ele próprio em apenas N passos.

Novamente, o resultado pode ser enorme, logo, devolvam-no reportado mod .

Exemplos:
Claramente, para N = 1 não há caminhos possíveis.

Para N = 2 a resposta é 3, e os caminhos possíveis são: D-B-D; D-A-D; D-C-D

Sabe-se ainda que, para N= 4, a resposta é 21!!



Have fun!!

Bruno

source: CodeForces

[francisco_machado]

Boas de novo,

Aqui vai a ideia:

A ideia deste problema é utilizar programação dinâmica, que consiste, resumidamente, em guardar o resultado dos estados anteriores para chegar ao próximo.
Fica-se a perceber mais a ideia com o exemplo deste problema.
Nós vamos criar uma lista que contém o número de trajectos que acabam em cada vértice i após um nº N de viagens da formiga.
Seja esse valor o cur[N][i].
Observação: Num tetraedro todos os vértices estão ligados entre si.
Imaginemos que sabemos cur[N-1][i] para todos os i, como calculamos os cur[N][i]?
Cada trajecto que acabe num vértice j na viagem N-1 poderá acabar em i na viagem N, pois todas os vértices estão ligados, logo o cur[N][i] é igual à soma dos cur[N-1][j] para j diferente de i, pois o vértice não pode ir para si próprio numa viagem.

Agora que já sabemos como gerar os estados seguintes a partir de estados anteriores, basta encontrar o primeiro estado, que será após a primeira viagem, onde cur[1][i] = 1 para todos menos para a origem, que será 0. A partir deste estado podemos gerar todos os outros pela regra a cima e ao chegar à viagem N, basta retornar o valor de cur[N][0], sendo o vértice 0 a nossa base.

No entanto dá para fazer uma melhoria em termos de memória. Deixo isso como desafio mas deixo aqui uma pista:

Super-spoiler (só olhar em caso de extrema necessidade:

É mesmo necessário guardar todos os estados anteriores? Se não, quais precisamos de manter?

Aqui vai o código:

Código: Seleccionar Todos

mod = 10**9 +7
cur = [ 0,1,1,1] #N de caminhos tais que acabam no vertice i ao fim de N andamentos
ab = [0,0,0,0]
for o in range(1,n):
   ab = [0,0,0,0]
   for k in range(4):
      for l in range(4):
         if not k==l:
            ab[k]+=cur[l] #Para o passo seguinte a o cur[i] será a soma todos os cur[j] dos outros vértices pois para cada
      ab[k] = ab[k]%mod      # caminho que vai para o vértice j, no passo seguinte também irá para i
   cur = ab
print cur[0]


[Bruno Oliveira]

Tenho uma ideia mais "matemática", um pouco baseada em intuição mas que acaba por ser talvez mais elegante...

Se ninguém chegar lá, posto a minha solução dentro em breve!!!

Muitos parabéns de novo Francisco!!

PS: O Francisco está a dominar ehehe, ninguém se opõe?
PPS: Tharis, is that you?

[francisco_machado]

Boas,

Depois de pensar um pouco mais no que poderia ser essa ideia mais matema´tica, acho que ja´ a descobri.

Aqui vai a ideia:

Observaç~ao, o valor e´ sempre mu´ltiplo de 3, pois os outros 3 vertices sa~o sime´tricos no problema e temos que o valor final e´ igual ao nu´emero de caminhos ate´ aos restantes ve´rtices em N-1 passos e como esse n´umero sera´ igual temos que o valor final sera´ mu´ltiplo de 3.

Seja [a,b,c,d] o nu´mero de caminhos que acabam na origem e em cada um dos outros ve´rtices (origem sera´ o 'a' para facilitar).
Para N=1 temos: [0,1,1,1]
Para N=2 temos: [3,2,2,2]
Para N=3 temos: [6,7,7,7]

Vemos que a origem tem sempre +1 ou -1 em relaçao aos restantes:
Seja k o valor de a para um N qualquer tal que os restantes ve´rtices tenham valor k+1. Nesse caso, o k seguinte sera´ 3*(k+1), e o dos ve´rtices sera 2*(k+1) + k = 3k+2 que faz com que os vertices sejam em 1 menores que a origem
Seja k o valor de a para um N qualquer tal que os restantes ve´rtices tenham valor k-1. Nesse caso, o k seguinte sera´ 3*(k-1), e os ve´rtices sera 2(k-1)+k = 3k-2 que faz com que sejam em 1 maiores que origem.
Logo do primeiro estado passa para o segundo, que passa de seguida para o primeiro, e temos que o valor tal que multiplicado por 3 da´ o resultado ´e o valor anterior *3 +- 1 dependendo da paridade de N.
Pois:
1. 3(k+1) -> 3*( 3(k+1)-1): k+1 -> 3*(k+1)-1
2. 3(k-1) -> 3*(3(k-1)+1): k+1 -> 3*(k-1) +1

Agora basta codar a relaça~o em cima.

Aqui vai o codigo:

Código: Seleccionar Todos

mod = 10**9 + 7
k = 0
n = input()
for i in range(1,n):
   k = 3*k + ((-1)**(i+1))
   k = k%mod
k = k%mod
print k*3


Peço desculpa pelos acentos, mas estou nos pcs do departamento e isto na~o tem os acentos bem.

[Bruno Oliveira]

Bem, andaste a aprender algoritmos com os famosos CLRS? Estes são mesmo muito bons!!

Parabéns pelos insights todos!!

Mas há ainda outra maneira!!

Bruno

[francisco_machado]

CLRS? Não conheço, o que é?

Muito obrigado.

A outra maneira que vejo é arranjar a fórmula fechada para isso que uma pesquisa rápida no google já me deu. É essa que estás a pensar?

[Bruno Oliveira]

Sim, francisco é exactamente isso!!

No entanto, aviso-te que existe uma pequena nuance relacionada com a implementação dessa ideia...

Ora corre o teu programa com a fórmula fechada para o valor de 30...

Bruno

PS: CLRS é a designação pela qual é conhecido o livro de algoritmos mais divulgado por várias universidades, o famoso: "Introduction to Algorithms" As letras são as iniciais dos apelidos dos autores.

PPS: Se não o conheces, onde aprendeste tanto de algoritmia?

[francisco_machado]

Tenho esse livro, mas não o conhecia por esse nome. Quanto a saber tanto de algoritmia advém de ter participado nas Olimpíadas Internacionais de Informática e a preparação deu-me bases fortes.

Deveria entrar em overflow não é? No meu não está a entrar...

[Bruno Oliveira]

De repente, acho que o problem setter, passou a coder e vice-versa

Não, nada de overflows... não esquecer que o valor máximo aqui pode ser relativamente grande... da ordem de 10.000.000 (esqueci-me das constrains... Fuck me, right? ), pelo que o problema é outro, mais matemático novamente...

Que valor devolve o teu programa?

[francisco_machado]

O de 30 devolve 347990060

[Bruno Oliveira]

Ehehe consegui apanhar um Olímpico em contra-pé... Ao fim de anos aqui no fórum..

Agora mais a sério, então e para N = 15?

Eu bem disse que havia um problema eheh!!!

A resposta para N = 15 é 3587226 e para N = 30 é 782663359

Boa sorte no debugging!!

[francisco_machado]

Tinha-me esquecido de multiplicar por 3, afinal tenho bem

[Bruno Oliveira]

Óptimo!!

Congrats, então se puderes coloca aqui a resolução para os newbies que aí vierem possam aprender também!

Eu posso depois colocar também a minha resolução aqui para ficarem duas explicações distintas!!

Cumprimentos,
Bruno

[francisco_machado]

Aqui vai a ideia:

Seguinto a logica do meu post anterior, temos que encontrar a formula fechada para a sequencia.

Para mostrar que a formula :

funciona, usaremos induçao.
Primeiro mostramos que a formula funciona para os casos base, n=1 e n=2 e vemos que nao funciona, mas se tomarmos n como n-1 vemos que ja funciona.

Agora vamos mostrar que se funciona para um n tambem funciona para n+1:
Se n for impar, temos que os restantes vertices tem o numero de elementos do vertice base +1, logo o vertice base para n+1 tera:
=
=
=

Tal como queriamos provar.

Para n par temos:
=
=
=

Logo a nossa formula funciona. YEAH

Aqui vai o codigo:

Código: Seleccionar Todos

mod = 10**9 + 7
n = input()
n-=1
print (3*( (3**n - (-1)**n)/4))%mod


[Bruno Oliveira]

O que o Francisco fez está tudo correcto, mas e que tal demonstrar directamente a fórmula fechada, sem indução?

Após a análise dos casos dados e vendo (à mão) que para N = 3 a resposta é 6, podemos intuir que a solução será da forma:



com f(1) = 0, e f(2) = 3 como caso base da recursão.

Agora, acontece que a solução em forma fechada para este tipo de recorrências pode ser achada através do que se chama a equação característica da recorrência! Como temos apenas um termo de ordem inferior a n (o termo onde entra o n-1) então a equação característica da nossa recorrência será de 1º grau, sendo os termos de ordem inferior a N, constantes com o valor da sua ordem!

Importa ainda referir que a solução final da recorrência é do tipo: onde é a equação característica homogénea (termo independente igual a 0) e é uma solução da nossa recorrência geral.

Seja o termo de ordem N. A equação homogénea fica:



pelo que uma solução geral para a parte homogénea fica:



Para resolvermos agora a parte não homogénea, intuimos (baseados no termo independente) que uma solução que satisfaz a equação:

será do tipo:



Substituindo na equação original vem:



e resolvendo para A sai imediatamente que:



Neste momento, a nossa solução é do tipo:



Podemos achar o valor de c, recorrendo à condição inicial de que f(2) = 3, de onde sai que e...voilá!!

Chegámos à fórmula do francisco!!

Edit: Franscisco, há muitos problemas com esse código :p