Putina istorie ACM ICPC SEERC

Cosmin Negruseri
29 octombrie 2007

Alt titlu la care m-am gandit pentru acest post este "In cate moduri poti sa propui niste probleme busite".
In fiecare an sunt probleme cu problemele de la regionala ACM la care participa studentii romani, iar anul asta s-a vazut mai clar din rezultate si nu din studierea testelor. Va ziceam intr-un post anterior ca un set de probleme bune este unul in care fiecare problema e rezolvata de cel putin o echipa, dar nici o echipa nu rezolva toate problemele. Anul asta sapte echipe au rezolvat toate problemele, una reusind sa le rezolve in doua ore si patru minute, cand timpul total al concursului e de cinci ore.

Putina istorie a problemelor bushite de-a lungul timpului:

In 2002 problema Sly Number implica rezolvarea unui sistem de ecuatii liniare modulare. Un concurent a testat cu backtracking testele comisiei si nici unul nu ii dadea rezultatul asteptat. In timpul concursului, o echipa a rezolvat problema respectiva, facand probabil aceiasi greseala ca si solutia comisiei.

In 2004 la problema City Game, se cerea determinarea dreptunghiului de arie maxima ce contine doar caracterul F pe o matrice ce contine caractere de F si R. Intre teste era unul care specifica o matrice de 100 de randuri si 100 de coloane, dar avea doar 98 de randuri. Daca aveai norocul ca partea de citire din program sa fie implementata ca si cea a comisieri, puteai rezolva problema ... Multe echipe s-au blocat in problema asta clasica, incercand sa isi gaseasca bugul de implementare care era de fapt in testele comisiei. De asemenea in acelasi an s-a propus problema Alibaba despre care am dubii mari ca ar exista vreo solutie de complexitate mai buna decat desi limita de timp din concurs facea ca o asemenea solutie sa obtina mesajul Time Limit Exceeded. Testele la Alibaba sunt foarte misto, cateva teste mici ce merg cu programare dinamica in si doua teste mari la care merge lejer greedy.

In 2005 s-a propus rezolvarea unui puzzle Sudoku, dar toate testele puteau fi rezolvate punand o cifra in locuri fortate, pentru nici un test nu trebuia facut backtracking. Astfel echipele care fac solutia buna au un dezavantaj fata de echipele care nu isi dau seama ca exista cazuri pe care solutia lor nu merge. Problema Adventurous Driving avea ca limita in enunt n <= 100 iar in teste era un n = 1000. Autorul problemei era mandru de ea, pentru ca doar o echipa a rezolvat-o in timpul concursului.

In 2006 problema Shortest Pair of Paths cerea determinarea a doua drumuri minime disjuncte de la sursa la destinatie. Problema este clasica si se rezolva cu flux maxim de cost minim, dar testele au facut ca o solutie ce gaseste de doua ori un drum folosind algoritmul lui Dijkstra sa mearga. Din nou echipele care au stiut ca problema e mai complicata au pierdut timp implementand solutia mai grea. Alta problema bushita a fost Sherloc Holmes care era un knapsack 2d, dar nu prea incapea in memorie pentru ca n si m erau 10000. Dupa concurs s-a vazut ca testele contineau n si m-ul maxim 300.

Acestea nu sunt singurele exemple.

Sa organizezi un concurs cu multe probleme, la un nivel inalt este foarte greu. Putine regionale reusesc asta. Printre ele sunt ECNA, o regionala din Canada, NEERC, una din Rusia, CEPC, regionala Europei Centrale. Acestea au probleme de calitate, de dificultate mare, cu explicatii de solutii scrise, cu o echipa de organizatori care contin studenti care au fost concurenti. Nu e de mirare ca aceste regionale au aproape in fiecare an o echipa in primele cinci din lume.

Si la TopCoder se intampla ca un concurs sa fie bushit, desi ei isi bazeaza afacerea lor pe asta. Dar pentru a evita greselile, care, avand in vedere ca organizeaza mai mult de un concurs pe saptamana, ar fi normal sa se intample, acestia au o metodologie foarte bine pusa la punct. Fiecare problema este rezolvata de inca trei oameni, altii decat autorul, care isi dau cu parerea atat asupra problemei cat si asupra testelor alese. Un al patrulea om are grija ca textul sa nu aiba ambiguitati. Autorul trebuie sa faca enuntul, testele si un validator pentru teste.

Concursul ACM este un eveniment important care se desfasoara o data pe an, si el ar trebui organizat cu grija, astfel incat concurentii sa nu plece cu impresia ca au fost luati in bataie de joc. Ce trebuie facut pentru corectarea problemelor din trecut ar fi intinerirea comisiei stiintifice, scrierea unui validator de teste, si implementarea a mai multor solutii pentru fiecare problema. Nu pare foarte greu, dar se pare ca nu se invata nimic din esecurile anterioare.

Puteti citi si postul lui Florin Manea, antrenor al echipelor universitatii Bucuresti, despre regionala ACM aici