 # Codevita Number Mystery

I got this problem in codevita and I was totally unable to even understand the problem statement. Can anyone here help?

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.
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.

@l_returns God has Answered. Now everybody may chill in heaven.

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 - https://www.codechef.com/problems/PPOW/
Sol - https://www.codechef.com/viewsolution/6320611

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[], 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[], int n)
{
float sum = y;

for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[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;
float x[n];
for(int i=0;i<n;i++)
{
x[i]=(i+1);
y[i]=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 - https://www.codechef.com/problems/PPOW/
Sol - https://www.codechef.com/viewsolution/6320611

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