Category: maratona

Motivado pelo seguinte problema: https://br.spoj.pl/problems/DIOFANTO/

Então, eu li esse problema e bolei uma solução toda bonitinha pra ele usando combinatória. Só tava faltando implementar e eu mal sabia que era isso que ia me causar toda a dor de cabeça.

Eu estou implementando um algoritmo e em certo ponto preciso fazer a seguinte conta:

Em que a e b são números cujo fatorial não cabe em uma variável, p é um primo e p é maior que a e b. Como proceder?

Obviamente não posso calcular o fatorial antes, fazer a divisão e depois tirar o módulo. Mesmo um algoritmo que tenta ir simplificando a fração à medida que o fatorial é calculado não funciona. E o módulo do quociente não é o quociente dos módulos (Não acredita? Teste com p = 7, a = 5 e b = 3).

O que fazer então? Bom, as seguintes propriedades vão ajudar:

a^-1 (mod p) existe se mmc(a, p) = 1

Agora a gente pode usar essas coisas pra fazer o seguinte:

(a/b) mod p = ab^-1 mod p = (a mod p)(b^-1 mod p) mod p

Ainda sobre a prova de 2004 da seletiva da USP, agora no problema F: Estimando a Produção.

Se eu soubesse o que era o método dos mínimos quadrados antes de ler o problema eu ia ver isso e pensar “óbvio!”. Fazendo uma analogia, seria como um problema que possa ser resolvido com Dijkstra ser descrito por um grafo e pedindo o menor caminho a partir de um vértice para todos. Enfim… faltaram algumas aulas de matemática aí.

O problema é descaradamente a aplicação do método dos mínimos quadrados. Eu li isso, entendi a modelagem e tal, mas como resolver isso computacionalmente?? Não é trivial =/
Nesse link tem alguns métodos numéricos que mostram como fazer, mas sem pseudo-código nem nada… e pra mim que não conheço esses algoritmos fica difícil.

Em algum outro lugar vi que podia ser resolvido com o método de Newton ou algoritmo de Gauss-Newton, mas não olhei os detalhes deles ainda.

Sobre o problema I, da prova de 2004 da seletiva interna para a maratona de programação da USP, chamado Centro de Convenções.

Esse problema é um caso especial do “largest empty circle”, descrito aqui. Para resolver esse problema acho que tem que ser feito o seguinte:

Primeiro vc tem que gerar o diagrama de Voronoi do seu plano. Suponha que seu plano seja formado por um conjunto de n pontos: p1, p2, …, pn. Esse diagrama é uma divisão do plano em regiões de maneira que as arestas dessas regiões são formadas por pontos equidistantes de pi e pj. Cada vértice da região é um ponto equidistante de três ou mais pontos. Portanto, em cada região só existe um ponto pi, e aquela região contém todos os pontos que são mais próximos de pi do que de qualquer outro do plano.

Um diagrama de Voronoi pode ser construído com o algoritmo de Fortune (não achei trivial, por isso não implementei esse algoritmo =/ ).

Dado que a região foi construída, a maior circunferência que não contém nenhum pi terá o centro localizado em um dos vértices desse diagrama. Logo, basta percorrer a lista de vértices e verificar qual é a distância para os três (ou mais) pontos que definiram esse vértice.

A construção do diagrama é feita em O(n log n), o que é maior que o custo linear de percorrer os vértices para encontrar o centro do círculo procurado, logo, essa é a complexidade do algoritmo.