Question link

Using unordered map with custom hash mentioned below for storing frquency/kind of prefix sum but gives TLE and using map gets accepted.

For the first time I have seen unordered map with this custom hash is getting TLE because of it.

(Custom hash from blog )

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
           x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve()
{
  
  long long n;cin>>n;
  long long a[n];f(n)cin>>a[i];
  unordered_map<long long,long long,custom_hash>lp;
  lp[0]++;
  long long s=0;long long ans=0;
  f(n){
    s+=a[i];
    if(lp[s]>0){ans++;s=0;lp.clear();lp[0]++;}
    else lp[s]++;
  }cout<<ans<<endl;
}

Can anyone please explain it

Can anyone hep me with this question I can think of LIS but am not able to solve it

Code implement with LIS

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
int main(){
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
ll t;
cin>>t;
while(t--){

    ll n;cin>>n;
    vector<pair<ll,ll>>a(n);
   f(n)cin>>a[i].first;
   f(n){cin>>a[i].second;}
   sort(a.begin(),a.end(),[&](pair<ll,ll>a,pair<ll,ll>b){
    if(a.first==b.first)return a.second>b.second;
    return a.first<b.first;
   });
   vector<ll>b;
   vector<pair<ll,ll>>lp;
   ll ans=1;
   lp.push_back({-1,-1});
   b.push_back(-1);
   for(ll i=0;i<n;i++){
if(lp[lp.size()-1].first==a[i].first)continue;
 auto it= lower_bound(b.begin(), b.end(), a[i].second);
        if (it == b.end()) {
            b.push_back(a[i].second);
            lp.push_back(a[i]);
        }
        else {
          lp[it-b.begin()]=a[i];
            b[it-b.begin()] = a[i].second;
        }
}    
       cout<<lp.size()-1<<endl;
}
}

Question from algozenith mocks Microsoft coding test 2 — question 1 This question is asked un Microsoft online assessment which is present in various sites but none of them have provided correct solutions. One can think of bfs but it will give TLE as many steps are repeated a lot of time. So talking about dp optimization. 2D dp where dp[i][j] will give total number of ships when start with value j and total layers are i including current layer. Base case would be for every i dp[i][0]=i and for every j dp[1][j]=1. dp[i][j]= (summation dp[i-1][j] for every j from 0 to (j*j+1)%m-1 ) But its constantly giving wrong answer. And to make it worse nowhere correct answer is given nor failed test case is shown. i think i have something wrong in my idea can anyone clarify. below is my code.

ll l,m;cin>>l>>m;
    vector<vector<ll>>dp(l+2,vector<ll>(m+2,0));
    f(m){dp[1][i]=1;}

    vector<ll>lp(m+1);lp[0]=1;
    for(ll i=1;i<l;i++){lp[i]=lp[i-1]+1;}
for(ll i=0;i<l;i++){dp[i][0]=i;}
    for(ll j=2;j<=l;j++){

for(ll i=0;i<m;i++){
    if(i==0)continue;
    if((i*i+1)%m!=0)dp[j][i]=lp[((i*i+1)%m)-1];
    dp[j][i]++;

}
for(ll i=0;i<lp.size();i++){if(i==0)lp[i]=dp[j][i];else lp[i]=lp[i-1]+dp[j][i];}

    }
    cout<<dp[l][2]%m<<endl;

question link Question link