CODECRCK - Editorial

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.

Editorial solution is showing wrong results.

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

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.

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

1 Like

Good Question (y)

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

1 Like

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

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

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!

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

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

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

I know I should ask this as a question, but I do not have enough karma points, so I’m commenting it here.

I want to know how does codechef detect plagiarism as the following three codes from the SEPT15 long challenge seem exactly same to me:

problem CODECRCK:

https://www.codechef.com/viewsolution/8142078

https://www.codechef.com/viewsolution/8151690

https://www.codechef.com/viewsolution/8164233

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:

https://www.codechef.com/viewsolution/8072373

https://www.codechef.com/viewsolution/8156642

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

1 Like

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.

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

so what’s the correct way ?

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