Analiza

Nameće da će čarobnjaci potrošiti manje vremena na uspavljivanje Jetija ako koriste više snage. Pored toga, bez obzira što se specijalna magija koristi na kraju (posle bacanja običnih čarolija), možemo već na početku "uračunati" specijalnu magiju (ako je veća od obične magije). Zbog toga formiramo niz sa svim mogućim čarolijama i magijama. Naime, ako su ~S_i~ i ~M_i~ početna jačina obične čarolije i jačina specijalne magije čarobnjaka broj ~i~, onda u niz ~a~ sa svim (mogućim) magijama dodajemo sledeće jačine: \(None\) M_i, S_i, \frac{S_i}{2^1}, \frac{S_i}{2^2}, \frac{S_i}{2^3}, ..., \frac{S_i}{2^k}, \(None\) gde je ~k~ broj sa osobinom da je \(None\) \frac{S_i}{2^k}\geqslant 1 \ \ \ \ \text{i}\ \ \ \ \ \frac{S_i}{2^{k+1}} < 1. \(None\) Po formiranju niza ~a~, soritramo ga u nerastućem poretku, a zatim određujemo najmanji broj ~m~ takav da je \(None\) a_1 + a_2 + a_3 + \dotsb + a_m \geqslant E. \(None\)

Kako su sve moći manje od ili jednake broju ~10^6~, to će i elementi niza ~a~ biti između ~1~ i milion, pa se taj niz može sortirati primenom sortiranja prebrajanjem (counting sort). Broj elemenata u nizu je ~O(N\log\max\{S_i, M_i|i=1, 2, ..., N\}) = O(N\log N)~. Složenost sortiranja je takođe ~O(N\log N)~ . Određivanje broja ~m~ koji predstavlja broj dana potrebnih da se uspava Jeti ima složenost ~O(\max\{S_i,M_i\})~.

Niz ~a~ se može sortirati primenom nekog brzog algoritma za sortiranje (npr. quick sort) i tada je složenost samog sortiranja ~O(N\log N\log(N\log N))~.

Zadatak možemo rešiti i bez sortiranja niza sa magijama. Naime, magije možemo smestiti u prioritetni red, a zatim iz reda brisati redom magije od najveće smanjijući svaki put Jetijevu moć za iznos te čarolije (magije) sve dok se Jeti ne uspava.