2012/1/29 Tiago Peczenyj <[email protected]> > 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/
=begin disclaimer Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ SaoPaulo-pm mailing list: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
