La info clasamentul pe natiuni se face dupa medalii si nu dupa punctajul cumulat? 
Felicitari pentru rezultat!

Dintre cele Q perechi, pot exista doua care sa aiba o pozitie comuna?

Da, ceea ce doream sa spun e ca trebuie sa EXISTE o solutie riguroasa, nu neaparat sa apara in solutiile publicate. In acest sens, precum s-a spus si mai sus, solutia la ciocolata este foarte buna: e precizat faptul ca se poate demonstra inductiv afirmatia facuta, dar demonstratia nu e facuta explicit. Daca, spre exemplu, comisia ar fi trebuit in solutiile publicate sa descrie ( NU neaparat sa demonstreze ) de ce algoritmul de la progresie este corect, cu siguranta s-ar fi descoperit greseala.

M-am uitat si eu peste problema, si intr-adevar solutiile oficiale sunt cu mai multe bube. In primul rand, absolut toate fac exact aceeasi constructie, singura diferenta fiind limbajul folosit (nu de programare). Dar mai intai despre problema.

Solutia greedy (cea oficiala), are in medie a_n ~ n^{log3/log2}, iar log3/log2 este aproximativ 1,585, deci asimptotic mai mare decat n*sqrt(n) cerut de problema. Totusi, se pune problema care e cel mai mic a_n astfel incat sirul ala sa aiba proprietatea ca nu exista 3 termeni in progresie aritmetica. Se cunoaste un upper bound (mai bun decat n*sqrt(n) ), demonstrat de Behrend; vezi http://www.epsilonsmall.com/resources/behrends-construction/behrend.pdf ; in fine, el defapt construieste o multime cu cat mai multe elemente, toate incluse in [1,N]; problemele sunt echivalente. Exista si un lower bound demonstrat de Roth; a_n trebuie sa fie  O(n/ln(n)), dar demonstratia este mai complicata.

Bineinteles constructia lui Behrend nu numai ca nu intra in timp pt N<=30000, dar nici macar nu e prea optima pt N atat de mic. Se pune acum problema daca exista alta constructie; o prima idee e sa facem din nou greedy, dar cu alt set de inceput (in solutia oficiala se incepe cu 1 si se obtin numerele care au in baza 3 doar cifre de 1 si 0). Aceasta problema a fost data la un test de selectie din China, si tot ce demonstreaza este ca exista multe n-uri astfel incat a_n < c*n^2, pentru o constanta c. Vezi http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3434262&sid=a676b71e9396b4d54d8588491732c637#p3434262 . Culmea problema a fost data cam acum o luna. Ce putem observa din aceasta problema este ca in afara de cateva cazuri magice (precum cel din solutia oficiala, dar si daca incepeam cu numere de forma 3^m sau 2*3^m), nu prea putem spune mai mult decat a_n<=c*n^2 (problema a fost data la un test chinezesc, deci ar trebui sa fie relativ optima! ). Intr-adevar, citind aici ( http://www-math.mit.edu/~rstan/papers/od.pdf ), se vede ca solutia greedy se presupune a fi foarte haotica in majoritatea cazurilor.

Iar atunci ramane intrebarea: cum putem rezolva problema? Am vorbit si cu un distins profesor de matematica, si nici el nu cunoaste alta constructie in afara de cele 2 amintite mai sus. Din cele 2, doar cea greedy este fezabila, dar aceasta nu rezolva corect problema.

Si acum sa incerc sa raspund la intrebarea lui Mihai : nu mai prea e nimic de facut, olimpiada s-a terminat deja. Ce poate fi facut in viitor este ca demonstratiile sa fie mai riguros matematica, si sa nu lasam in vant afirmatii (a se observa ca in nicio solutie oficiala nu se face precizare DE CE are loc a_n < 2n*sqrt(n) ). Am observat ca la informatica, spre deosebire de matematica, solutiile se bazeaza foarte mult pe intuitie. Acest lucru este foarte bun in concurs, unde participantii au de rezolvat 3 probleme (relativ) grele, sia poi mai trebuie sa le si implementeze. Nu ar fi timp prea mult pentru demonstratii extrem de riguroase la toate observatiile. Dar aceste demonstrtii nu pto lipsi din solutiile oficiale, caci altfel patim ca in aceasta problema ( a se observa ca si la problema volum de la 11-12 solutiile sunt mai mult intuitive decat argumantate; probabil e la fel la mai multe probleme).

Un numar de observatii in plus: din cate am observat, nici solutia lui Popescu Silcviu nu respecta problema (adica a_n < 2*n*sqrt(n) ). Probabil n-ul in acest caz este mai mare decat 30000, dar sigur exista , caci in solutia lui termenul a_{2^n} este (3^n+1)/2, care iarasi este aproximativ a_n^{log3/log2}. Mai mult, complexitatea primei solutii (daca am inteles bine), nu este O(n *log(n)) (care nu ar explica cele 30 de puncte), ci  O(n^{1(log2/log3)})
, unde log2/log3 este aproximativ 0,631, complexitate mult mai mare decat ce era precizat. Nici nu inteleg de unde au scos complexitatea aia.