10743 - Blocks on Blocks

[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..

[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.

[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?

[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..)

[Per]

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]

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]

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]

Yes, I understand the Q-matrix method, if you read my first post, but I don't know how it generalizes..

[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

[misof]

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]

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]

Thanks misof and Maniac. My math is too poor.

[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

[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].

[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