Групе
Аутор: Алекса Плавшић
Текст и тест примери: Александар Златески
Анализа решења: Драган Урошевић
Тестер: Иван Стошић
Приметимо да ако збир свих елемената низа није дељив бројм L, онда не постоји решење, јер се низ не може поделити у L група који имају једнаке збирове. Значи у том случају је решење нула (0).
Ако је S збир свих елемената низа S и ако је S дељиво бројем L, онда збир сваке од група мора бити S/L. Нека је L' број група за које важи да је збир различит од S/L. Тада важи следеће:
Ако L'\not\in\{0,2\}, онда не постоји нити једна размена којом би се изједначио збир елемената у свим групама, па је решење нула.
Ако је L'=0, онда све групе већ имају једнак збир, па због тога размена било ког пара елемената из исте групе или било ког пара елемената који имају исту вредност доводи до низа који задовољава услов (да све групе имају исти збир). Број размена у којима се размењују елементи из исте групе је
L \times \frac{N/L(N/L-1)}{2}.
Број размена у којима се размењују једнаки елементи се добија тако што се преброји број појављивања сваке од вредности. Ако су V_1, V_2, V_3, ..., V_K различите вредности који се појављују у низу a, а n_{V_1}, n_{V_2}, n_{V_3}, ..., n_{V_K}, бројеви појављивања тих вредности онда је број размена елемената који имају исту вредност једнак:
\frac{n_{V_1}(n_{V_1}-1)}{2} + \frac{n_{V_2}(n_{V_2}-1)}{2} + ... + \frac{n_{V_K}(n_{V_K}-1)}{2}.
Међутим, у овом изразу фигуришу и размене једнаких који се налазе у истој групи. Због тога те размене треба одузети, а то ћемо извести тако што ћемо исти поступак пребрајања вредности извести за сваку групу и израчунати вредност одговарајућег израза (еквивалентног горњем).
Ако је L'=2, онда постоје две групе у којима се збир не поклапа са просечном вредношћу (тј. са S/L). У једној групи је збир већи од просека, а у другој је мањи од просека (при чему су апсолутне разлике тих сума и просека једнаке). Означимо са d апсолутну разлику суме једне од тих група и просека S/L. Тада се може разменити било који пар елемената из те две групе за који важи да је разлика елемента који се налази групи са већим збиром и елемента који се налази у групи у којој је мањи збир једнак d. Значи, потребно је пребројати број појављивања појединих вредности у две групе, након тога измножити одговарајуће бројеве појављивања и производе сабрати.
Смернице за алгоритам
Будући да су вредности елемента мање од или једнаке 10^6, може се формирати низ у коме ће се рачунати бројеви појављивања појединих вредности. Због тога бројеве појављивања појединих вредности можемо одредити једним пролазом кроз низ. Поред тога потребан је један пролаз кроз низ како би се одредили збирови елемената по групама. Али како се у оба случаја ради о једном пролазу кроз низ, алгоритам има линеарну сложеност.