Diferente pentru blog/acm-2013-etapa-nationala intre reviziile #20 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

iar clasamentul 'aici':http://acm.tju.edu.cn/toj/vcontest/ranklist9268.html
La concurs au participat peste 50 echipe iar setul de probleme a fost unul echilibrat.
Voi prezenta in continuare o parte din probleme şi soluţiile acestora
Voi prezenta in continuare o parte din probleme şi soluţiile acestora. Vă invit să contribuiţi la comentarii cu soluţiile voastre
h2. 'G. Election Time':http://acm.tju.edu.cn/toj/vcontest/showp9268_G.html
h2. 'J. Template Library Management':http://acm.tju.edu.cn/toj/vcontest/showp9268_J.html
În această problemă se dă un vector $V$ de $N$ $(N<=100 000)$ $(V[i]<=10^9^)$ elemente şi o listă de dimensiune $M$ în care iniţial sunt numerele de la 1 la $M$. Pentru a trece mai departe de la poziţia $i$ trebuie să avem în listă valoarea $V[i]$. La orice moment de timp putem înlocui un număr din listă cu orice alt număr care nu se află deja in ea. Problema ne cere numărul minim de înlocuiri cu care putem parcurge vectorul.
 
Vom încerca să aplicăm o strategie de tip greedy pentru a rezolva problema. La fiecare pas la care elementul de pe poziţia $i$ nu se află în listă trebuie să decidem ce element trebuie să eliminăm. Se observă că este optim să eliminăm elementul din listă care apare în vector pe cea mai din dreapta poziţie sau care nu apare deloc. Pentru a calcula această informaţie vom calcula un vector $next[i]$ cu semnificaţia: prima poziţie $> i$ pe care apare elementul $V[i]$. Având această informaţie calculată putem simula lista cu un max heap în care vom ţine elementele ordonate în funcţie de poziţiile pe care urmează să apară.
 
 
h2. 'K. Fast Arrangement':http://acm.tju.edu.cn/toj/vcontest/showp9268_K.html

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.