#define ll long long

int mod = 1e9 + 7;

ll calcpower(ll x, ll n)
{
    if (n == 1)
    {
        return x;
    }
    ll temp = calcpower(x, n / 2);
    if (n & 1)
    {
        return ((((x * temp) % mod) * temp) % mod);
    }
    return (temp * temp) % mod;
}

// Fermat's Little Theorem : a^p=a mod(p)  =>   a^(p-2)=(a^-1)mod(p)
ll modinv(ll num)
{
    return calcpower(num, mod - 2);
}

// Z-Algorithm
vector<int> calculateZ(string &s)
{
    vector<int> z(s.size(), 0);
    int l = 0;
    int r = 0;
    for (int k = 1; k < s.size(); k++)
    {
        if (k > r)
        {
            l = r = k;
            while (r < s.size() && s[r] == s[r - l])
            {
                r++;
            }
            z[k] = r - l;
            r--;
        }
        else
        {
            int k1 = k - l;
            if (z[k1] < r - k + 1)
            {
                z[k] = z[k1];
            }
            else
            {
                l = k;
                while (r < s.size() && s[r] == s[r - l])
                {
                    r++;
                }
                z[k] = r - l;
                r--;
            }
        }
    }
    return z;
}

int numberOfWays(string s, string t, long long k)
{
    if (s.size() != t.size())
    {
        return 0;
    }
    string temp = t;
    temp += '$';
    temp += s;
    temp += s;

    vector<int> z = calculateZ(temp);
    vector<long long> v;
    int n = s.size();
    if (k % 2 == 0)
    {
        v.resize(n, (((calcpower(n - 1, k) - 1) * modinv(n)) % mod));
        v[0] += 1;
        v[0] %= mod;
    }
    else
    {
        v.resize(n, (((calcpower(n - 1, k) + 1) * modinv(n)) % mod));
        v[0] -= 1;
        v[0] += mod;
        v[0] %= mod;
    }

    int ans = 0;
    for (int i = 0; i < z.size(); i++)
    {
        if (z[i] == t.size())
        {
            if (i - t.size() - 1 >= 0 && i - t.size() - 1 < n)
            {
                ans += v[i - t.size() - 1];
            }
            ans %= mod;
        }
    }

    return ans % mod;
}

int getNumWays(string src, string target, int k)
{
    return numberOfWays(src, target, k);
}

NLP atlassian

int countAnalogousArrays(vector<int>& arr, int lower, int higher) { 
    int max = std::numeric_limits<int>::min();  
    int n = lower; 
    for (int i = 0; i < arr.size(); i++) { 
        int k = arr[i]; 
        int k1 = n - k; 
 
        if (k1 > higher || k1 < lower) { 
            return 0; 
        } 
 
        n = k1; 
        max = std::max(max, n); 
    } 
 
    max = higher - max + 1; 
 
    return max; 
}

analogus array atlassian

long getMaximumScore(vector<int> v)
{
    int n=v.size();
    map<int,vector<int>> mp; 
    for(int i=0;i<n;i++)
    {
       mp[v[i]-i].push_back(v[i]);
    }
    long ans=0;
    for(auto v:mp)
    {
        long sum=0;
        for(auto it: v.second)
        {
            sum+=it;
        }
        ans=max(sum,ans);
    }
    return ans;

}

max score atlassian

int n = a.size();
sort(a.begin(),a.end());
int s = 0;
int e = a[n-1]-a[0];
int ans = 0;
while(s<=e){
int mid = s+(e-s)/2;
int mi = a[0];
int count = 1;
bool f = true;
for(int i=1; i<n; i++){
if((a[i]-mi)<=mid){
count++;
}
else{
if(count<m) f = false;
else{
count = 1;
mi = a[i];
}
}
}
if(count<m) f = false;
if(f==false){
s = mid+1;
}
else{
ans = mid;
e = mid-1;
}
}
return ans;

array division Deshaw
9/15

ll solve(vector<int> &arr){
    int n=arr.size();
    vector<ll> pf(n),sf(n);
    pf[0]=arr[0];
    sf[n-1]=arr[n-1];
    for(int i=1;i<n;i++) pf[i]=arr[i]+pf[i-1];
    for(int i=n-2;i>=0;i--) sf[i]=arr[i]+sf[i+1];
    ll sm=0,mn=0;
    ll mx=-1e18;
    for(int i=0;i<n;i++){
        sm+=arr[i];
        if(sm>0) sm=0;
        mn=min(mn,sm);
        mx=max(mx,pf[i]-2*mn-(i<n-1?sf[i+1]:0));
    }
    return mx;
}

subarrays Deshaw

    int l=0,r=1e14;
    while(l<r){
        int mid=(l+r+1)>>1;
        int ans=1;
        int pr=0;
        for(int i=0;i<n;i++){
            if(pr>starts[i]+d){
                ans=0;
            }else{
                pr=max(pr+mid,starts[i]);
            }
        }
        if(ans){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;

Range selection deshaw

2/15

15/15
Deshaw range selection

long getMaxDist(std::vector<long> starts, long d) {
int n = starts.size();
sort(starts.begin(), starts.end()); // Sort the starting points in ascending order
long l = 0, r = 1e14;

while (l < r) {
long mid = (l + r + 1) / 2;
int ans = 1;
long pr = 0;

for (int i = 0; i < n; i++) {
if (pr > starts[i] + d) {
ans = 0;
} else {
pr = std::max(pr + mid, starts[i]);
}
}

if (ans) {
l = mid;
} else {
r = mid - 1;
}
}

return l;
}
c++ Deshaw range queries

Deshaw questions

tomorrow which oa now comment in this thread?

Product Internship at Directi

Link
https://jobs.lever.co/directi/cf481540-aa1b-46b0-bb73-96d0b8100a2d


Try to take referral (good cp profile have high chance in this)