Питања
Аутор: Игор Павловић
Текст и тест примери: Игор Павловић
Анализа решења: Алекса Плавшић
Тестер: Александар Златески
Дефинишимо са d_i = \frac{y_i - x_i}{k_i} + 1. У i-том упиту је потребно израчунати суму тачно d_i бројева.
Први подзадатак
Као помоћ потребно је користити формулу за суму првих n природних бројева \sum_{i=1}^{n} i= \frac{n\cdot(n+1)}{2}
Решење за i-ти упит можемо записати у обликз \sum_{j = 0}^{d_i -1} (x_i + j \cdot k_i) = \sum_{j = 0}^{d_i-1} x_i + k_i \cdot \sum_{j = 0}^{d_i-1} j =
d_i \cdot x_i + k_i \cdot \frac{(d_i - 1)\cdot d_i}{2}. Последње написану формулу можемо израчунати у временској и меморијској сложености O(1) по упиту.
Други подзадатак
Поред формуле из првог подзадатка потребно је искористити формулу за суму првих n квадрата природних бројева \sum_{i=1}^{n} i^2= \frac{n \cdot(n+1) \cdot(2n+1)}{6}
На сличан начин можемо решити и други подзадатак, уз мало већу манипулацију са математичким формулама. Тако да решење можемо представити у облику \sum_{j = 0}^{d_i -1} (x_i + j\cdot k_i)^2 = \sum_{j = 0}^{d_i -1} (x_i^2 + 2\cdot x_i \cdot k_i \cdot j + (j\cdot k_i)^2) = = \sum_{j = 0}^{d_i -1} x_i^2 + 2\cdot x_i \cdot k_i \cdot \sum_{j = 0}^{d_i -1} j + k_i^2 \cdot \sum_{j = 0}^{d_i -1} j^2 = = d_i \cdot x_i^2 + 2 \cdot x_i \cdot k_i \cdot \frac{d_i\cdot (d_i - 1)}{2} + k_i^2 \cdot \frac{(d_i -1)\cdot d_i \cdot (2 \cdot d_i - 1)}{6}. Слично као и у првом подзадатку, наведени израз можемо израчунати у временској и меморијској сложености O(1) по упиту.
Трећи подзадатак:
У i-том упиту можемо проћи кроз свих d_i бројева и израчунати њихову суму. У најгорем случају за наш програм потребно је N итерација по упиту (на пример x_i=1, y_i=N, k_i=1). Временска сложеност описаног алгоритма је O(NQ).
Четврти подзадатак:
Алгоритам описан у трећем подзадатку је ефиксан за упите чија је вредност d_i релативно мала. Поставићемо границу B, и сваки упит за који важи d_i \leq B обрадићемо као и у трећем подзадатку. У случају d_i > B, вредност броја k не може бити већа од \frac{N}{B}. Направићемо матрицу D димензије \frac{N}{B} \times N, где вредност D[i][j] представља \sum A_x тако да важи x \mod i = j \mod i и x\leq j. Описану матрицу можемо израчунати у временској сложености O(\frac{N^2}{B}), слично поступку прерачунавања префиксних сума. Када израчунамо матрицу D одговор на упит (x_i, y_i, k_i), за који важи d_i > B можемо добити као D[k_i][y_i] - D[k_i][x_i] + A_{x_i} y временској сложености O(1). Коначан алгоритам који комбинује претходна два у зависности од вредности d_i има временску сложеност O(\frac{N^2}{B} + Q \cdot B) и меморијску O(\frac{N^2}{B}). Ако константу B поставимо на вредност B~\sqrt N добили смо алгоритам временске сложености O(N \sqrt N + Q \sqrt N) и меморијске O(N\sqrt N).
Приметити да меморијску сложеност алгоритма можемо побољшати ако упите за које важи d_i > B обрађујемо у групама по истој вредности k_i (нпр. прво обрадимо све упите за које важи k_i = 1, затим k_i = 2 итд). У овом случају је довољно памтити само један низ D који би се након сваке групе једнаких ресетовао на 0. Постоје и многи други начини оптимизације меморије на линеарну, међутим то се не захтева за максималан број бодова у задатку.