Despre problema
===============
Problema a fost propusa la concursul USACO.
Este rezolvabila prin metoda programarii dinamice, ne-evident (dupa
parerea mea) la prima citire a textului.
Fiecare balot este asezat sub cele trei forme : (a,b,c), (a,c,b),
(b,c,a). Primele 2 dimensiuni sunt sortate. Se sorteaza apoi dupa prima
dimensiune (iar in cazuri de egalitate dupa a doua). Astfel oricare
doua baloturi i, j pentru care este posibil ca i sa fie pus peste j apar
in ordinea . Se aplica algoritmul de la subsir crescator de lungime
maxima, varianta patratica (nu se mai poate face optimizarea logaritmica).
Complexitate : O(N^2).
Despre sursele concurentilor
============================
Toate sursele au rulat intr-un timp acceptabil (maxim 3 sec pe un DX4 la
100 Mhz), deci am considerat ca nici o sursa nu a iesit din timp pe nici
un test (nu am stiut exact limita de timp si nici masina pe care trebuia
sa evaluez).
Nici un concurent nu a avut probleme cu asezarea corecta a baloturilor
(din punct de vedere al dimensiunilor).
Nici un concurent nu a folosit baloturi inexistente.
Singura problema a ramas astfel inaltimea stivei de baloturi. 6 din cei
7 concurenti au reusit sa rezolve si acest punct perfect. Un singur
concurent (Popa Mihai) a avut dificultati, obtinand stive mai mici pe
7 din cele 10 teste propuse.
Concurentii sunt rugati in continuare sa includa descrieri succinte ale
rezolvarii in sursele trimise (la aceasta problema, doar Stan Bogdan a
explicat metoda folosita).
Cam atat.
|
|