h1. Solutii runda 2

Suntem bucurosti ca runda 2 a concursului Autumn Warmup 2007 s-a incheiat. Acest articol va va prezenta solutiile celor 4 probleme propuse spre rezolvare, precum si cateva aprecieri in legatura cu desfasurarea probei.
 
Spre deosebire de prima runda, am incercat sa variem cat mai mult dificultatea problemelor, pentru a le permite tuturor sa se pregateasca. Au fost 2 probleme usoare (Trompeta si MMsir), una de dificultate medie (Curcubeu), iar ultima a fost "rupere" (Rompetrol), nivelul de dificultate al acestea fiind crescut chiar si pentru o competitie gen IOI. Il felicitam pe veteranul "Codrut Grosu":/utilizator/ragnar_lodbrok, care a fost singurul concurent ce a obtinut maxim la aceasta problema.
 
Aruncandu-ne privirea peste clasamentul rundei, observam in frunte membri vechi ai comunitatii, cu rezultate anul acesta la olimpiadele internationale. Runda a fost castigata de "Bogdan Tatataroiu":/utilizator/bogdan2412 care a reusit sa se impuna cu 3 probleme rezolvate aproape corect si cu un brute-force la Rompetrol. Pe locul 2 s-a clasat "Cosmin Gheorghe":/utilizator/gcosmin, iar pe 3 "Victor Rusu":/utilizator/victorsb. Ii felicitam atat pe ei, cat si pe ceilalti participanti.
 
Spre deosebire de prima runda, remarcam o oarecare omogenitate a punctajelor si speram ca v-au placut problemele. Daca aveti sugestii despre cum am putea sa imbunatatim concursul, le asteptam pe "forum":/forum/index.php?topic=2124.0. In continuare va prezentam solutiile problemelor din concurs.
 

h2. 'Curcubeu':problema/curcubeu
Vom considera colorarile incepand cu ultima. Parcurgem intervalul asociat ei si de fiecare data cand gasim o casuta necolorata ii asociem valoarea $C$<sub>$i$</sub>. Aceasta solutie are complexitatea $O(N^2^)$ si ar fi obtinut 20 de puncte. Pentru punctaj maxim este nevoie de un rafinament. Analizand solutia anterioara, observam ca vom parcuge de foarte multe ori castue deja colorate, lucru inutil si consumator de timp. Pentru fiecare pozitie $i$ vom mentine o valoare $Next[i]$, semnficand faptul ca intervalul $[i, Next[i]-1]$ contine doar casute colorate (initial $Next[i] = i$). Astfel, la colorarile urmatoare, vom putea "sari" peste secvente intregi de pozitii anterior colorate. Pentru a implementa eficient aceasta solutie, putem folosi una din cele doua euristici ale structurilor pentru multumi disjuncte, cea a comprimarii drumului. Puteti citi mai multe despre structuri pentru multimi disjuncte in "Cormen":http://zhuzeyuan.hp.infoseek.co.jp/ita/chap22.htm sau "aici":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure. Complexitatea finala este $O(N log* N)$. De mentionat faptul ca se pot obtine 50 de puncte implementand solutii de complexitate $O(N log N)$ folosind arbori de intervale sau un maxheap.