Codevita Number Mystery

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 :slight_smile:

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.

@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 :slight_smile:

1 Like

Sakshat Bhagwan ne jawab de diya … mitro :joy::joy::joy:

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 :slight_smile:

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 :slight_smile:
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 :slight_smile:

Yup this works as well. :+1:

Nope I answered before God (Karan :stuck_out_tongue: ) .

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