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

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 https://www.idomaths.com/simeq.php#gauss

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

Sol - https://www.codechef.com/viewsolution/6320611

Que - https://www.codechef.com/problems/POWOFPOW/

sol - 1. https://www.codechef.com/viewsolution/19901187

sol - 2. https://www.codechef.com/viewsolution/19841429

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

Sol - https://www.codechef.com/viewsolution/6320611

Que - https://www.codechef.com/problems/POWOFPOW/

sol - 1. https://www.codechef.com/viewsolution/19901187

sol - 2. https://www.codechef.com/viewsolution/19841429

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