10743 - Blocks on Blocks

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

Moderator: Board moderators

Larry
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 Q-matrix method to get the required O( log n ) running time, but I haven't been able to modify it correctly..

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Notice that you should find only the last 4 digits of a number. That makes it pretty easy - such series are often periodical.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
I haven't solved this problem yet, but I do know that there is a very simple recursive formula for the requested number:
a = ...
...
a = ...
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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Thanks for the hint, Krzysztof. I will try that.

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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.. =)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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 Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Yes, I understand the Q-matrix method, if you read my first post, but I don't know how it generalizes..

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
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   misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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 It's in the upper right corner of each post.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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 )

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Thanks misof and Maniac. My math is too poor. tthoai
New poster
Posts: 2
Joined: Sat Oct 30, 2004 8:38 am
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

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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].

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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