Entre os dias 6 e 7 de junho aconteceu a oitava edição do Contest Noturno, organizada pelo maratonista Bruno Ribas, com exercícios inéditos escritos pelo Bruno, Ricardo Oliveira, Mateus Dantas e eu.
Pra quem ainda não tem, aqui está o link da prova – [link].
Os exercícios desta e das competições anteriores estão disponíveis nesta página do spoj – [link].
Abaixo segue um editorial escrito por mim. Clique no link abaixo para vê-lo.
Continuar lendo 8o Contest Noturno – Editorial
Descobrir o n-ésimo elemento da sequência de fibonacci é o problema mais manjado de competições de programação, mas mesmo assim sempre há uma forma criativa de expor esse conceito e por isso é bom estar preparado.
Se você só conhece o método recursivo e/ou iterativo (O(n)), uma hora ou outra vai passar algum apuro para descobrir alguns valores maiores.
Por mais que essa sequência seja um grande mistério, e ainda não se conhece uma fórmula* 100% precisa para descobrir os elementos, para nossa salvação há alguns métodos com complexidade bem “amigáveis”.
Clique no link abaixo para ver a implementação do algoritmo Fast Doubling, que descobre o n-ésimo elemento em complexidade O(log N).
Continuar lendo Implementação – Fast Doubling