#include <iostream>
#include <vector>

using namespace std;

int solver(int idx, vector<int>& A) {
    if (idx >= A.size()) return 0;
    int pick = A[idx] + solver(idx + 2, A);
    int notpick = solver(idx + 1, A);
    return max(pick, notpick);
}

int solve(int n, vector<int>& A, int q, vector<vector<int>>& queries) {
    int ans = 0;
    for (auto it : queries) {
        int index = it[0];
        int value = it[1];
        A[index] -= value;
        ans += solver(0, A);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;

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

    int q;
    cin >> q;

    vector<vector<int>> queries(q, vector<int>(2));
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0] >> queries[i][1];
    }

    int result = solve(n, A, q, queries);
    cout << result << endl;

    return 0;
}



yet another subsequence ✅
Infosys

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[10005][2];
const int mod = (1e9 + 7);

ll solve(ll i, ll o, ll n, ll k, vector<ll> &v) {
    if (i > n) {
        return 0;
    }
    if (dp[i][o] != -1)
        return dp[i][o];
    ll ans = 0;
    if (o == 0) {
        for (int j = i; j < min(n + 1, i + k); j++) {
            ans = max(ans, solve(j + 1, 1 - o, n, k, v)) % mod;
        }
    } else {
        ll ta = 0;
        ll mx = 0;
        for (int j = i; j < min(n + 1, i + k); j++) {
            if (ta + v[j] >= 0) {
                ta += v[j];
                mx = max(mx, ta);
            } else {
                ta = 0;
            }
            ll c = solve(j + 1, 1 - o, n, k, v) % mod;
            ans = max(ans, ((j - i + 1) * mx) % mod + c % mod);
        }
    }
    return dp[i][o] = ans;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> v;
    ll neg = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        v.push_back(x);
        if (x <= 0)
            neg++;
    }

    if (neg == v.size()) {
        cout << 0 << endl;
        return 1;
    }
    memset(dp, -1, sizeof(dp));
 
    cout << max(solve(0, 0, v.size() - 1, k, v), solve(0, 1, v.size() - 1, k, v)) << endl;
}

Array Segment
Infosys ✅

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>

using namespace std;

int smartTaxiDriver(int N, int K, vector<int>& T, vector<int>& P, vector<int>& C) {
    unordered_map<int, vector<pair<int, int>>> g;

    for (int i = 0; i < N - 1; ++i) {
        g[P[i] - 1].push_back({i + 2, C[i]});
    }

    int mpc = 0;

    for (int sn = 1; sn <= N; ++sn) {
        vector<int> d(N + 1, -1);
        d[sn] = 0;
        deque<pair<int, int>> q = {{sn, 0}};

        while (!q.empty()) {
            auto [cn, cd] = q.front();
            q.pop_front();

            for (auto& [ne, rd] : g[cn]) {
                if (d[ne] == -1 || d[ne] > cd + rd) {
                    d[ne] = cd + rd;
                    q.push_back({ne, d[ne]});
                }
            }
        }

        int pc = 0;
        for (int des : T) {
            if (d[des] <= K) {
                pc++;
            }
        }

        mpc = max(mpc, pc);
    }

    return mpc - 1;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> T(N - 1), P(N - 1), C(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> T[i];
    }
    for (int i = 0; i < N - 1; ++i) {
        cin >> P[i];
    }
    for (int i = 0; i < N - 1; ++i) {
        cin >> C[i];
    }

    int res = smartTaxiDriver(N, K, T, P, C);
    cout << res << endl;

    return 0;
}

Smart Taxi Driver ✅
Infosys

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

void solve(vector<vector<int>> vv, int operation, int xx, int yy, int &res)
{

    for (int i = 1; i < 3; i++)
    {
        int sum1 = 0;
        for (int j = 0; j < vv.size(); j++)
        {
            sum1 += vv[j][i - 1];
        }
        int sum2 = 0;
        for (int j = 0; j < vv.size(); j++)
        {
            sum2 += vv[j][i];
        }
        if (sum1 == sum2)
        {
            res = min(res, operation);
        }

        return;
    }
    for (int i = 0; i < vv.size(); i++)
    {
        solve(vv, operation, xx, yy, res);
        vector<int> p1 = vv[i];
        reverse(p1.begin(), p1.end());
        solve(vv, operation + yy, xx, yy, res);
        vector<int> p2 = vv[i];
        int temp1 = p2[0];
        int temp2 = p2[1];
        int temp3 = p2[2];
        p2[2] = temp1;
        p2[1] = temp3;
        p2[0] = temp2;
        solve(vv, operation + xx, xx, yy, res);
        vector<int> p3 = vv[i];
        temp1 = p2[0];
        temp2 = p2[1];
        temp3 = p2[2];
        p2[2] = temp2;
        p2[1] = temp1;
        p2[0] = temp3;
        solve(vv, operation + xx, xx, yy, res);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while (t--)
    {
        int n = 0, m = 0, a = 0, b = 0, c = 0, d = 0, sum = 0, diff = 0, maxN = 0, minN = 0, count = 0, temp = 0;
        bool flag = false;
        cin >> n;

        cin >> m;
        int xx;
        cin >> xx;
        int yy;
        cin >> yy;
        vector<vector<int>> vv(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> vv[i][j];
            }
        }
        if (n == 1)
        {
            cout << -1 << endl;
            continue;
        }
        int res = INT_MAX;
        solve(vv, 0, xx, yy, res);
        cout << res << endl;
    }
    return 0;
}

Pay for Gift ✅
Infosys

#include <iostream>
#include <vector>

const int MOD = 1000000007;

using namespace std;

int countBeautifulSequences(int n) {
    if (n == 1) {
        return 1;
    }

    vector<int> dp(n + 1, 0);
    dp[1] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            dp[j] = (dp[j] + dp[j - i]) % MOD;
        }
    }

    return (dp[n] - 1 + MOD) % MOD;
}

int main() {
    int n;
    cin >> n;

    int result = countBeautifulSequences(n);
    cout << result << endl;

    return 0;
}

Count Beautiful sequence

ll help(ll ans,ll k,map<pair<ll,ll>,ll>&m){
    //cout<<ans<<endl;
    if(k==0)
      return ans;
     if(m.find({ans,k})!=m.end())
       return m[{ans,k}];
     ll a=ans;
    for(ll i=30;i>=0;i--){
        for(ll j=30;j>=0;j--){
            ll k1=(ans|(1LL<<i))^(1LL<<j);
            //cout<<k1<<endl;
            a=max(a,help(k1,k-1,m));
        }
    }
    m[{ans,k}]=a;
    return a;
}
void solve(vector<ll>a,ll k){
    ll n=a.size();
    ll ans=a[0];
    for(ll i=1;i<n;i++){
        ans &=a[i];
    }
    map<pair<ll,ll>,ll>m;
    cout<<help(ans,k,m);
}

Limited mask

int min_operations(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
            } else {
                for (int k = i; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
                }
            }
        }
    }

    return dp[0][n - 1];
}

String Dot
Infosys

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 1e9;

struct Node {
    int value, dist;
    Node(int v, int d): value(v), dist(d) {}
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> A(n);
    vector<vector<int>> graph(n, vector<int>());
    vector<vector<int>> dist(n, vector<int>(n, INF));

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

    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        graph[x].push_back(y);
        graph[y].push_back(x);
        dist[x][y] = dist[y][x] = 1;
    }

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    priority_queue<Node, vector<Node>, greater<Node>> pq;

    for (int i = 0; i < n; ++i) {
        if (A[i] > 0) {
            pq.push(Node(i, 0));
        }
    }

    long long cost = 0;

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();

        int u = node.value;
        int d = node.dist;

        if (A[u] > 0) {
            cost += d * A[u];
            A[u] = 0;

            for (int v : graph[u]) {
                if (A[v] > 0) {
                    pq.push(Node(v, d + 1));
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (A[i] > 0) {
            cout << -1 << endl;
            return 0;
        }
    }

    cout << cost << endl;

    return 0;
}

Tree=0✅

Jai Shree Ram ❤

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int val) : val(val), left(NULL), right(NULL) {}
};

Node* expand(Node* root) {
    if(root->left == NULL && root->right == NULL) {
        root->left = new Node(root->val);
        root->right = new Node(root->val);
    } else {
        if(root->left != NULL) root->left = expand(root->left);
        if(root->right != NULL) root->right = expand(root->right);
    }
    return root;
}

void print(Node* root) {
    if(root == NULL) return;
    cout << root->val << " ";
    print(root->left);
    print(root->right);
}

def count_substring_words(s):
    n = len(s)
    unique_words = set()

    for i in range(n - 2):
        substring = s[i:i+3]
        unique_words.add(substring)

    return len(unique_words)

Python 3✅

class UserMainCode(object):

    @classmethod
    def strongString(cls, input1, input2):
        n = len(input2)
        min_strings = []

        for i in range(min(input1, n)):
            distribution = [''] * input1
            for j in range(n):
                distribution[j % input1] += input2[j]

            min_string = min(distribution)
            min_strings.append(min_string)

        result = max(min_strings)
        return result

Game of String Distribution ✅

int maxSubjectsNumber(vector<int> answered, vector<int> needed, int q) {
int n=answered.size();
vector<int>L;
int c=0;
for(int i=0;i<n;i++)
{
    int x=needed[i];
    int y=answered[i];
    if(x>y)
    L.push_back(x-y);
    else
    c++;
}
sort(L.begin(),L.end());
int p=q;
for(int i=0;i<L.size();i++)
{
    int x=L[i];
    if(p<x)
    break;
    p-=x;
    c++;
}
return c;
}

int solve(int N, vector<int> A, int T) {
    int xa = 0;
    for(int i=0; i<N; i++) {
        xa ^= A[i];
    }
    int d = xa ^ T;
    if(d == 0) return 0;
    int ops = 0;
    while(d > 0) {
        ops += d & 1;
        d >>= 1;
    }
    return ops;
}

Flip or flop ✅

Company Name: Leap

Role: Engineering Intern

Batch eligible: 2024 passouts only

Apply: https://leapfinance.freshteam.com/jobs/IDtsNXR4UToB/engineering-internship