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

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

326 - Extrapolation Using a Difference Table

Post by Red Scorpion » Mon Jun 09, 2003 9:45 am

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:

Post by Dominik Michniewski » Mon Jun 09, 2003 11:17 am

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

Post by Red Scorpion » Wed Jun 11, 2003 3:40 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 :lol:

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

Post by jpfarias » Sun Jun 15, 2003 11:13 pm

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

Post by WR » Wed Apr 14, 2004 2:14 pm

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?

added 19/04
Accepted

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

326 - Extrapolation Using a Difference Table

Post by uDebug » Fri May 30, 2014 2:12 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 3 (300-399)”