* Optimizarea "<tex>O(nk^2)</tex> devine <tex>O(nk)</tex>", care a apărut pentru prima oară în România o dată cu problema 'Cli':problema/cli. Aceasta este o rafinare a mai cunoscutei "<tex>O(n^3)</tex> devine <tex>O(n^2)</tex>", folosită în probleme precum: 'Politic':problema/politic, 'Purification':problema/purification şi 'Tricolor':problema/tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina $22$ de 'aici':http://www.lookingforachallengethebook.com/uploads/1/4/5/5/14555448/preview-_looking_for_a_challenge.pdf (problema Barricades).
* În afara programei de olimpiadă: 'Algoritmul Simplex':https://en.wikipedia.org/wiki/Linear_programming. Cu toate acestea, problema 'Echilibrare':problema/echilibrare admite o soluţie inedită, alternativă, folosind această tehnică; pentru majoritatea elevilor, Simplex nu e mai mult decât un "black-box". _Aside_: Având în vedere soluţia oficială a problemei, ce putem înţelege, sau intui, din acestea? Există strânse legături între problemele de flux întâlnite la olimpiada, forma lor matriceala şi problemele lor duale de optimizare. Nu nu, nu o să explic ce am vrut să zic cu asta - să vă provoc şi pe voi puţin!

Sistemul de vot pe care îl studiem se numeşte Chamberlin-Courant, şi este destul de uşor de descris. Avem $n$ candidaţi şi $m$ alegatori, fiecare alegător exprimându-şi preferinţele prin liste ordonate de preferinţe. Pentu un $k$ dat, scopul este să alegem un comitet câstigător format din $k$ candidaţi, adica unul de **cost minim**. Cum calculăm costul? Pentru fiecare alegător număram candidaţii mai bine văzuţi de către el decât toţi aleşii din comitetul de $k$, şi apoi adunăm la costul total acest număr. De exemplu, dacă primele opţiuni ale tuturor alegătorilor formeaza o mulţime de cel mult $k$ candidaţi, atunci comitetul câstigător va avea cost $0$! Din păcate, problema generală este NP-hard, dar nu este totul pierdut, deoarece în alegeri reale preferinţele candidaţilor nu sunt arbitrare, sau "wrost-case", aşa cum ne obisnuiesc temerarii comisiilor, ci au destul de multa _structură_. În ce sens au structură? Depinde - esenţa este să restrângem domeniul de preferinte suficient de puţin încât să putem înca modela alegerile reale, dar şi suficient de mult încât să putem rezolva problema în timp polinomial. Nu zic mai mult să nu plictisesc!

Sistemul de vot pe care îl studiem se numeşte Chamberlin-Courant, şi este destul de uşor de descris. Avem $n$ candidaţi şi $m$ alegatori, fiecare alegător exprimându-şi preferinţele prin liste ordonate de preferinţe. Pentu un $k$ dat, scopul este să alegem un comitet câstigător format din $k$ candidaţi, adica unul de **cost minim**. Cum calculăm costul? Pentru fiecare alegător număram candidaţii mai bine văzuţi de către el decât toţi aleşii din comitetul de $k$, şi apoi adunăm la costul total acest număr. De exemplu, dacă primele opţiuni ale tuturor alegătorilor formeaza o mulţime de cel mult $k$ candidaţi, atunci comitetul câstigător va avea cost $0$! Din păcate, problema generală este NP-hard, dar nu este totul pierdut, deoarece în alegeri reale preferinţele candidaţilor nu sunt arbitrare, sau "worst-case", aşa cum ne obisnuiesc temerarii comisiilor, ci au destul de multa _structură_. În ce sens au structură? Depinde - esenţa este să restrângem domeniul de preferinte suficient de puţin încât să putem înca modela alegerile reale, dar şi suficient de mult încât să putem rezolva problema în timp polinomial. Nu zic mai mult să nu plictisesc!

Totuşi, cel mai mare efort pentru mine a fost acela de a prezenta noile rezultate clar şi fără "leap"-uri în raţionament. Am observat în general o oarecare superficialitate când vine vorba de asta - de foarte multe ori într-un salt în raţionament se ascunde o greşeală extrem de subtilă. În sensul ăsta, vă las cu o anecdotă: primul rezultat pe care l-am avut a constat pur şi simplu în a citi un paper vechi de aproximativ 5 ani. Am observat cum autorii prezentau un algoritm polinomial bazat pe programare dinamică pentru o problema pe arbori, dar algoritmul era redactat de aşa natura încât micile greşeli de scriere (cum ar fi un ' uitat aici, un indice dincolo) se aliniau perfect cât sa dea naştere unui algoritm care părea corect. Şi mai interesant, în funcţie de cum corectai typo-urile, fie devenea greşit, dar polinomial, fie corect, dar atunci analiza complexităţii nu mai mergea dusă la capăt (algoritmul devenea exponenţial pe un arbore stea, aşa cum arătăm în {'paper':https://arxiv.org/abs/2010.08637}-ul complet). **Ironia** este că am fost la un milimetru să zic "mda, are sens, probabil e corect", cum nu înţelegeam încă toate notaţiile şi ideea centrală părea naturala. Totuşi, ceva tot parca nu se lega şi eram încăpăţânat! Fast-forwarding, am găsit un algoritm nou pentru problemă, unde am putut folosi chiar optimizarea menţionată în lista de tehnici de la olimpiade de mai sus.