CODECRCK - Editorial

editorial
, , ,
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

1 Like
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 !!

3 Likes
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[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.

7

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.

8

this way of writing (a<<p) will not work if p>64…and who marked this as community wiki!!!

9

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?

10

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.

11

so what’s the correct way ?

12

Did you do it by writing the recurrence in matriceal form?

13

Editorial solution is showing wrong results.

14

change the ints into long long and it will work.

15

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.

3 Likes
16

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.

17

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

1 Like
18

Good Question (y)

19

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

1 Like
20

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