Editorial for Takmičenje


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: TadijaSebez

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}.


Comments

There are no comments at the moment.