[SP-pm] Facebook World Cup 2012 Fase 1

[Bruno Buss]

2012/1/29 Tiago Peczenyj <tiago.peczenyj at gmail.com>

> Eu tentei fazer o Auction mas cheguei a um algoritmo O(n^2) e me
> arrependi amargamente.
>

O Auction foi o mais difícil até agora (dos 6 problemas dos dois rounds).
O algoritmo não poderia ser parametrizado em n, nem mesmo linear - O(n) -
pois n era da ordem de 10^18. Logo qualquer tentativa de simulação ou
trabalhar os pontos explicitamente não iria muito adiante.

A parte mais trick do problema era saber utilizar matemática modular e
trabalhar aquela formula do "gerador pseudoaleatório" que ele dava,
identificando a fase transiente e a parte cíclica das sequências. Com isso
você consegua um algoritmo O(m + k), onde m e k são da ordem de 10^7.

[ ]'s
-- 
Bruno C. Buss
http://brunobuss.wordpress.com/
http://www.dcc.ufrj.br/~brunobuss/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20120129/4051723d/attachment-0001.html>