Legenda lui Algorel

Poveste

Într-un mic oraș liniștit, unde serile erau mai lungi decât zilele, trăia un elev pe nume Algorel. Nu era cunoscut pentru sport sau pentru povești spuse în pauze, ci pentru altceva: o pasiune tăcută, dar arzătoare: algoritmica.

În fiecare noapte, după ce luminile orașului se stingeau, ecranul lui rămânea aprins. Acolo, în fața lui, se deschidea o lume diferită: lumea problemelor de pe Codeforces. Nu erau simple exerciții. Erau enigme, fiecare cu propria personalitate, fiecare cerând răbdare, intuiție și curaj.

Ani la rând, Algorel a rezolvat probleme. A greșit. A revenit. A învățat. A început să vadă tipare acolo unde alții vedeau doar text. Unele probleme păreau despre șiruri, dar ascundeau programare dinamică. Altele păreau simple, dar erau, de fapt, despre grafuri sau teoria numerelor.

Într-o zi, profesorul său i-a oferit o provocare diferită.

„Nu mai vreau să rezolvi probleme!” i-a spus.
„Vreau să le înțelegi.”

I-a oferit o arhivă, un fragment din vasta colecție Codeforces, și o sarcină aparent simplă, dar profundă: să învețe să recunoască esența fiecărei probleme.

Dar Algorel a simțit imediat că această provocare merge mai departe decât algoritmica standard.

Nu mai era doar despre soluții.
Era despre recunoașterea tiparelor, despre clasificare, despre abstractizare.

Exact aceleași idei care stau la baza Inteligenței Artificiale.

A început să vadă legături peste tot:

• programarea dinamică (dp) — similară cu memorarea și reutilizarea informației în modele de învățare;
• grafurile — fundament pentru rețele neurale, relații și propagarea informației;
• teoria numerelor — esențială în optimizare și criptografie;
• procesarea șirurilor — apropiată de analiza limbajului natural;
• geometria — folosită în reprezentarea spațială, viziune artificială și înțelegerea formelor și a datelor în spații multidimensionale.

Profesorul său a observat schimbarea.

„Acum înțelegi!” i-a spus.
„Algoritmica nu se poate distinge de Inteligența Artificială, deoarece este fundația ei.”

Dar provocarea era prea mare pentru un singur elev.

Așa că profesorul a luat o decizie.

A trimis această arhivă către cei mai străluciți elevi din țară - elevii din lotul național al Olimpiadei de Inteligență Artificială.

Pentru că dacă cineva îl poate ajuta pe Algorel să ducă această misiune la capăt, aceia sunteți voi.

Trebuie să-l ajutați pe Algorel să-l impresioneze pe dascălul său.

Setul de date

Aveți la dispoziție fișierul problems.csv, care conține o colecție de probleme selectate din arhiva Codeforces. Fiecare problemă include:

• id – identificator unic
• title – titlul problemei
• description – descriere detaliată
• statement – enunț complet
• input_format – formatul datelor de intrare
• output_format – formatul datelor de ieșire
• examples – exemple
• time_limit – limita de timp
• memory_limit – limita de memorie
• rating – dificultate estimată

Fiecare problemă ascunde un tipar. Uneori evident. Alteori bine deghizat.

Cerință

Pentru fiecare problemă din problems.csv, trebuie să determinați categoria algoritmică principală.

Etichetele posibile sunt:

1["dp", "geometry", "graphs", "number theory", "strings"]

Descrierea categoriilor

dp (Programare Dinamică)

Problemele din această categorie implică descompunerea unei probleme în subprobleme mai mici și reținerea rezultatelor deja calculate în vederea reutilizării. Accentul este pus pe optimizare și eficiență, evitând recalculările inutile prin memorarea soluțiilor intermediare.

geometry (Geometrie)

Aceste probleme se bazează pe concepte geometrice precum puncte, segmente, unghiuri, arii sau distanțe. Ele pot implica calcule în plan sau spațiu și sunt adesea legate de reprezentarea și analiza formelor sau a pozițiilor relative.

graphs (Grafuri)

Problemele de grafuri modelează relații între obiecte sub formă de noduri și muchii. Acestea includ parcurgeri (BFS, DFS), determinarea drumurilor, componente conexe, cicluri sau optimizări pe rețele.

number theory (Teoria Numerelor)

Această categorie cuprinde probleme bazate pe proprietăți ale numerelor întregi: divizibilitate, numere prime, factorizare, resturi și operații modulare. Sunt frecvente conceptele matematice riguroase și optimizările bazate pe ele.

strings (Șiruri de caractere)

Problemele din această categorie implică manipularea și analiza șirurilor de caractere. Ele pot include căutare de pattern-uri, comparări, transformări sau verificări de proprietăți ale textului.

Formatul fișierului de submisie

Trebuie să generați un fișier CSV cu următoarea structură:

1id,label2PROBLEM_0001,strings3PROBLEM_0002,strings4....

Evaluarea

Punctajul pentru această problemă este de 100 puncte.

Evaluarea se face prin compararea etichetelor prezise cu cele stabilite de experți.

Se utilizează metrica Macro-F1, care evaluează performanța modelului pe fiecare categorie în mod egal, indiferent de distribuția datelor.

Pentru fiecare categorie c:

• Precision = proporția clasificărilor corecte din totalul predicțiilor pentru categoria c
• Recall = proporția clasificărilor corecte din totalul instanțelor reale din categoria c

Scorul F1 pentru categoria c este:

Scorul final Macro-F1 este media scorurilor F1 pentru toate categoriile:

unde K = 5 reprezintă numărul de categorii.

Calculul punctajului

Punctajul final se calculează astfel:

$0, \text{ dacă MacroF1 } < 0.7$

$100\times\text{MacroF1},\ \text{dacă } 0.7 \le \text{MacroF1} < 0.95$

$100,\ \text{dacă } \text{MacroF1}\ge 0.95$