this seem to be the case with lot of recent challenges, that’s why I stopped participating
An alternative way to solve this, albeit slightly slower would be to notice that each E(n-i)=E(n)- b(i) where b(i) forms a recursive sequence given by b(i) = 2b(i - 1) - b(i - 2) + 2 with starting values b(0)=0 and b(1)=2. We know that E(1)=0. Thus, E(1) = E(n) - b(n - 1) = 0 which means E(n) = b(n - 1). Thus, E(x) = E(n) - b(n - x) = b(n - 1) - b(n - x).
Thus, our task is reduced to fast computation of values of the sequence b, which can be done using matrices in O(log(n)) time. We notice that,
[2 -1 2] [ b(i) ] [b(i + 1)]
[1 0 0] x [b(i - 1)] = [ b(i) ]
[0 0 1] [ 1 ] [ 1 ]
Let’s call the square matrix on the left M. Hence, we can compute b(i) for all i>1 by exponentiating this matrix (which would take O(log(n)) time) to the i-1 power and multiplying it by,
[b(1)]
[b(0)]
[ 1 ]
The total runtime now would be O(T log(n)) which is sufficient for the given bounds.
The implementation for this is given below.
https://www.codechef.com/viewsolution/67803196
how did you come up with b(i)?
how are the equations identical? where in the new array of equations [1, M=2*N]
E(M/2) = E(N) is only related to E(M/2-1)
and E(M/2+1) is only related to E(M/2+2)
where in the old set of equations, every i is related to i-1 and i+1 (expect i=1 and i=M),
I see that they are symmetrical but a don’t see how they are identical.
another pattern recognition solution:
initially we have:
ex(1) = 0
ex(i) = 0.5*(1+ex(i+1)) + 0.5*(1+ex(i-1))
ex(n) = 0.5*(1+ex(n)) + 0.5*(1+ex(n-1))
ex(n) = 0.5*(1+ex(n)) + 0.5*(1+ex(n-1))
ex(n) = 0.5 + 0.5*ex(n) + 0.5 + 0.5*ex(n-1)
0.5*ex(n) = 1 + 0.5*ex(n-1)
=> ex(n) = 2 + ex(n-1)
we have:
ex(1) = 0
ex(2) = 1 + 0.5(ex(1) + ex(2))
= 1 + 0.5*ex(3)
ex(3) = 1 + 0.5(ex(2) + ex(4))
= 1 + 0.5*(1+0.5*ex(3)) + 0.5*ex(4)
= 1 + 0.5 + 0.25*ex(3) + 0.5*ex(4)
= (1/(1-0.25)) * (1.5 + 0.5*ex(4))
= c + p*ex(4)
in general:
ex(i) = c0 + p0*ex(i+1)
ex(i+1) = c + p*ex(i+2)
= 1 + 0.5(ex(i) + ex(i+2))
= 1 + 0.5*ex(i) + 0.5*ex(i+2)
= 1 + 0.5(c0+p0ex(i+1)) + 0.5*ex(i+2)
= 1 + 0.5*c0 + 0.5*p0*ex(i+1) + 0.5*ex(i+2)
= (1/(1-0.5*p0)) * (1+0.5*c0 + 0.5*ex(i+2))
= (2/(2-p0)) * ((2+c0)/2 + 0.5*ex(i+2))
= (2+c0)/(2-p0) + (1/(2-p0))*ex(i+2))
= c + p*ex(i+2)
=>
c = (2+c0)/(2-p0)
p = 1/(2-p0)
=> pattern found:
i -> (
c_i = (i-1)
p_i = (i-1)/i
)
=> ex(n-1) = (n-2) + (n-2)/(n-1) * ex(n)
= c + p*ex(n)
we have:
ex(n) = 2 + ex(n-1)
= 2 + (c + p*ex(n))
= 1/(1-p) * (2+c)
= (n-1)*n
=> ex(n) = (n-1)*n
// now we can calculate ex(n)
// and we need to find a way te calculate ex(x) from it
ex(n-1) = c + p*ex(n)
c = n-2
p = (n-2)/(n-1)
ex(n-2) = c + p*ex(n)
c = 2*(n-3)
p = (n-3)/(n-1)
ex(n-3) = c + p*ex(n)
c = 3*(n-4)
p = (n-4)/(n-1)
=> pattern found:
ex(x) = c + p * ex(n)
c = d*(n-d-1)
p = (n-d-1)/(n-1)
where: d = n-x
ex(x) = c + p * ex(n)
= c + p * (n*(n-1))
= d*(n-d-1) + (n-d-1)/(n-1) * n*(n-1)
= d*(n-d-1) + n * (n-d-1)
= (n-d-1) * (n+d)
1 Like