How many of you guys had given the codenation hiring contest?

How many questions you have got AC?

I gave a try and got 2 AC. First and third. What about you?

Can you please share your approach for third one?

Just LPSâŚ longest palindromic subsequenceâŚ used a bottom up approach to fill the dp[][]âŚ *The most important thing is you need to know your previous elementâŚ store it in a temp variable and do it*

Anyone knows approach for the second problem?

I guess itâs Stirling number and Modulo inverseâŚ recursively we can find modulo inverse âŚ likeâŚ 2^-1(mod 10^9+7) ll be like 10^9+7=2(some number)+the remainder you add to get 10^9+7âŚ I m not sure. Maybe.

I found the answer using contribution technique and it turned out to be summation of (1/i) with i ranging from 1 to N. (Hint : Represent the sequence as a permutation of 1 to N and find contribution of each position as a winning position. )

Can anyone please share the approach of fourth problem ?

What was the time complexity of your approach for third problem ?

N^2 prolly

O(26 *N *N)

From where did you guys get to know about the contest?

They didnât update the website, I mean if you go to the hiring events page it still mentions some competition of Septemberâ19.

I think you must be frequent visitor of hackerrank or should have a friend like thatđ

Please provide solutions with code.

Isnât it NÂ˛?

3rd one

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define krishwish ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define localin freopen(âin.txtâ,ârâ,stdin);

#define localout freopen(âout.txtâ,âwâ,stdout);

const int MAX=2e5+5;

#define ld long double

#define endl â\nâ

#define pb push_back

#define ff first

#define ss second

#define vi vector

#define all(v) v.begin(),v.end()

#define rtcheck cout<<âkrish\nâ;exit(0);

#define vcheck(x) cout<<#x<<" "<<x<<endl;

#define pii pair<int,int>

#define forn for(int i=0;i<n;i++)

const int modu=1e9+7;

const int inf=1e17;

string s;

int dp[1005][1005][27];

int fun(int i,int j,int pre)

{

if(i>j||i==j)

return 0;

if(s[i]==s[j]&&s[i]-âaâ!=pre&&i+1==j)

return 2;

if(dp[i][j][pre]!=-1)

return dp[i][j][pre];

if(s[i]==s[j]&&pre!=s[i]-âaâ)

{

int r= max(fun(i+1,j,pre),fun(i,j-1,pre));

return dp[i][j][pre]=max(2+fun(i+1,j-1,s[i]),r);

}

```
else
{
return dp[i][j][pre]=max(fun(i+1,j,pre),fun(i,j-1,pre));
}
```

}

int32_t main()

{

krishwish;

localin

localout

memset(dp,-1,sizeof(dp));

cin>>s;

int n=s.size();

cout<<fun(0,n-1,26);

}

I just wrote 26 because it is an appreciable factor, and there could be a huge difference in execution time between a code that does (2-3)N*N operations and 26*(N*N) operations.

Can anyone explain the solution to the 4th one?

can you explain it better?