Page 1 of 2

10743 - Blocks on Blocks

Posted: Thu Oct 21, 2004 11:44 pm
by Larry
Can someone give some hints? DP won't work (too slow), and I'm thinking of using the Q-matrix method to get the required O( log n ) running time, but I haven't been able to modify it correctly..

Posted: Fri Oct 22, 2004 1:16 am
by Krzysztof Duleba
Notice that you should find only the last 4 digits of a number. That makes it pretty easy - such series are often periodical.

Posted: Fri Oct 22, 2004 2:32 am
by Maniac
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[n-1] - ? a[n-2] + ? a[n-3]
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?

Posted: Fri Oct 22, 2004 4:56 am
by Larry
Thanks for the hint, Krzysztof. I will try that.

Maniac: that sounds right, but keep in mind that a[4] != ? a[3] - ? a[2] + ? a[1], if that situation arise (I don't know if it does, but something to look out for..)

Posted: Fri Oct 22, 2004 4:30 pm
by Per
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
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.

(Larry: I used the matrix method to solve the problem)

Posted: Fri Oct 22, 2004 4:44 pm
by Larry
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.. =)

Posted: Fri Oct 22, 2004 5:03 pm
by misof
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.. =)
Consider for example Fibonacci numbers.
Let v = [ F_n , F_{n+1} ] be a vector, A a matrix defined as follows:

Code: Select all

A = ( 0 1 )
    ( 1 1 )
Then v.A = [ F_{n+1} , F_n + F_{n+1} ] = [ F_{n+1} , F_{n+2} ]

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 :D

Posted: Fri Oct 22, 2004 6:49 pm
by Larry
Yes, I understand the Q-matrix method, if you read my first post, but I don't know how it generalizes..

Posted: Fri Oct 22, 2004 7:06 pm
by Maniac
How do you guys make quotes with author names above?

Larry: if f[n+1] = a f[n] + b f[n-1] + c f[n-2] 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 :-( :-( :-(

Posted: Fri Oct 22, 2004 10:06 pm
by misof
Maniac wrote:How do you guys make quotes with author names above?
Don't click on the "new post" button, click on the "quote" button for the corresponding post instead :D
It's in the upper right corner of each post.

Posted: Fri Oct 22, 2004 10:23 pm
by misof
Larry wrote:Yes, I understand the Q-matrix method, if you read my first post, but I don't know how it generalizes..
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 i-th element of x is the scalar product of v and w_i.

Now suppose we have a recursive formula e.g. F(n) = aF(n-1) + bF(n-2) + cF(n-3). 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 )

Posted: Fri Oct 22, 2004 10:47 pm
by Larry
Thanks misof and Maniac. My math is too poor. :oops:

Posted: Sat Oct 30, 2004 8:53 am
by tthoai
Can you help me to check my input/output :
Input:

Code: Select all

10
1
999
9999
10000
100000
123456
1234567
12345678
1000000000
999999999
Output:

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
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[n-1] + B*a[n-2] + C*a[n-3]. Is there any mathemetical theorem about this.

Thank you

Posted: Sat Oct 30, 2004 9:19 am
by Cho
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].

Posted: Wed Dec 29, 2004 7:22 pm
by Cho
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