def max_beauty_sum(A, intervals):
    N = len(A)
    dp = [0] * (N + 1)
    last_non_overlapping = [0] * (N + 1)
    
    interval_beauty = []
    for start, end in intervals:
        distinct = set(A[start-1:end])
        beauty = sum(distinct)
        interval_beauty.append((start, end, beauty))
    interval_beauty.sort(key=lambda x: x[1])
    
    for start, end, beauty in interval_beauty:
        prev_end = last_non_overlapping[start-1]
        dp[end] = max(dp[end], dp[prev_end] + beauty)
        
        for i in range(end, N + 1):
            last_non_overlapping[i] = max(last_non_overlapping[i], end)
    
    return max(dp)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    index = 0
    N = int(data[index])
    index += 1
    Q = int(data[index])
    index += 1
    C = int(data[index])
    index += 1
    A = []
    for _ in range(N):
        A.append(int(data[index]))
        index += 1
    
    intervals = []
    for _ in range(Q):
        l = int(data[index])
        index += 1
        r = int(data[index])
        index += 1
        intervals.append((l, r))
    
    result = max_beauty_sum(A, intervals)
    print(result)

if __name__ == "__main__":
    main()

Max Intervals✅
Infosys

Chair Game
Infosys ✅

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int InvasionTime(int N, int M, vector<string>& Q) {
    vector<vector<char>> grid(N, vector<char>(M));
    queue<pair<int, int>> q;
    int enemyCount = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            grid[i][j] = Q[i][j];
            if (grid[i][j] == 'A') {
                q.push({i, j});
            } else if (grid[i][j] == 'E') {
                ++enemyCount;
            }
        }
    }
    if (enemyCount == 0) {
        return 0;
    }

    int time = 0;
    while (!q.empty()) {
        int size = q.size();
        ++time;

        for (int i = 0; i < size; ++i) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            for (const auto& dir : directions) {
                int nx = x + dir.first;
                int ny = y + dir.second;

                if (nx >= 0 && ny >= 0 && nx < N && ny < M && grid[nx][ny] == 'E') {
                    grid[nx][ny] = 'A';
                    q.push({nx, ny});
                    --enemyCount;

                    if (enemyCount == 0) {
                        return time;
                    }
                }
            }
        }
    }

    return -1;
}

int main() {
    int N, M;
    cin >> N >> M;
    cin.ignore(); 

    vector<string> Q(N);
    for (int i = 0; i < N; ++i) {
        getline(cin, Q[i]);
    }

    cout << InvasionTime(N, M, Q) << endl;

    return 0;
}

Army invasion ✅
Infosys

from math import gcd
from collections import defaultdict

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

def find_minimum_subgraph(N, values, edges):

    total_lcm = values[0]
    for i in range(1, N):
        total_lcm = lcm(total_lcm, values[i])
    
    graph = defaultdict(list)
    for u, v in edges:
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)
    
    min_size = N
    subtree_lcm = values.copy()
    
    def dfs(node, parent):
        nonlocal min_size
        size = 1
        current_lcm = values[node]
        
        for child in graph[node]:
            if child != parent:
                child_size, child_lcm = dfs(child, node)
                size += child_size
                current_lcm = lcm(current_lcm, child_lcm)
        
        if current_lcm == total_lcm:
            min_size = min(min_size, size)
            return 0, total_lcm
        
        return size, current_lcm
    
    dfs(0, -1)
    return min_size

tree cutting✅
Infosys

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

vector<int> sieve(int max_number) {
    vector<bool> is_prime(max_number + 1, true);
    vector<int> primes;
    for (int number = 2; number <= max_number; ++number) {
        if (is_prime[number]) {
            primes.push_back(number);
            for (int multiple = number * number; multiple <= max_number; multiple += number) {
                is_prime[multiple] = false;
            }
        }
    }
    return primes;
}

int count_divisors(int number, const vector<int>& primes) {
    int divisor_count = 0;
    int prime_count = primes.size();
    for (int subset = 1; subset < (1 << prime_count); ++subset) {
        long long least_common_multiple = 1;
        int bit_count = 0;
        for (int bit = 0; bit < prime_count; ++bit) {
            if (subset & (1 << bit)) {
                least_common_multiple *= primes[bit];
                bit_count++;
                if (least_common_multiple > number) break;
            }
        }
        if (least_common_multiple > number) continue;
        if (bit_count % 2 == 1) divisor_count += number / least_common_multiple;
        else divisor_count -= number / least_common_multiple;
    }
    return divisor_count;
}

int count_non_divisors(int number, const vector<int>& primes) {
    if (number == 0) return 0;
    return number - count_divisors(number, primes);
}

int count_non_divisors_range(int max_prime, int left, int right) {
    vector<int> primes = sieve(max_prime);
    int right_count = count_non_divisors(right, primes);
    int left_count = count_non_divisors(left - 1, primes);
    return right_count - left_count;
}

int main() {
    int max_prime;
    string left_str, right_str;
    cin >> max_prime >> left_str >> right_str;
    cout << count_non_divisors_range(max_prime, stoi(left_str), stoi(right_str)) << endl;
    return 0;
}

Divisible String ✅
Infosys

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