Hello guys
in this problem we have n equation with n unknown
than solved with Gause-Jordan modification
a0 a1 a2 a3 a4 a5 .... an
if a1=(a0+a2)/2 - c0 then
2a1 - a2 = a0- 2c0
if a2=(a1+a3)/2 - c1 then
-a1 +2a2 - a3= -2c1
....
2a1 - a2     = a0- 2c1
-a1 +2a2 - a3= -2c2
-a2 +2a3 - a4= -2c3
-a3 +2a4 - a5= -2c4
....
-an +2an-1 - an+1 = -2cn
e.g for n=5:
2  -1   0   0   0   a0-2c1
-1  2   -1  0   0   -2c2
0   -1  2   -1  0   -2c3
0   0   -1  2   -1  -2c4
0   0   0   -1  2   a6-2c5
and now you must solve the top diagonal "-1" of
matirs ( start of last row)and finish.
the order is O(n)
sudo code is:
m[0 ... n]
a=2;
while(--n){
 f= 1/a;
 m[n-1]= m[n-1]+ f*m[n];
 a = 2-f;
}
cout<< m[0]/a ;


Edited by author 01.03.2008 22:56

I did the same stuff in my solution, but I used Cramer's rule to calculate the answer. I used recurrent sequence for calculating determinants. Final complexity is O(n), but the it is easily can be calculated in O(logn).