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:

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

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

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.

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