Задатак можемо решити тако што \(n-1\) пут низ ефективно ротирамо за по једно место улево, израчунавајући сваки пут тежински збир изнова, тражећи максимум и позицију максимума тако добијених тежинских збирова. Пошто се тежински збирови у нашем задатку рачунају по датом модулу \(mod\), све операције у претходним формулама треба заменити одговарајућим операцијама по модулу (њих можемо реализовати у засебним функцијама).
Сложеност. Пошто број операција потребан за израчунавање тежинског збира линеарно зависи од дужине низа \(n\) (сваки тежински збир се израчунава у сложености \(O(n)\)), овај приступ доводи до квадратне сложености алгоритма (сложености \(O(n^2)\)). Чак иако бисмо оптимизовали број израчунавања остатака, програм ће бити неефикасан услед квадратне сложености алгоритма и пуно померања елемената низа.
#include <iostream>
#include <vector>
using namespace std;
// modul dat u tekstu zadatka
const int mod = 1234567;
// zbir brojeva x i y po modulu mod
int zm(int x, int y, int mod) {
return (x % mod + y % mod) % mod;
}
// ciklicno pomeranje (rotiranje) niza za jedno mesto ulevo
void rotirajUlevo(vector<int>& a, int n) {
int pom = a[0];
for (int i = 0; i < n - 1; i++)
a[i] = a[i + 1];
a[n - 1] = pom;
// moglo bi i rotate(begin(a), next(begin(a)), end(a));
}
// suma brojeva a[i]*i, za i od 0 do n-1, po modulu mod
int tezinskiZbir(const vector<int>& a, int n, int mod) {
int s = 0;
for (int i = 0; i < n; i++)
s = zm(s, i * a[i], mod);
return s;
}
// najveci tezinski zbir 0*a[0] + ... + (n-1)*a[n-1] posle ciklicnog
// pomeranja niza ulevo
int maksTezinskiZbirNakonRotacije(const vector<int>& a) {
// kopiramo niz da bismo mogli da ga menjamo
auto acopy = a;
// broj elemenata niza
int n = acopy.size();
// maksimum inicijalizujemo na tezinsku sumu pocetnog niza
int maxTezinskiZbir = tezinskiZbir(acopy, n, mod);
for (int i = 1; i < n; i++) {
// rotiramo elemente niza a za jedno mesto ulevo
rotirajUlevo(acopy, n);
// izracunavamo novu tezinsku sumu
int tekSuma = tezinskiZbir(acopy, n, mod);
// azuriramo podatke o maksimumu ako je to potrebno
if (tekSuma > maxTezinskiZbir)
maxTezinskiZbir = tekSuma;
}
return maxTezinskiZbir;
}
int main() {
// ubrzavamo ucitavanje elemenata niza
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo maksimalni zbir
cout << maksTezinskiZbirNakonRotacije(a) << endl;
return 0;
}Уместо ефективне ротације свих елемената низа, ефекат обиласка низа који је ротиран за \(k\) места улево можемо постићи тако што обилазак крећемо од позиције \(k\), а затим у петљи која има \(n\) итерација увећавамо бројач за \(1\), али овај пут по модулу \(n\) (када бројач постане \(n\) вредност му се враћа на нулу што можемо постићи било експлицитним испитивањем вредности након сваког увећања бројача, било израчунавањем остатка при дељењу са \(n\), што је спорије од гранања, јер је израчунавање остатка при дељењу обично релативно скупа операција).
На основу ограничења датих у тексту задатка, максимална вредност тежинског збира се постиже када низ има \(50000\) елемената чија је вредност \(100\). Тада се са \(100\) множи сваки елемент од \(0\) до \(49999\) и максимални тежински збир је једнак \(100\) пута вредност збира свих природних бројева до \(49999\) што је једанко \(100\cdot \frac{49999\cdot(49999 + 1)}{2}\), што је око \(1.25\cdot 10^{11}\) и стаје у опсег 64-битног типа (у језику C++ то је тип long long). Ако тај тип употребимо за чување збира, онда остатак при дељењу можемо израчунати само једном, након целокупног израчунавања збира, чиме се добија на ефикасности.
Сложеност. Иако избегавамо ротације, свака од \(n\) тежинских сума се израчунава засебно у времену \(O(n)\), па сложеност остаје \(O(n^2)\).
#include <iostream>
#include <vector>
using namespace std;
// modul dat u tekstu zadatka
const int mod = 1234567;
// najveci tezinski zbir 0*a[0] + ... + (n-1)*a[n-1] posle ciklicnog
// pomeranja niza ulevo
long long maksTezinskiZbirNakonRotacije(const vector<int>& a) {
int n = a.size();
long long maxTezinskiZbir = 0;
for (int i = 0; i < n; i++) {
// koristimo tip long long, da ne bismo morali da izracunavamo
// ostatak posle svakog sabiranja, vec samo nakon izracunavanja
// celog zbira
long long tezinskiZbir = 0;
int k = i;
for (int j = 0; j < n; j++) {
tezinskiZbir += a[k] * j;
if (++k == n) k = 0;
}
tezinskiZbir %= mod;
// azuriramo podatke o maksumumu, ako je to potrebno
if (tezinskiZbir > maxTezinskiZbir)
maxTezinskiZbir = tezinskiZbir;
}
return maxTezinskiZbir;
}
int main() {
// ubrzavamo ucitavanje elemenata niza
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo maksimalni zbir
cout << maksTezinskiZbirNakonRotacije(a) << endl;
return 0;
}Задатак је могуће решити и много ефикасније ако применимо принцип инкременталности тј. пронађемо начин да тежински збир после ротације ефикасно израчунамо на основу познатог тежинског збира пре ротације. Можемо уочити да je у тежинском збиру после померања улево сваки елемент низа, изузев првог елемента \(a_0\), један пут мање укључен него пре померања, а први елемент је укључен \(n-1\) пут. Обележимо са \(z_i\) тежински збир добијен приликом померања полазног низа улево \(i\) пута, а са \(z\) класичан збир свих елемената низа. Према томе важе следеће једнакости:
\[ \begin{array}{rcl} z_0 &=& 0 \cdot a_0 + 1 \cdot a_1 + 2 \cdot a_2 + ...+ (n - 2) \cdot a_{n-2} + (n - 1) \cdot a_{n-1}\\ z_1 &=& 0 \cdot a_1 + 1 \cdot a_2 + 2 \cdot a_3 + ...+ (n - 2) \cdot a_{n-1} + (n - 1) \cdot a_0\\ z_2 &=& 0 \cdot a_2 + 1 \cdot a_3 + 2 \cdot a_4 + ...+ (n - 2) \cdot a_0 + (n - 1) \cdot a_1\\ &\ldots&\\ z_{n-1} &=& 0 \cdot a_{n-1} + 1 \cdot a_0 + 2 \cdot a_1 + ...+ (n - 2) \cdot a_{n-3} + (n - 1) \cdot a_{n-2} \end{array} \]
\[z = a_0 + a_1 + ... + a_{n-2} + a_{n-1}\]
Приметимо да важи
\[ \begin{array}{rcl} z_0 - z_1 &=& a_1 + a_2 + \ldots + a_{n-1} - (n-1) \cdot a_0 = z - n \cdot a_0\\ z_1 - z_2 &=& a_2 + a_3 + \ldots + a_0 - (n-1) \cdot a_1 = z - n \cdot a_1\\ &\ldots&\\ z_{n-2} - z_{n-1} &=& a_{n-1} + a_{0} + \ldots + a_{n-3} - (n-1)\cdot a_{n-2} = z - n \cdot a_{n-2} \end{array} \]
итд.
Према томе \(z_{i-1} - z_i = z - n \cdot a_{i-1}\), тј.
\[z_0 = z, \qquad z_i = z_{i-1} - z + n \cdot a_{i-1},\ \textrm{за}\ i>0.\]
Дакле, тежински збир после померања за једно место улево можемо једноставно израчунати без померања низа на основу тежинског збира низа пре померања и збира свих елемената низа.
Имплементацију можемо извршити на следећи начин. Израчунамо тежински збир полазног низа \(z_0 = \sum_{i=0}^{n-1}{i \cdot a_i}\) и класични збир свих елемената низа \(z = \sum_{i=0}^{n-1} a_i\) (једноставним алгоритмом сабирања елемената низа). Од свих збирова треба израчунати највећи и одредити после колико ротација се та највећи збир постиже. Максимум ћемо иницијализовати на први израчунати тежински збир, а број померања ћемо иницијализовати на 0. Затим рачунамо тежинске збирове за низове добијене померањем низа за једно место улево \(i\) пута, и то редом за \(i\) од \(1\) до \(n-1\). Тежински збир \(z_i\) за низ добијен након \(i\) померања рачунамо тако што претходни тежински збир \(z_{i-1}\) умањимо за збир свих елемената \(z\) и увећамо за \(n \cdot a_{i-1}\). Проверавамо да ли је добијени тражени збир већи од дотадашњег максимума и ако јесте коригујемо максимум.
Наравно, све аритметичке операције вршимо по датом модулу.
Сложеност. Приметимо да време потребно за израчунавање почетних збирова линеарно зависи од дужине низа \(n\), док је за израчунавање сваког наредног збира довољан константан број операција, тако да је укупна временска сложеност алгоритма линеарна тј. \(O(n)\).
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1234567;
// zbir x i y po modulu mod
int zm(int x, int y, int mod) {
return (x % mod + y % mod) % mod;
}
// razlika x i y po modulu mod
int rm(int x, int y, int mod) {
return (x % mod - y % mod + mod) % mod;
}
// najveci tezinski zbir posle ciklicnog pomeranja
int maksTezinskiZbirNakonRotacije(const vector<int>& a) {
// broj elemenata niza
int n = a.size();
// izracunavamo tezinsku sumu i*a[i] i obicnu sumu elemenata a[i] po
// modulu mod
int tezinskiZbir = 0;
int suma = 0;
for (int i = 0; i < n; i++) {
tezinskiZbir = zm(tezinskiZbir, i * a[i], mod);
suma = zm(suma, a[i], mod);
}
// najveca do sada vidjena tezinska suma
int maxTezinskiZbir = tezinskiZbir;
for (int i = 1; i < n; i++) {
// rotacija za jedno mesto ulevo na sledeci nacin menja tezinsku sumu
tezinskiZbir = zm(rm(tezinskiZbir, suma, mod), n * a[i - 1], mod);
// proveravamo da li je dobijena tezinska suma veca od do tada
// najvece
if (tezinskiZbir > maxTezinskiZbir)
maxTezinskiZbir = tezinskiZbir;
}
return maxTezinskiZbir;
}
int main() {
// ubrzavamo ucitavanje elemenata niza
ios_base::sync_with_stdio(false);
// ucitavamo broj elemenata niza
int n;
cin >> n;
// ucitavamo niz
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo maksimalni zbir
cout << maksTezinskiZbirNakonRotacije(a) << endl;
return 0;
}