10743  Blocks on Blocks
Moderator: Board moderators

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
10743  Blocks on Blocks
Can someone give some hints? DP won't work (too slow), and I'm thinking of using the Qmatrix method to get the required O( log n ) running time, but I haven't been able to modify it correctly..

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
I haven't solved this problem yet, but I do know that there is a very simple recursive formula for the requested number:
a[1] = ...
...
a[5] = ...
a[n] = ? a[n1]  ? a[n2] + ? a[n3]
with positive integers in stead of question marks (not giving it all away).
So whenever three values in a row have occured earlier, we know our period, right?
a[1] = ...
...
a[5] = ...
a[n] = ? a[n1]  ? a[n2] + ? a[n3]
with positive integers in stead of question marks (not giving it all away).
So whenever three values in a row have occured earlier, we know our period, right?
As usual I managed to find the recurrence through experimentation, but have no idea as to why it works. Did you actually derive the recurrence, or did you too find it by experimentation? If the first, I would be very interested in seeing the derivation, so if you could drop a hint or two I would be grateful.Maniac wrote:I haven't solved this problem yet, but I do know that there is a very simple recursive formula for the requested number
(Larry: I used the matrix method to solve the problem)
Consider for example Fibonacci numbers.Larry wrote:Per: For these problems, I generate, bruteforce, and see if I can guess/recognize an easy formula or something..
How do you use the matrix method for an arbitrary a_1, a_2, a_3, a_4, and A, B, C? I've been trying to derive something, but no luck.. thanks.. =)
Let v = [ F_n , F_{n+1} ] be a vector, A a matrix defined as follows:
Code: Select all
A = ( 0 1 )
( 1 1 )
This means that [ F_0 , F_1 ] . A^n = [ F_n , F_{n+1} ]
To compute F_n, you only have to compute A^n. This can be done in logarithmic time (e.g. by repeated squaring).
Of course, for this task the matrix will be of size 3x3 and it will be different
How do you guys make quotes with author names above?
Larry: if f[n+1] = a f[n] + b f[n1] + c f[n2] then the matrix is {{a,b,c},{1,0,0},{0,1,0}}. Does that help?
Per: sorry, no derivation just calculating the first few values and using the encyclopedia of integer sequences... I haven't got a clue why the formula works.
P.S. By the way, the NWERC rules have changed and I can't compete in Lund cause I'm too old
Larry: if f[n+1] = a f[n] + b f[n1] + c f[n2] then the matrix is {{a,b,c},{1,0,0},{0,1,0}}. Does that help?
Per: sorry, no derivation just calculating the first few values and using the encyclopedia of integer sequences... I haven't got a clue why the formula works.
P.S. By the way, the NWERC rules have changed and I can't compete in Lund cause I'm too old
It goes like this. Let v be a row vector (of length N) and A a matrix (with N rows and say M columns). We may look at the matrix as if it were M separate column vectors w_1, ..., w_M. The product v.A is a vector x of length M, where the ith element of x is the scalar product of v and w_i.Larry wrote:Yes, I understand the Qmatrix method, if you read my first post, but I don't know how it generalizes..
Now suppose we have a recursive formula e.g. F(n) = aF(n1) + bF(n2) + cF(n3). We want to create a matrix A that transforms each vector
u_k = [ F(k) , F(k+1) , F(k+2) ] into the vector [ F(k+1) , F(k+2) , F(k+3) ].
Clearly, the matrix A will be 3x3. Let w_1, w_2, w_3 be its column vectors.
We know that u.A = [ u.w_1 , u.w_2 , u.w_3 ] . From this we can easily see, that we need to take w_1 = [ 0 , 1 , 0 ] and w_2 = [ 0 , 0 , 1 ]. The last element of the vector should be the next element of the sequence. We know that we can compute it using the recursive formula. If we take w_3 = [ c , b , a ], the last element of the result will be u_k.w_3 = F(k).c + F(k+1).b + F(k+2).a = F(k+3).
Therefore in our case the matrix is:
Code: Select all
( 0 0 c )
A = ( 1 0 b )
( 0 1 a )
Can you help me to check my input/output :
Input:
Output:
I dont know why i still get WA.
by the way can anyone explain to me where this recursion relation come from: a[n] = A*a[n1] + B*a[n2] + C*a[n3]. Is there any mathemetical theorem about this.
Thank you
Input:
Code: Select all
10
1
999
9999
10000
100000
123456
1234567
12345678
1000000000
999999999
Code: Select all
Case 1: 1
Case 2: 4314
Case 3: 8650
Case 4: 5035
Case 5: 7963
Case 6: 4
Case 7: 4021
Case 8: 9268
Case 9: 7211
Case 10: 1338
by the way can anyone explain to me where this recursion relation come from: a[n] = A*a[n1] + B*a[n2] + C*a[n3]. Is there any mathemetical theorem about this.
Thank you
tthoai: The problem requires you to output the last 4 digits if it's > 9999. So your 6th output should be 0004 instead of 4.
This problem consumes my leisure time for a week. Finally I got the prove of the recurrence relation. But it's not easy to explain completely here.
Let a[n] be the number of figure with n squares.
Let b[n,k] be the number of figure with n squares and the top row contains k squares.
The idea is to think about the recurrence relation of b[n,k] and the relation between a[n] and b[n,k].
This problem consumes my leisure time for a week. Finally I got the prove of the recurrence relation. But it's not easy to explain completely here.
Let a[n] be the number of figure with n squares.
Let b[n,k] be the number of figure with n squares and the top row contains k squares.
The idea is to think about the recurrence relation of b[n,k] and the relation between a[n] and b[n,k].
It seems that a lot of people know the recurrence relation without knowing why that works. I think it would be more meaningful to know the proof (if you're interested in Mathematics) rather than just coding the formula and got AC. I want to do this long time ago. Just worked it out finally.
My proof to the recurrence relation of this problem: 10743.ps
My proof to the recurrence relation of this problem: 10743.ps