Eugene and Big Number

general
1

Editorial of this Eugene and Big Number | HackerRank problem says We can solve this recurrence for such large values by a technique known as Matrix Exponentiation.what is Matrix Exponentiation.I googled it but still no idea.please help

1 Like
2

Matrix exponential is just like an Binary exponential or modular exponential(which you have already familiar i think). SO i.e., the complexity is still log ( N )… But what foe d^3 in editorial solution?

So answer is this extra factor comes into play as we are multiplying the 2-D Matrix which is taking a factor of (d^3) in worst case!

So overall time complexity will be written as Log (N) * (d^3)… Excluding test case T.

Just debug the solution by yourself after that your whole doubt will be cleared.

You can see the codechef discussion seesion here or read the full article of Matrix exponential at geeks

1 Like
3

Hey @anno, this problem is actually what is known as a linear recurrence which can solved using the process of matrix exponentiation. I learnt about it from two links which I found on this incredibly useful list. I’m putting the two links here and you can also find them in the list. I hope this will help you too :slight_smile:

  1. A tutorial on Codechef
  2. A blog by Zobayer Hasan
1 Like
4

Actually there is another technique other than matrix exponentiation.

Let me explain this : 123 , 3 times in a row is : 123123123 .

Now,

123123123 = 123*(10^3)^2+123*(10^3)+123 = 123((10^3)^2+10^3+1)).

The above equation is a GP and can be solved easily using fast modular exponentiation.

Here 10^3 = 10^(log10(123)+1).

Edit:- Changed the error in the 10^3 calculation.

5

You can solve it in O((logn)^2) by using fast exponentiation and logrithmic recurrence.
here is the code : http://code.geeksforgeeks.org/8f5V0B

1 Like
6

I belive that we can solve this by observing the fact that a single reminder is repeated after a particular number of repititions of a single number. but my array is not designed for input of order 10^12. how shuold i store such large inputs.

1 Like
7

I tried two approaches one using vector<vector > to create a matrix and then did what was asked and another approach by using **v (pointer to a pointer) to create 2d arrays (matrices)as the first one was not working.

It is strange but my first approach is giving different outputs every time i run it on the same compiler and also getting wa for rest of test cases. Can someone please help me with this (Not getting right answer even in the second approach though ans is not changing).
My first solution- pMo16z - Online C++0x Compiler & Debugging Tool - Ideone.com
Second solution - h6YiDy - Online C++0x Compiler & Debugging Tool - Ideone.com

Thanks,

8

Thanks for the reply. No, I have taken “vector<vector >v(n,vector(n))” as 2D matrix whose rows are n, n is 2 and number of columns are also 2. So every time I require a 2D matrix i am using this and then performing 2 operations on 2D matrices (multiplication and power) by the function matmul and matpow.

I saw this in the editorial of eugene and a big number of hacker rank but still cannot figure out my mistake and the most important thing is that of different outputs every time (I use sublime).

Ohk…Are you saying this because of the bad alloc error? But I have not allocated large memory its just for a 2x2 matrix.

9

Can you explain more.

10

Which part do you need explanation?

11

Are you trying to declare a vector of size 10^12?

12

Hi, I am using the formula:
X = A*(10^(NL) - 1)/(10^L - 1) where L = length of A
but i am getting a wrong answer, could it be because the denominator term would not be coprime with m in some cases?