Napravimo ternarno stablo na sledeći način. Napravimo po jedan list za savku poziciju u početnom redu. Zatim uzimajmo prva 3 čvora iz reda i napravimo novi čvor koji će biti njihov direktni predak. Ubacimo novi čvor na kraj reda. To ponavljamo sve dok ne ostane samo jedan čvor u redu i on je koren stabla. Ako bismo u listove upisali nivoe veštine takmičara i u svaki čvor upisali medijanu brojeva njegovih direktnih potomaka u korenu bismo dobili nivo veštine pobednika.

Problem ćemo dalje rešavati binarnom pretragom po vrednosti rešenja. Recimo da proveravamo da li je rešenje barem ~X~. Da bi u nekom čvoru imali broj veći ili jednak ~X~, bar 2 njegova direktna potmoka moraju imati brojeve veće ili jednake ~X~. Dinamičkim programiranjem na stablu ćemo odrediti koliko najmanje brojeva većih ili jednakih ~X~ treba da stavimo u prazne listove kako bi u korenu stabla bio broj veći ili jednak ~X~. Neka je ~dp(node)~ ova vrednost ako posmatramo samo podstablo čvora ~node~. Za prazne listove ~dp(node)=1~. Za listove u koje je već upisan broj veći ili jednak ~X~, ~dp(node)=0~, a ako je uisan broj manji od ~X~, ~dp(node)= + \infty~. Za ostale čvorove ovu vrednost računamo po formuli ~dp(node)=dp(ch1)+dp(ch2)~ gde su ~ch1~, ~ch2~ i ~ch3~ direktni potomci čvora ~node~ i ~dp(ch1) \leq dp(ch2) \leq dp(ch3)~. Ako je ~dp(root)~ manje ili jednako broju takmičara koji nisu poranili i imaju ~A_i \geq X~, rešenje je veće ili jednako ~X~.

Vremenska složenost: ~O(Nlog(max A_i))~

Zadatak je preuzet sa ~\texttt{JOI}~ ~\texttt{Final}~ ~\texttt{Round}~ ~\texttt{2015}~.