<div class="gmail_quote">2012/1/29 Tiago Peczenyj <span dir="ltr"><<a href="mailto:tiago.peczenyj@gmail.com">tiago.peczenyj@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Eu tentei fazer o Auction mas cheguei a um algoritmo O(n^2) e me<br>
arrependi amargamente.<br></blockquote><div><br>O Auction foi o mais difícil até agora (dos 6 problemas dos dois rounds).<br>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.<br>

<br>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.<br>

 <br></div>[ ]'s<br></div>-- <br>Bruno C. Buss<br><a href="http://brunobuss.wordpress.com/">http://brunobuss.wordpress.com/</a><br><a href="http://www.dcc.ufrj.br/~brunobuss/">http://www.dcc.ufrj.br/~brunobuss/</a><br>