10870 - Recurrences

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

10870 - Recurrences

Post by kp » Tue Jun 28, 2005 2:24 am

I solved this problem using matrix multiplication.
The complexity of my algorithm is about
d^3*log(n/d) = O(logN). d <= 15 by the statement.

My program runs in 0:00.326 s.
Are there any other (faster) algorithms?
Maybe some tricks?

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Tue Jun 28, 2005 9:29 am

We can easily speed up the multiplication process... ie, d^3 can be reduced... think about it. :wink:

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Tue Jun 28, 2005 12:02 pm

Yes, I thought about that, but I think that using FFT to find
matrix product of matrices not bigger than 15x15 is like
"shouting birds from the cannon" (I don't know the english
equivalent of this russian proverb, sorry :)).

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Tue Jun 28, 2005 12:32 pm

Maybe exists a O(1) algorithm? (small simple formulae :))

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Jun 28, 2005 12:42 pm

Well, most probably there's nothing much better than the solution with matrices. The general form of the solution is something along the lines:

Code: Select all

n-th term  =  \sum_{i=1}^d  y_i (x_i ^n)
where x_i are the roots of the characteristic polynomial of the recurrence and y_i are coefficients depending on the initial values.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

need to learn...

Post by sohel » Wed Jun 29, 2005 11:24 am

Can someone explain how matrix multiplication is implemented in order to solve this problem?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Jun 29, 2005 12:59 pm


kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Wed Jun 29, 2005 1:06 pm

Let
1. F(n) = A(1)*F(n-1)+...+A(d)*F(n-d).
2. F[k*d] = column (F(d*(k-1)+1), F(d*(k-1)+2), ..., F(k*d)), k=1..infinity

It's not difficult to find quadric matrix A of size d, that

F[2*d] = A*F[d]

The main property of the matrix A is that for every k>0 we have

F[(k+1)*d] = A*F[k*d] , so

F[k*d] = A*F[(k-1)*d] = A*A*F[(k-2)*d] = ... = A^(k-1)*F[d] , k>0

So to find F(n) you should calculate M-th power of A, where M
is ((n-1) div d), after that you multiply row ((n-1) mod d)+1 of this matrix
to the column Start (initial values) and get the answer.

P.S.:
Of cource, we can get the N-th power of quadric matrix of size d
for the d^3*log(N).

[EDIT]: misof is faster :)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

thanks..

Post by sohel » Sat Jul 02, 2005 3:44 pm

Thanks to Misof and KP.
..got AC.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

TLE with Pascal

Post by FAQ » Sun Dec 18, 2005 6:44 am

Someone who have got AC with Pascal please help me
I used algorithm with O(d^3logN) but I still got TLE, I think MOD operation in Pascal is too slow.
Can we multiply 2 matrixes faster than this one:

Code: Select all

ACed
I tried to avoid "Mod m" then I got WA, if you have some large test case please tell me
Last edited by FAQ on Sun Dec 18, 2005 5:09 pm, edited 1 time in total.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sun Dec 18, 2005 4:43 pm

I used this routines:

Code: Select all


type
  TMatrix = array [1..15, 1..15] of integer;

..............

function MatrixMul(const A, B: TMatrix): TMatrix;
 var
   i, j, k: integer;
begin
  for i:=1 to d do
    for j:=1 to d do begin
      result[i,j]:= 0;
      for k:=1 to d do begin
        inc(result[i,j],(A[i,k]*B[k,j]) mod m);
        result[i,j]:= result[i,j] mod m;
      end;
    end;
end;

function MatrixPow(const A: TMatrix; pow: integer): TMatrix;
 var
   i: integer;
begin
  fillchar(result,sizeof(result),0);
  if pow=0 then begin
    for i:=1 to d do result[i,i]:=1;
  end else if pow=1 then result:= A
  else begin
    B:= MatrixPow(A,pow div 2);
    B:= MatrixMul(B,B);
    if odd(pow) then
      result:= MatrixMul(A,B)
    else result:= B;
  end;
end;

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sun Dec 18, 2005 5:08 pm

Great, I got AC now, thank you a lot, kp :)

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10870 - Recurrences

Post by Shafaet_du » Sat May 21, 2011 10:23 pm

Nice problem to learn matrix exponentiation(You should try 10229 first though).
Try this:

Code: Select all

6 345345 443
999999 12443434 3214234 34535 456456 21424
7676 435 34 78 34 23

10 4468895 231123
9999 122344 321743 3412 12156 223424 23345555 76  222   12213
7676 435 34 78 34 23 456 8979 2323 2345

18 412455 2334523
9999   999999 12443434 3214234 34535 456456 21424 122344 321743 3412 12156 223424 23345555 76  222   12213 234  666
7676 435 34 78 34 23 7676 435 34 78 34 23 456 8979 2323 2345  23445 6666

1 3455 100007
17
23

0 0 0
out:

Code: Select all

195
206146
1958147
24190

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10870 - Recurrences

Post by Shafaet_du » Sat May 21, 2011 10:26 pm

Slight mistake in above input. D should be less than 15 but i gave 18. but ac codes should be able to pass it i think,

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 10870 - Recurrences

Post by matrix2220 » Tue Sep 09, 2014 5:25 pm

Hint:

Code: Select all

 |  f(n+1)  |   | a1 a2 ...... ad |   |  f(n)  |
 |  f(n)    |   | 1  0  0 .... 0  |   | f(n-1) |
 |    .     | = | 0  1  0 .... 0  | * |   .    |
 |    .	  |   | ..............  |   |   .    |
 | f(n-d+1) |   | ...........1 0  |   | f(n-d) |
 
 Generalization:
 
 |  f(n+k)  |   | a1 a2 ...... ad |^k    |  f(n)  |
 | f(n+k-1) |   | 1  0  0 .... 0  |      | f(n-1) |
 |    .     | = | 0  1  0 .... 0  |  *   |   .    |
 |    .	  |   | ..............  |      |   .    |
 |f(n+k-d+1)|   | ...........1 0  |      | f(n-d) |
 
 Answer is f(n+k) , k = n-d

Abdelrahman Ali (MaTrix)

Post Reply

Return to “Volume 108 (10800-10899)”