Analiza

Zadatak rešavamo razmatranjem vrednosti ~K~:

• Ako je ~K=0~, vrednost svakog stepena će biti 1, osim vrednosti ~0^0~. U tom slučaju treba da prebrojimo koliko ima 0 u nizu i svaku koju možemo povećamo za 1.

• Ukoliko je ~K=1~, lepota niza je suma njegovih elemenata. Tada je svejedno koji ćemo element povećati, pa samo primenimo svih ~C~ operacija na bilo koji element.

• Ukoliko je ~K=2~ i ukoliko budemo primenjivali ijednu operaciju, primenićemo svih ~C~ operacija na najveći. To važi, jer pretpostavimo da smo ukupno primenili ~D~ operacija i to ~D_i~ na element ~A_i~ i neka najveći ima vrednost ~a~ tada je konačna suma: ~\sum_{i=1}^n (A_i + D_i)^2 = \sum_{i = 1}^{n} (A_i^2 + 2 \cdot A_i \cdot D_i + D_i^2) = \sum_{i = 1}^{n} (A_i^2 + 2 \cdot A_i \cdot D_i) +\sum_{i = 1}^{n} D_i^2 \leq \sum_{i = 1}^{n} (A_i^2 + 2 \cdot a \cdot D_i) + \sum_{i = 1}^{n} D_i^2 = \sum_{i = 1}^{n} A_i^2 + 2 \cdot a \cdot D + \sum_{i = 1}^{n} D_i^2 \leq \sum_{i = 1}^{n} A_i^2 + 2 \cdot a \cdot D + D^2~, što je tačno jednako lepoti niz, kada bi na najveći dodali ~D~. Dakle ukoliko primenjujemo neke operacije, svakako ih primenjujemo na najveći. Međutim, primetimo da se tada lepota promenila za ~2 \cdot a \cdot D + D^2~ što maksimum dostiže ili za ~D=0~ ili za ~D=C~, pa ako budemo primenjivali neku operaciju, primenićemo svih ~C~ na najveći.

Smernice za algoritam

Primetimo da, ukoliko je ~K=2~, dovoljno je da proverimo da li povećavanjem najvećeg elementa za ~C~, povećavamo njegovu apsolutnu vrednost, ukoliko je povećavamo, primenićemo svih ~C~ operacija na njega, u suprotnom, nećemo primeniti ni jednu operaciju. Primetimo da, ukoliko apsolutna vrednost ostaje ista, nećemo primeniti ni jednu operaciju, jer težimo da minimizujemo broj operacija.