Hi, I try using Gauss Jordan Elimination to solve this prob, but got WA.
Am I in the right track ?
Thanks
326  Extrapolation Using a Difference Table
Moderator: Board moderators

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

 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 ...
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 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
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
The DP approach is:
Hope I've helped,
JP!
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 k1 do
4. for j=n2 to 0 do
5. vec[j] = vec[j+1] + vec[j]
6. print vec[0]
JP!