## 326 - Extrapolation Using a Difference Table

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

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 326 - Extrapolation Using a Difference Table

Hi, I try using Gauss Jordan Elimination to solve this prob, but got WA.
Am I in the right track ?

Thanks

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I don't know this method, but I solve it using kind of DP (I think)

Best regards
DM

PS. It's easy problem I think and I got Acc first time ...
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Thanks, for reply Dominik.

I think this problem can't be solve by construct a complete difference table, so I try to find some equation that satisfy this condition.

If the extrapolation difference is n, the eqution become :
y(x) = Ax + B.x^2 + C.x^3 + D.x^4 + ... +K1.x^n + K2
where K1 and K2 some constants.

so for input : 3 6 10 15, I calculate :

y(x)= Ax^3 + Bx^2 + Cx + D
y(1) = A + B + C + D = 3.
y(2) = 8A + 4B + 2C + D = 6
y(3) = 27A + 9B + 3C + D = 10
y(4) = 64A + 16B + 4C + D = 15

So I find A, B, C, D using gauss jordan elimination. But I thinks that's not a good idea.

Dynamic Programing ? Hmmm, I still can't imagine how DP can be applied here.

Thanks Dominik,
RS

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
The DP approach is:

Code: Select all

``````
1. Build the nxn difference table (there will some blanks)
2. Copy the last line in the triangle to a vector(just to make things easier), this line has n elements
3. for i = 0 to k-1 do
4.     for j=n-2 to 0 do
5.         vec[j] = vec[j+1] + vec[j]
6. print vec[0]

``````
Hope I've helped,

JP!

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Hi,

I think I used the same procedure as jpfarias, but got a WA.

Of course there's some uncertainty as to the range of the data.

Is a Pascal integer ok for the sequence and for k?