CODECRCK - Editorial

easy-medium
editorial
math
sept15

#1

PROBLEM LINK:

Practice
Contest

Author: Alex Gu
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math

PROBLEM:

Given two sequences a and b and a recurrence to calculate a_i and b_i, we need to calculate a certain value c when a pair of corresponding terms of a and b are given.

EXPLANATION:

Subtask 1
For subtask 1, we can simply iterate from i to k (as the case may be) and use the recurrences to calculate a_k and b_k.

Now, there are two cases:

  • When i \leq k.
    In this case, the given recurrence can be used directly. I.e.,
    a_{n+1} = x(a_n + b_n) - xy(a_n - b_n)
    b_{n+1} = x(a_n - b_n) + xy(a_n + b_n)

  • When k < i.
    In this case, the following recurrence can be derived and used.
    a_{n-1} = \frac{a_n + b_n - y(a_n - b_n)}{2x + 2xy^2}
    b_{n-1} = \frac{a_n - b_n + y(a_n + b_n)}{2x + 2xy^2}

The last step is to calculate 2^s. The calculation must be done in floating type to ensure that the answer doesn’t overflow. The in-built exponentiation function in most of the programming languages can do this job easily.

Subtask 2
Let us look at the original recurrences given to us, i.e.,
a_{n+1} = x(a_n + b_n) - xy(a_n - b_n)
b_{n+1} = x(a_n - b_n) + xy(a_n + b_n)

What do they tell us? Basically, we are given a_{n+1} and b_{n+1} in terms of a_n and b_n. Let us go a step further and try to calculate a_{n+2} and b_{n+2} in terms of a_n and b_n.

For doing this, we first note the following terms:
a_{n+1} + b_{n+1} = 2xa_n + 2xyb_n
a_{n+1} - b_{n+1} = 2xb_n - 2xya_n

Now, we use our original recurrence to calculate a_{n+2} and b_{n+2}.
a_{n+2} = x(2xa_n + 2xyb_n) - xy(2xb_n - 2xya_n) = a_n(2x^2 + 2x^2y^2)
b_{n+2} = x(2xb_n - 2xya_n) + xy(2xa_n + 2xyb_n) = b_n(2x^2 + 2x^2y^2)

Since, x = \sqrt 2 and y = \sqrt 3, thus, (2x^2 + 2x^2y^2) = 16.
This leads us to a very important observation:
a_{n+2} = 16a_n
b_{n+2} = 16b_n

It tells us that if i and k are both even or both odd, then a_k + b_k = c(a_i + b_i), where c is a constant. When k-i = 2, c = 2^4; when k-i = 4, c = 2^8, and so on. Thus, c = 2^{2(k-i)}.
When i and k are of different parities, i.e., one is even and the other is odd, we can first calculate a_{i+1} and b_{i+1} and then calculate a_k and b_k.

The last part is to calculate 2^s, which has already been explained in subtask 1.

COMPLEXITY:

All the operations take constant time except the use of exponentiation function. The in-built exponentiation function is implimented as \mathcal{O}(\log N) algorithm in all the programming languages.
Net complexity: \mathcal{O}(\log N).

SAMPLE SOLUTIONS:

Author
Tester
Editorialist


#2

Hi we are getting access denied for the sample solutions. Please fix it.


#3

i have used the same approach as discussed but only 9 out of 13 test cases passed …
After analyzing the test cases i got to know that when a big number (say 2^16) is multiplied with a double then answer is approximated and hence i was getting wrong answer
SO MY QUESTION IS HOW CAN I IMPROVE ACCURACY IN MULTIPLICATION WITH A DOUBLE OR IS THERE ANY OTHER WAY OUT??
LINK TO MY SUBMISSION IS link text


#4

Can you please explain the calculation of 2^s? I mean s is large. So the result will definitely overflow. How can this be avoided in floating point calculation?


#5

@dragonemperor please note that the final answer is between (-10^9,10^9) so if s is large than in that test case 2*(i-k) would be somewhat near about s hence always you should calculatee the final exponent of 2 !!


#6

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* + b* (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.


#7

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?


#8

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.


#9

Editorial solution is showing wrong results.


#10

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.


#11

I used Matrix Diagonalization to solve this problem. We can represent the equations as follows:

 Mn+1                  Q             Mn  

[{An+1},{Bn+1}]=[{x-y,x+y},{x+y,x-y}]*[{An},{Bn}] (where x=sqrt(2),y=sqrt(6))

Now, Q can be written as PDP^-1 where P is the modal matrix and D is the diagonal matrix.

  1. 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

  2. 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.


#12

What’s wrong with my solution?
https://www.codechef.com/viewsolution/8130432


#13

Good Question (y)


#14

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]=16
a[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]=16
b[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


#15

The code given by the editorialist fails to run for the subtask 2. Please figure out the mistake in it.
Thank You!


#16

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. https://www.codechef.com/viewsolution/8156597


#17

https://www.codechef.com/viewsolution/8164155
can someone please tell what is the mistake in this solution. I have tried several changes but nothing worked. Thanks in advance!


#18

can’t understand why my code fails for task 6
https://www.codechef.com/viewsolution/8169674


#19

The Test Case 10 was out of constraints. What action was taken ??


#20

https://www.codechef.com/viewsolution/8116132
whats wrong with my solution??