I got this problem in codevita and I was totally unable to even understand the problem statement. Can anyone here help?
Please see comments for I/O
Is this is from this year codevita???
Yes. It’s from codevita zone 1.
Ya…it’s seems difficult and not understable wait… @anon55659401 , @samarthtandon @l_returns will help …
2 Likes
Question says there exist a polynomial f(x).
IMO it asks for f(0) given f(1), f(2), ..., f(k)
Where f(x) is a L degree polynomial.
Meaning for first test case
L=2 => f(x) = a*x^2 + b*x + c
Now f(0)=c meaning goal is to find c.
Given,
f(1) = 6 = a+b+c
f(2) = 15 = 4a+2b+c
f(3) = 28 = 9a+3b+c
Here we have three variables and three equations. So just solve them and you will get value of a,b,c and answer should be c.
It’s impossible if K<=L or if there doesn’t exist any set of coefficients which satisfies given values.
4 Likes
for the 1st test case L is 2 so its easy to find values but what if L is large , how can i solve for that , please give some hint 
1 Like
There are various methods to solve this in Linear algebra.
Google or refer this I Do Maths · Simultaneous Linear Equation Solver
The degree is limited to 10 so it should work easily.
If you solve it using determinant then solution is simply finding inverse of a 10*10 matrix.
But be careful about precision issues.
Okay so we need to find f(0). This is where my confusion was. Thank you
1 Like
Sakshat Bhagwan ne jawab de diya … mitro 
1 Like
karan short me iski approach bhi bataona
Que - PPOW Problem - CodeChef
Sol - CodeChef: Practical coding for everyone
Que - POWOFPOW Problem - CodeChef
sol - 1. CodeChef: Practical coding for everyone
sol - 2. CodeChef: Practical coding for everyone
matlab ye karna kya chahta hai, thoda explain krdo 
I used interpolation to solve this problem .
here is my code
#include <bits/stdc++.h>
using namespace std;
float proterm(int i, float value, float x[])
{
float pro = 1;
for (int j = 0; j < i; j++) {
pro = pro * (value - x[j]);
}
return pro;
}
void dividedDiffTable(float x[], float y[][10], int n)
{
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
y[j][i] = (y[j][i - 1] - y[j + 1]
[i - 1]) / (x[j] - x[i + j]);
}
}
}
float applyFormula(float value, float x[],
float y[][10], int n)
{
float sum = y[0][0];
for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[0][i]);
}
return sum;
}
int main()
{
int k;
int l;
cin>>k>>l;
int arr[k];
for(int i=0;i<k;i++)
cin>>arr[i];
if(k<(l+1))
{
cout<<"Impossible";
exit(0);
}
int n=6;
if(k<n)
n=k;
float value,y[10][10];
float x[n];
for(int i=0;i<n;i++)
{
x[i]=(i+1);
y[i][0]=arr[i];
}
dividedDiffTable(x, y, n);
value = 0;
cout<< (int)applyFormula(value, x, y, n);
return 0;
}
2 Likes
You can go through the interpolation algorithms in Geeks for Geeks
1 Like
Nice code buddy… keep it up
Help me with this
Que - PPOW Problem - CodeChef
Sol - CodeChef: Practical coding for everyone
Que - POWOFPOW Problem - CodeChef
sol - 1. CodeChef: Practical coding for everyone
sol - 2. CodeChef: Practical coding for everyone
matlab ye karna kya chahta hai, thoda explain krdo
Yup this works as well. 
Nope I answered before God (Karan 
) .
1 Like
Possibly yes. Though question doesn’t clarify this.
Wo kuch khaas nhi kar rha … Sirf strings/arrays use karke 9^4000 calculate kar rha hai … For more doubts , ask God @l_returns
int n=6;
if(k<n)
n=k;
Why this?
1 Like