Task Management
Infosys ✅

max triple sum ✅

#include <bits/stdc++.h>
#define ll long long  
using namespace std;
ll mod(ll x,ll mod)
{
    if(x<mod) return 0;
    return x%mod;
}
bool check(ll l,ll r,ll k,vector<ll>&a)
{
    unordered_map<ll,ll>mpp;
    for(ll i=l;i<=r;i++) mpp[i]++;
    for(auto it:mpp)
    {
       if(it.second!=k) return false;
    }
    return true;
}
ll solve(ll n,ll k,vector<ll>&a,ll q,vector<vector<ll>>&queries)
{
    if(k==1)
    {
        ll sum=0;
        for(ll i=1;i<=q;i++) sum+=i;
        return sum;
    }
    vector<ll>p(q);
    ll t=0,tt=0;
    ll L,R;
    for(ll i=0;i<q;i++)
    {    
        L=mod((t+queries[i][0]),n)+1;
        R=mod((tt+queries[i][1]),n)+1;
        t=L;
        tt=R;
        if(check(L,R,k,a)) p[i]=i+1;
    }
    ll sum=0;
    ll m=1e9+7;
    for(auto  it:p) sum=(sum+it)%m;
    return sum%m;
}
signed main() 
{
    ll n,k; cin>>n>>k;
    vector<ll>a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    ll q; cin>>q;
    ll two; cin>>two;
    vector<vector<ll>>queries(q,vector<ll>(2));
    for(ll i=0;i<q;i++)
    {
        ll x,y; cin>>x>>y;
        queries[i][0]=x;
        queries[i][1]=y;
        //cout<<x<<" "<<y<<endl;
    }
    cout<<solve(n,k,a,q,queries);
    return 0;
}

occurences queries ✅
Infosys

#include <bits/stdc++.h>
#define ll long long  
using namespace std;
ll mod=1e9+7;
ll C(vector<ll>&a,ll n)
{

    ll count=0;
    for(ll i=0;i<n-1;i++) 
    {
        if(((a[i]*a[i+1])-(a[i]+a[i+1]))%2==0) count++;
    }
    return count;
}

void generate(ll n,ll m,ll k,vector<ll>&current,ll&count) 
{
    if (current.size()==n) 
    {
        if (C(current,n)==k) 
        {
            count=(count+1)%mod;
        }
        return;
    }
    for (ll i=1;i<=m;i++) 
    {
        current.push_back(i);
        generate(n,m,k,current,count);
        current.pop_back();
    }
}
ll solve(ll n,ll m,ll k)
{
    vector<ll>current;
    ll count=0;
    generate(n,m,k,current,count);
    return count%mod;
}
signed main() 
{
    ll n,m,k; cin>>n>>m>>k;
    cout<<solve(n,m,k);
    return 0;
}

Perfectly even ✅

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

int main()
{
    ll n, i, j;
    cin >> n;
    ll a[n];
    for(i=0; i<n; i++)
    {
        cin >> a[i];
    }
   
    ll maxi = 0;
    i=0;
    while(i<n-1)
    {
        ll curr=0;
        for(j=i; j<n-1; j++)
        {
            int diff = a[j+1]-a[j];
            if(diff<0)
            {
                break;
            }
            else if((diff & (diff-1)) == 0 || diff==0)
            {
                curr++;
            }
            else
            {
                break;
            }
        }

        i=j+1;
        maxi = max(maxi, curr+1);
    }

    if(n==1) maxi=1;

    cout<<maxi<<'\n';
    return 0;
}

Yet another lis ✅
Infosys

#include <bits/stdc++.h>
using namespace std;

int minimumCost(int N, vector<int> A, vector<vector<int>> Cost) {
    int minCost = INT_MAX;
    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 1);

    do {
        bool valid = true;
        for (int i = 0; i < N; ++i) {
            if (perm[i] > A[i]) {
                valid = false;
                break;
            } else if (perm[i] < A[i]) {
                break;
            }
        }

        if (valid) {
            int cost = 0;
            for (int i = 0; i < N; ++i) {
                cost += Cost[i][perm[i] - 1];
            }
            minCost = min(minCost, cost);
        }
    } while (next_permutation(perm.begin(), perm.end()));

    return minCost;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<vector<int>> Cost(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> Cost[i][j];
        }
    }

    cout << minimumCost(N, A, Cost) << endl;

    return 0;
}

Cheapest permutation ✅

import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt(),i;
    TreeMap<Long,Integer> map=new TreeMap<>();
    long dp[]=new long[n];
    long r[]=new long[n];
    long h[]=new long[n];
    long mod=(long)1e9+7;
    for(i=0;i<n;i++) r[i]=sc.nextLong();
    for(i=0;i<n;i++) h[i]=sc.nextLong();
    for(i=0;i<n;i++){
        long volume=(h[i]*r[i]*r[i])%mod;
        Long low=map.floorKey(volume);
        if(low!=null) dp[i]=(dp[i]+dp[map.get(low)]+volume)%mod;
        else dp[i]=(dp[i]+volume)%mod;
        map.put(volume,i);
    }
    long max=0;
    for(long it:dp) max=Math.max(max,it);
    System.out.println(max);
  }
}

Biggest Tower ✅

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MOD = 1e9 + 7;

struct Intv {
    int s, e;
};

bool cmp(const Intv& a, const Intv& b) {
    return a.s < b.s;
}

int solve(const vector<Intv>& ivs, int L, int R) {
    int cnt = 0;
    int i = 0;
    int maxR = 0;

    while (i < ivs.size() && ivs[i].s <= L) {
        maxR = max(maxR, ivs[i].e);
        i++;
    }

    if (maxR >= R) return 1;

    while (maxR < R) {
        int newR = maxR;
        while (i < ivs.size() && ivs[i].s <= maxR + 1) {
            newR = max(newR, ivs[i].e);
            i++;
        }
        if (newR == maxR) {
            return -1;
        }
        maxR = newR;
        cnt++;
    }

    return cnt + 1;
}

int main() {
    int N, M, two;
    cin >> N >> M >> two;

    vector<Intv> ivs;
    for (int i = 0; i < M; ++i) {
        int x, c;
        cin >> x >> c;
        ivs.push_back({max(1, x - c), min(N, x + c)});
    }

    sort(ivs.begin(), ivs.end(), cmp);

    int Q;
    cin >> Q;

    vector<pair<int, int>> qry(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> qry[i].first >> qry[i].second;
    }

    long long sum = 0;
    int Bk = 0;

    for (int i = 0; i < Q; ++i) {
        int L = 1 + (Bk + qry[i].first) % N;
        int R = 1 + (Bk + qry[i].second) % N;
        if (L > R) swap(L, R);

        int res = solve(ivs, L, R);
        if (res == -1) {
            Bk = MOD - 1;
        } else {
            Bk = res;
        }

        sum = (sum + Bk) % MOD;
    }

    cout << sum << endl;

    return 0;
}


//radio station infosys

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int solve(string s2, int n, int x, int y) {
    vector<char> s(s2.begin(), s2.end());
    
    vector<int> prevSame(s.size(), -1);
    int idxL = -1;
    int idxR = -1;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'l') {
            prevSame[i] = idxL;
            idxL = i;
        } else {
            prevSame[i] = idxR;
            idxR = i;
        }
    }
    vector<vector<long>> dp(s.size() + 1, vector<long>(n + 1, 0));
    dp[0][x] = 1;
    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == 'l') {
                if (j + 1 <= n) dp[i][j] += dp[i - 1][j + 1];
                if (j + 1 <= n && prevSame[i - 1] >= 0) dp[i][j] -= dp[prevSame[i - 1] + 1 - 1][j + 1];
            } else {
                if (j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1];
                if (j - 1 >= 0 && prevSame[i - 1] >= 0) dp[i][j] -= dp[prevSame[i - 1] + 1 - 1][j - 1];
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD;
        }
    }
    return (int) dp[s.size()][y];
}

Paths to a goal ✅

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n <= 0) return false;
        if(n == 1) return true;
        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5
        vector<int> k(n);
        k[0] = 1;
        for(int i  = 1; i < n ; i ++)
        {
            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));
            if(k[i] == k[t2]*2) t2++;
            if(k[i] == k[t3]*3) t3++;
            if(k[i] == k[t5]*5) t5++;
        }
        return k[n-1];
    }
};

Jlr ✅

#include <bits/stdc++.h>
using namespace std;
vector<int> computePrefixFunction(const string &s) {
    int n = s.size();
    vector<int> pi(n);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}
string findSmallestString(const string &s) {
    vector<int> pi = computePrefixFunction(s);
    int n = s.size();
    int len = n - pi[n - 1]; 
    if (n % len == 0)
        return s.substr(0, len);
    else
        return s; 
}
bool isDivisible(const string &s, const string &t) {
    int n = s.size(), m = t.size();
    if (n % m != 0)
        return false;
    for (int i = 0; i < n; i += m) {
        if (s.substr(i, m) != t)
            return false;
    }
    return true;
}
string findGCDString(const string &s, const string &t) {
    if (!isDivisible(s, t))
        return "-1";
    string smallestS = findSmallestString(s);
    string smallestT = findSmallestString(t);
    if (smallestS == smallestT)
        return smallestS;
    else
        return "-1";
}

Jlr ✅

int solve(int n, const vector<int>& from, const vector<int>& to, const vector<int>& weight, int start, int end, int maxStops) {
    vector<vector<pair<int, int>>> adj(n);

    for (size_t i = 0; i < from.size(); ++i) {
        adj[from[i]].emplace_back(to[i], weight[i]);
    }

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    pq.emplace(0, start, 0);

    vector<vector<int>> minCost(n, vector<int>(maxStops + 2, numeric_limits<int>::max()));
    minCost[start][0] = 0;

    while (!pq.empty()) {
        auto [cost, node, stops] = pq.top();
        pq.pop();
       
        if (node == end) {
            return cost;
        }

        if (stops > maxStops) {
            continue;
        }

        for (auto& [nextNode, nextCost] : adj[node]) {
            int newCost = cost + nextCost;
            int newStops = stops + 1;

            if (newCost < minCost[nextNode][newStops]) {
                minCost[nextNode][newStops] = newCost;
                pq.emplace(newCost, nextNode, newStops);
            }
        }
    }


    return -1;
}

vector<int> findCheapestCosts(int n, const vector<int>& from, const vector<int>& to, const vector<int>& weight, const vector<vector<int>>& queries) {
    vector<int> results;
    for (const auto& query : queries) {
        int start = query[0];
        int end = query[1];
        int maxStops = query[2];
        int result = solve(n, from, to, weight, start, end, maxStops);
        results.push_back(result);
    }
    return results;
}


// railway ticket cost calculation Eightfold ai

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int countValidSeries(int n, int m, vector<int>& f) {
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    if (f[0] == 0) {
        for (int j = 1; j <= m; ++j) {
            dp[1][j] = 1;
        }
    } else {
        dp[1][f[0]] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        if (f[i-1] == 0) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j > 1) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
                if (j < m) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
            }
        } else {
            int j = f[i-1];
            dp[i][j] = dp[i-1][j];
            if (j > 1) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
            if (j < m) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
        }
    }
    int result = 0;
    for (int j = 1; j <= m; ++j) {
        result = (result + dp[n][j]) % MOD;
    }
    return result;
}

Flight Series Counter ✅

def countPairs(numbers, k):
    numbers_set = set(numbers)
    pairs = set()
    for number in numbers:
        if (number + k) in numbers_set:
            pairs.add((number, number + k))
        if (number - k) in numbers_set:
            pairs.add((number - k, number))
    return len(pairs)

Counting Pairs ✅

int numConns(const vector<vector<int>>& grid) {
    vector<int> cnt;
    int rows = grid.size();
    int cols = grid[0].size();

    for (int i = 0; i < rows; ++i) {
        int v = 0;
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 1) {
                v++;
            }
        }
        if (v != 0) {
            cnt.push_back(v);
        }
    }

    int conns = 0;
   
    if (cnt.size() >= 2) {
        for (size_t i = 0; i < cnt.size() - 1; ++i) {
            conns += cnt[i] * cnt[i + 1];
        }
    }

    return conns;
}


//Grid climing ✅

#include <bits/stdc++.h>
using namespace std;
long solve(vector<vector<int>>& grid) {
    long long  prev = 0;
    long long  connections = 0;
    for (vector<int>& row : grid) {
        int sum = 0;
        for (int n : row) {
            sum += n;
        }

        if (sum > 0) {
            connections += prev * sum;
            prev = sum;
        }
    }

    return connections;
}

Grid climbing ✅