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.

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

h2. 'Trompeta':problema/trompeta