Link to the question - https://www.hackerrank.com/contests/avadacodavra/challenges/notfibo
The sequence is a Linear recurrence relation, you can just brute force it and use recursion. But that would not clear all the test cases and might give TLE. You have to use memoisation (Dynamic Programming) to store precomputed values, to avoid repeated computations. But even that might give a TLE. So to further improve the complexity of the solution, we use Matrix Exponentiation.
Link to a resource on Matrix exponentiation: https://codeforces.com/blog/entry/67776
Solution Code -
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector <vector <long long int>> matrix_product(vector <vector <long long int>> a, vector <vector <long long int>> b)
{
vector <vector <long long int>> res(b.size());
for(int i=0;i<a.size();i++)
{
for(int j=0;j<b[i].size();j++)
{
long long int sum = 0;
for(int k=0;k<a[i].size();k++)
{
sum += a[i][k]*b[k][j];
sum %= MOD;
}
res[i].push_back(sum%MOD);
}
}
return res;
}
vector <vector <long long int>> matrixFE(vector <vector <long long int>> a, long long int n)
{
vector <vector <long long int>> iden = {{1,0,0},{0,1,0},{0,0,1}};
if(n==0)
return iden;
else if(n==1)
return a;
else
{
vector <vector <long long int>> res = matrixFE(a,n/2);
if(n%2==0)
{
return matrix_product(res,res);
}
else
{
return matrix_product(matrix_product(res,a),res);
}
}
}
long long int alterfib(long long int a, long long int n)
{
if(n==0)
return 1;
else
{
vector <vector <long long int>> T = {{a%MOD,0,1},{0,1,0},{0,1,1}};
vector <vector <long long int>> F = {{1},{1},{1}};
vector <vector <long long int>> ans = matrix_product(matrixFE(T,n),F);
return ans[0][0];
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long int a,q;
cin>>a>>q;
while(q--)
{
long long int n;
cin>>n;
cout<<alterfib(a,n)<<endl;
}
}
}
LInk to the question - https://www.hackerrank.com/contests/avadacodavra/challenges/distminlen
Naive appraoch is of O(nXn) , which will not pass the timelimit (2 Sec).
We can improve this time complexity by using binary search.
Observation 1 : for any given 'l', if there is a substring of length 'x' with 'l' distinct characters , then there also exists a substring of length y (y<=x).
Observation 2 : the maximum possible answer for this problem is n , and minimum possible is 0 (if there are not 'l' distinct characters in string).
Observation 3 : if there is a substring with length 'x' with 'l' distinct characters ,
we can find it in linear time.(using sliding window method)
Now to apply binary search , our higher boundary is hb = n and lower boundary is lb = 0.
we get our midpoint as mid = (hb + lb)/2 = (n + 0)/2.
So we check , if there is a substring of length 'mid' which has 'l' distinct letters in linear time.
if there is a substring of length 'mid' with 'l' distinct letters , then we can say that there is also a substring with 'l' distinct letters with length <= mid (Observation 1).So now , we can discard the right part of our searching area [mid + 1 , hb] by reducing higher bound to mid-1 and saving current mid as one of possible answers.
if there is not any substring of length 'mid' with 'l' distinct letters , then we can surely say that there will not be any substring with lenght <= mid which has 'l' distinct characters.So, now we discard our left searching area [lb , md] searching area by increasing lower bound to mid+1.
As we are halving the range [0 , n] at every step , we make roughly log(n) steps.And at each step to check if there is substring with length 'mid' , we use O(n) complexity.
So our time complexity becomes nlogn.
Solution code :
#include<bits/stdc++.h>
using namespace std;
string s;
int x;
bool ok(int m) {
int f[26];
memset(f,0,sizeof(f));
for(int i=0;i<m;++i)
f[s[i]-'a']++;
int cnt=0;
for(int i=0;i<26;++i)
if(f[i]>0)
cnt++;
if(cnt>=x)
return 1;
//sliding window of size m
for(int i=m;i<(int)s.size();++i) {
f[s[i]-'a']++ , f[s[i-m]-'a']--;
int cnt=0;
for(int i=0;i<26;++i)
if(f[i]>0)
cnt++;
if(cnt>=x)
return 1;
}
return 0;
}
void solve(){
cin >> s >> x;
int n = (int)s.size();
int l=0,h=n,ans=0;
while(l<=h) {
int md = (l+h)/2;
if(ok(md))
ans=md,h=md-1;
else
l=md+1;
}
cout << ans << "\n";
}
int main(){
solve();
return 0;
}