You could also have derived the sum in the following way:
Given that a[n+2] = a[n] * 2^4 and b[n+2] = b[n] * 2^4, you can calculate the result as a pair [number, exponent], where the actual number will be number * 2^exponent, like this: a[n+2x] = a[n] * 2^(4*x) and a[n+2x+1] = a[n+1] * 2^(4*x). The number is just a[i] + b[i] (or a[i+1] + b[i+1], in case of odd difference between the given term index and the requested term index), and the exponent is (4*(diff / 2)) - s. (note here that diff might be negative at this point, no worries)
Then, you just multiply the two at the end. The statement imposes no overflow from this point onwards.
Can someone explain the statement “in-built exponentiation function in most of the programming languages can do this job easily.”
How we are calculating 2^(1000) without any overflow?
Can someone explain to me how can you get to the formula for an-1 and bn-1 for the subtask 1 case k<i?
I tried pretty hard to do it,but all I can do is write an-1+bn-1 from an+bn and an-bn.
Thanks.
One way to derive the recurrence relations would be to write a brute force solution(using recursion or in a for loop), and print An and Bn upto some value say 10. Then it is easy if overflow is taken care of.
Now, Q can be written as PDP^-1 where P is the modal matrix and D is the diagonal matrix.
Now, if k>i,
the we need to find B^(k-i) which is essentiall PD^(k-i)P^(-1). Here, P and P^-1 are precalculated as given here: Diagonalize on Wolfram Alpha
Now, if we find D, we find the eigen values are -4 and 4. So now if we take these out from D, and divide both sides of the equation by 4^(k-i), we get the above equation as Mn+1/(4^(k-i)). Also, since we have to find An+Bn/2^s, write 2^s as 4^(s/2) and essentially we have to find An^(i-k-(s/2)) and same for B. Now since D is simply [{-1,0},{0,1}], the power of D is easily calulate
Now if k>i, then you basically have to find the inverse of (PDP^-1), take if to the other side, and find Mk in terms of Mi (repeat the almost exact same procedure)
I have tried to explain my best. Maybe a lot of people would not understand directly but my code here is pretty lucid : Submission
Any idea why it fails of 3-4 testcases of subtask 2? It so happens that @grebnesieh has used the exact same procedure here and it seems to pass.
Given (i). a[n+1] = x(a[n]+b[n])−xy(a[n]−b[n]) (ii). b[n+1] = x(a[n]−b[n])+xy(a[n]+b[n])
Adding the above two equations, we get (iii). a[n+1]+b[n+1] = 2xa[n]+2xyb[n]
Subtracting the given two equations, we get (iv). a[n+1]−b[n+1] = 2xb[n]−2xya[n]
Therefore,
a[n+2] = x(a[n+1]+b[n+1])−xy(a[n+1]−b[n+1])
Using (iii) and (iv) in the above equation we get
a[n+2] = 2xx*(1+yy)a[n]
Substituting values of x and y, (v). a[n+2]=16a[n];
Similarly,
b[n+2] = x(a[n+1]-b[n+1])+xy(a[n+1]+b[n+1])
Using (iii) and (iv) in the above equation we get
b[n+2] = 2xx*(1+yy)b[n]
Substituting values of x and y, (vi). b[n+2]=16b[n];
Therefore,
a[n+k] = (2^4)^(k/2)a[n] = 2^(2k)*a[n] (where k is even)
b[n+k] = (2^4)^(k/2)b[n] = 2^(2k)*b[n] (where k is even)
Thus, value of Q would be calculated differently for two cases: 1. When (k-i)%2==0
Since , Q = (a_k + b_k) / (2^s)
num=pow(2.0,(2*(k-i))-s); (vii). a[k]=a[n]*num; (viii). b[k]=b[n]num;
ans=a[k]+b[k];
NOTE: We are not calculating 2^s and 2^(k-i) individually and then divide them, this would cause the condition of overflow, instead we are calculating 2^(2(k-i))-s) 2. When (k-i)%2!=0
In this case we would first calculate a[k-1] and b[k-1] (since, (k-i-1)%2==0) using the equation (vii) and (viii) and then using equation (i) and (ii), we will calculate a[k] and b[k].
Code attached link text
best part was the answer required a precision of only 0.01 so i could use ans = pow(2.0,log2(ans)) to get the solution! i did it exactly the way @retrograd said above. CodeChef: Practical coding for everyone
In the above three codes, one thing that is to be noted is, the first one seemed manipulative to submit the solution the PYPY instead of PYTH. The second and third codes were detected by the scanner and the first one was not as the ratings of these users suggest.
So, my question is don’t they consider laguages/ implementation with same syntax may have plagiarised codes, or it is just a mistake?
My second question is regarding these two codes, in which there is just one difference of variable name, and everything else is exactly the same:
What may be possible reason these codes got undetected? Isn’t it a setback for those who try real hard for 10 days and these people go undetected by their manipulations.
Codechef, please consider these maipulations too, this is really serious!!
for that you need to modify your equations in such a way that the value of 2^k calculated at any point of time remains computable…means k should be choosed in such a way that it is always <=2000, means u cannot perform something like 2^5000/2^3000…This was the catch of the question.