def max_beauty_sum(A, intervals):
    N = len(A)
    intervals.sort(key=lambda x: x[1])
    dp = [0] * (N + 1)
    last_non_overlapping = [0] * (N + 1)
    
    for start, end in intervals:
        distinct = set(A[start-1:end])
        beauty = sum(distinct)
        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)

Interval maximization ✅

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

const int m = 1e9 + 7;

int main()
{
    int numElements, divisor;
    cin >> numElements >> divisor;
    vector<int> elements(numElements);
    for (int i = 0; i < numElements; i++)
    {
        cin >> elements[i];
    }

    vector<vector<vector<long long>>> dp(divisor, vector<vector<long long>>(divisor, vector<long long>(divisor, 0)));
    dp[0][0][0] = 1;

    for (int value : elements)
    {
        vector<vector<vector<long long>>> newDp(divisor, vector<vector<long long>>(divisor, vector<long long>(divisor, 0)));

        for (int rSum = 0; rSum < divisor; rSum++)
        {
            for (int gSum = 0; gSum < divisor; gSum++)
            {
                for (int bSum = 0; bSum < divisor; bSum++)
                {
                    if (dp[rSum][gSum][bSum] > 0)
                    {
                        newDp[(rSum + value) % divisor][gSum][bSum] = (newDp[(rSum + value) % divisor][gSum][bSum] + dp[rSum][gSum][bSum]) % m;
                        newDp[rSum][(gSum + value) % divisor][bSum] = (newDp[rSum][(gSum + value) % divisor][bSum] + dp[rSum][gSum][bSum]) % m;
                        newDp[rSum][gSum][(bSum + value) % divisor] = (newDp[rSum][gSum][(bSum + value) % divisor] + dp[rSum][gSum][bSum]) % m;
                    }
                }
            }
        }

        dp = newDp;
    }

    long long ass = 0;
    for (int rSum = 0; rSum < divisor; rSum++)
    {
        for (int gSum = 0; gSum < divisor; gSum++)
        {
            int bSum = (divisor - rSum - gSum) % divisor;
            if (bSum < 0)
                bSum += divisor;
            ass = (ass + dp[rSum][gSum][bSum]) % m;
        }
    }

    cout << ass << endl;
    return 0;
}

RGB colouring ✅

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

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

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

    vector<vector<long long>> dp(N, vector<long long>(M, 0));
    vector<vector<long long>> dogDistance(N, vector<long long>(M, LLONG_MAX));

    if (grid[0][0] == 0)
    {
        dogDistance[0][0] = 0;
    }

    dp[0][0] = grid[0][0];

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (i == 0 && j == 0)
                continue;

            if (i > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + grid[i][j] - dogDistance[i - 1][j]);
                dogDistance[i][j] = min(dogDistance[i][j], dogDistance[i - 1][j] + 2);
            }

            if (j > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + grid[i][j] - dogDistance[i][j - 1]);
                dogDistance[i][j] = min(dogDistance[i][j], dogDistance[i][j - 1] + 2);
            }

            if (grid[i][j] == 0)
            {
                dogDistance[i][j] = 0;
            }
        }
    }

    cout << dp[N - 1][M - 1] << endl;

    return 0;
}

Lost in Orange Grove ✅

from collections import defaultdict, deque

def dfs_count(node, parent, adj, A, mod_target):
    count = 0
    stack = [(node, parent)]
    while stack:
        current, parent = stack.pop()
        if A[current] % 3 == mod_target:
            count += 1
        for neighbor in adj[current]:
            if neighbor != parent:
                stack.append((neighbor, current))
    return count

def solve(N, M, A, E, Q, Queries):
    adj = defaultdict(list)
    for u, v in E:
        adj[u-1].append(v-1)
        adj[v-1].append(u-1)
    
    total_result = 0
    for query in Queries:
        if query[0] == 1:
            _, U, X = query
            U -= 1 
            A[U] = X
        elif query[0] == 2:
    
            _, U, X = query
            U -= 1  
            mod_target = X % 3
            count = dfs_count(U, -1, adj, A, mod_target)
            total_result += count
    
    return total_result % (10**9 + 7)

Path queries ✅
Infosys

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

int findMax(vector<int>& a, vector<int>& height, int n, int i, int h, vector<vector<int>>& dp) {
    if (i >= n) return 0;
    if (dp[i][h] != -1) return dp[i][h];
   
    int vol = height[i] * a[i] * a[i];
    int inc = 0;
    int exc = 0;
   
    if (vol > h) {
        inc = vol + findMax(a, height, n, i + 1, vol, dp);
    }
    exc = findMax(a, height, n, i + 1, h, dp);
   
    return dp[i][h] = max(inc, exc);
}

int32_t main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> height(n);
    for (int i = 0; i < n; i++) cin >> height[i];
   
    int maxVol = 0;
    for (int i = 0; i < n; i++) {
        maxVol = max(maxVol, height[i] * a[i] * a[i]);
    }

    // Using the maximum possible value of h to size the dp table
    vector<vector<int>> dp(n, vector<int>(maxVol + 1, -1));

    int ans = findMax(a, height, n, 0, 0, dp);
    cout << ans << endl;

    return 0;
}

Volume of cylinder ✅
Infosys ✅

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

void precomputeMaxMin(vector<vector<int>> &grid, vector<vector<vector<int>>> &maxVal, vector<vector<vector<int>>> &minVal, int N) {
    for (int size = 1; size <= N; size++) {
        for (int i = 0; i <= N - size; i++) {
            for (int j = 0; j <= N - size; j++) {
                if (size == 1) {
                    maxVal[i][j][size] = grid[i][j];
                    minVal[i][j][size] = grid[i][j];
                } else {
                    int prevMax = maxVal[i][j][size - 1];
                    int prevMin = minVal[i][j][size - 1];
                    for (int k = 0; k < size; k++) {
                        prevMax = max({prevMax, grid[i + size - 1][j + k], grid[i + k][j + size - 1]});
                        prevMin = min({prevMin, grid[i + size - 1][j + k], grid[i + k][j + size - 1]});
                    }
                    maxVal[i][j][size] = prevMax;
                    minVal[i][j][size] = prevMin;
                }
            }
        }
    }
}

int getBeauty(vector<vector<vector<int>>> &maxVal, vector<vector<vector<int>>> &minVal, int x, int y, int size) {
    return maxVal[x][y][size] - minVal[x][y][size];
}

int get_ans(vector<vector<int>> &grid, int N) {
    vector<vector<vector<int>>> maxVal(N, vector<vector<int>>(N, vector<int>(N + 1, 0)));
    vector<vector<vector<int>>> minVal(N, vector<vector<int>>(N, vector<int>(N + 1, 0)));

    precomputeMaxMin(grid, maxVal, minVal, N);

    int maxBeautySum = 0;

    for (int size1 = 1; size1 <= N; size1++) {
        for (int x1 = 0; x1 <= N - size1; x1++) {
            for (int y1 = 0; y1 <= N - size1; y1++) {
                int beauty1 = getBeauty(maxVal, minVal, x1, y1, size1);

                for (int size2 = 1; size2 <= N; size2++) {
                    for (int x2 = 0; x2 <= N - size2; x2++) {
                        for (int y2 = 0; y2 <= N - size2; y2++) {
                            if ((x1 + size1 <= x2 x2 + size2 <= x1) && (y1 + size1 <= y2 y2 + size2 <= y1)) {
                                int beauty2 = getBeauty(maxVal, minVal, x2, y2, size2);
                                maxBeautySum = max(maxBeautySum, beauty1 + beauty2);
                            }
                        }
                    }
                }
            }
        }
    }

    return maxBeautySum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

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

    int result = get_ans(grid, N);
    cout << result << endl;

    return 0;
}

Two square minimax
Infosys ✅

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

int maxTripletSum(int arr[], int n) {
    int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN;

    for (int i = 0; i < n; i++) {
        if (arr[i] > maxA) {
            maxC = maxB;
            maxB = maxA;
            maxA = arr[i];
        } else if (arr[i] > maxB) {
            maxC = maxB;
            maxB = arr[i];
        } else if (arr[i] > maxC) {
            maxC = arr[i];
        }
    }

    return (maxA + maxB + maxC);
}

int main() {
    int arr[] = {10, 20, 4, 1, 100, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum triplet sum is " << maxTripletSum(arr, n) << endl;
    return 0;
}

Maximum Triplet Sum ✅
Infosys

#include <iostream>
#include <vector>
#include <numeric>
#define MOD 1000000007
using namespace std;
long long mod_inv(long long x, long long mod) {
    long long result = 1;
    long long power = mod - 2;
    while (power) {
        if (power % 2) {
            result = result * x % mod;
        }
        x = x * x % mod;
        power /= 2;
    }
    return result;
}

vector<long long> factorial(int n, long long mod) {
    vector<long long> fact(n + 1, 1);
    for (int i = 2; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % mod;
    }
    return fact;
}
long long binomial_coeff(int n, int k, const vector<long long>& fact, long long mod) {
    if (k > n || k < 0) {
        return 0;
    }
    return fact[n] * mod_inv(fact[k], mod) % mod * mod_inv(fact[n - k], mod) % mod;
}
long long count_ways(int N, int K, const vector<int>& A) {
    int sum_A = accumulate(A.begin(), A.end(), 0);
    int M = K - sum_A;
    vector<long long> fact = factorial(M + N - 1, MOD);
    return binomial_coeff(M + N - 1, N - 1, fact, MOD);
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    cout << count_ways(N, K, A) << endl;
    return 0;
}

DISTURBUTING BOOKS ✅
Infosys

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