Брой 26 на Списание Инфоман
 


Есенен турнир 2004, Задача B2. СРЕДНА СТОЙНОСТ И ВАРИАЦИЯ

Уловието на задачата може да прочетете тук.

Решение

Първото нещо, което трябва да се направи, е да се опрости формулата за средното аритметично на квадратите на отклоненията на отделните точки от средната стойност E.Използвайки формулата за повдигане на квадрат и групирайки събираемите получаваме:

S = ((x1-E)2 + (x2-E)2 + ... + (xn-E)2)/n = (x12 + x22 + … + xn2 – 2.E.(x1 + x2 + .. + xn) + n.E2 )/n

От дефиницията за E имаме

E = (x1 + x2 + x3 + ... + xn) / n

Следователно

(x1 + x2 + x3 + ... + xn) = E.n

Оттук

S = ((x1-E)2 + (x2-E)2 + ... + (xn-E)2) / n = (x12 + x22 +  ... + x n2 – 2.E.(x1 + x2 + ... + xn) + n.E2) / n = (x12 + x22 +  ... + xn2)/n – (2.E2.n + n.E2) / n =  (x12 + x22 +  ... + xn2)/n – E2

За решението се използва един стандартен подход, който е подходящ когато се изисква да се намери сума на последователност от числа в масив. За целта използваме един допълнителен масивT, в който на позиция T[i]  си пазим сумата от първитеi числа в масива. Така

T[0] = 0

T[1] = s[1]

T[2] = s[1] + s[2]  = T[1] + s[2]

T[3] = s[1] + s[2] + s[3]  = T[2] + s[3]

...

T[n] = T[n-1] + s[n]

Където с s[i] сме отбелязали i-тия елемент от входния масив. Очевидно този масив се получава с O(N) операции. Тогава от начина, по който сме дефинирали T следва, че сумата на елементите между дадени два индекса a и b е точно

Sum(a,b) = T[b] – T[a-1]

а да решим поставената ни задача ще дефинираме два масива, които притежават горното свойство – масив T, който ще пази сумата на първите K числа и масивTsqr, който ще пази сумата от квадратите на първите K числа. Тогава стойностите на E и S за  даден интервал [p;q]са съответно:

Е = (T[p]-T[q-1]) / (p-q+1)

S = (Tsqr[p]-Tsqr[q-1]) / (p-q+1) + E2

Тогава за всеки интервала ние отговаряме със сложност O(1). Така сложността на дадения алгоритъм е O(N+K*1) = O(N+K).

Примерна реализация:

#include <stdio.h>

#define MAXN 500001

int sum[MAXN]; // sum[X] = sumata na pyrwite X chisla ot whoda
int sqr[MAXN]; // sqr[X] = sumata ot kwadratite na pyrwite X chisla ot whoda

int main () {
double E;
int n,m,i,a,b;
	scanf("%d%d",&n,&m);
	// presmiatame masiwite sum i sqr
	for (i=1;i<=n;i++) {
		scanf("%d",&a);
		sum[i] = sum[i-1] + a; 
		sqr[i] = sqr[i-1] + a*a;
	}

	for (i=0;i<m;i++) {
		scanf("%d%d",&a,&b);
		// izchisliawame E i S po opisanata formula
		printf("%.4lf %.4lf\n",E = ((sum[b] - sum[a-1])/ 
		(double)(b-a+1)),(sqr[b] - sqr[a-1])/(double)(b-a+1) - E*E);
	}
	return 0;
}

Автор: Слави Маринов


обратно към брой 26