Contrar punctajelor, aceasta a vrut sa fie problema usoara a setului.

Problema are doua parti: aflarea discriminarii minime si gasirea componentei optime.

Problema are doua parti: aflarea discriminarii minime si gasirea componentei Consiliului Local.

Pentru prima parte era nevoie de observatia ca, discriminarea pe o ulita este fie $0$, fie $1$. $0$ era in cazul in care ulita avea un numar par de case (alegeam din prima casa un barbat, apoi o femeie, etc.) si, repsectiv, $1$, cand pe ulita erau un numar impar de case.

Pentru prima parte era nevoie sa se observe faptul ca discriminarea pe o ulita este fie $0$, fie $1$. $0$ era in cazul in care ulita avea un numar par de case (alegeam din prima casa un barbat, apoi o femeie, etc.) si, repsectiv, $1$, cand pe ulita erau un numar impar de case.

Partea a doua necesita o analiza mai atenta.
Prima solutie se bazeaza pe teoria grafurilor. Vom construi un graf bipartit, unde nodurie din partea stanga sunt reprezentate de dreptele paralele cu $OX$, iar nodurile din partea dreapta sunt reprezentate de dreptele paralele cu $OY$. Intre un nod din stanga si un nod din dreapta va exista muchie doar daca la intersectia celor doua drepte se afla o casa. Se porneste dintr-un nod cu grad impar, marcand alternativ muchiile (casele) cu $0$ sau $1$ si eliminandu-le. Raman, astfel, numai noduri cu grad par, care vor forma cicluri, dar care se pot rezolva folosind, din nou, algoritmul de mai sus.