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

int md(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

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

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

    int sx, sy;
    cin >> sx >> sy;

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

    for (int m = 0; m < (1 << n); ++m) {
        for (int i = 0; i < n; ++i) {
            if (!(m & (1 << i))) {
                int nm = m | (1 << i);
                int d = 2 * md(sx, sy, it[i].first, it[i].second);
                dp[nm] = min(dp[nm], dp[m] + d);

                for (int j = i + 1; j < n; ++j) {
                    if (!(m & (1 << j))) {
                        int nmp = nm | (1 << j);
                        int dpair = md(sx, sy, it[i].first, it[i].second) +
                                    md(it[i].first, it[i].second, it[j].first, it[j].second) +
                                    md(it[j].first, it[j].second, sx, sy);
                        dp[nmp] = min(dp[nmp], dp[m] + dpair);
                    }
                }
            }
        }
    }

    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

Collection of items
Google ✅

#include <iostream>
#include <vector>
#include <cstring>

#define MOD 1000000007
#define ALPHABET_SIZE 26

using namespace std;

int solve(int N, int M, vector<pair<char, char>> &Pairs) {
    bool forbidden[ALPHABET_SIZE][ALPHABET_SIZE];
    memset(forbidden, false, sizeof(forbidden));

    for (int i = 0; i < M; ++i) {
        int u = Pairs[i].first - 'a';
        int v = Pairs[i].second - 'a';
        forbidden[u][v] = true;
        forbidden[v][u] = true;
    }

    for (int k = 0; k < ALPHABET_SIZE; ++k) {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            for (int j = 0; j < ALPHABET_SIZE; ++j) {
                if(i == j)
                    continue;
                   
                forbidden[i][j] = forbidden[i][j] || (forbidden[i][k] && forbidden[k][j]);
            }
        }
    }

    vector<vector<int>> dp(N + 1, vector<int>(ALPHABET_SIZE, 0));

    for (int c = 0; c < ALPHABET_SIZE; ++c) {
        dp[1][c] = 1;
    }

    for (int i = 2; i <= N; ++i) {
        for (int c = 0; c < ALPHABET_SIZE; ++c) {
            for (int p = 0; p < ALPHABET_SIZE; ++p) {
                if (!forbidden[p][c]) {
                    dp[i][c] = (dp[i][c] + dp[i - 1][p]) % MOD;
                }
            }
        }
    }

    int result = 0;
    for (int c = 0; c < ALPHABET_SIZE; ++c) {
        result = (result + dp[N][c]) % MOD;
    }

    return result;
}

Reckon String ✅
Google

#include <bits/stdc++.h>
using namespace std;
#define INF LLONG_MAX
typedef long long ll;
vector<ll> dijkstra(int n, const vector<vector<pair<int, ll>>>& adj, int src) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty()) {
        auto [cur_dist, u] = pq.top();
        pq.pop();
       
        if (cur_dist > dist[u]) continue;
       
        for (const auto& [v, weight] : adj[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<ll> Cost(N + 2), Cost2(N + 2);
    for (int i = 1; i <= N + 1; ++i) {
        cin >> Cost[i];
    }
    for (int i = 1; i <= N + 1; ++i) {
        cin >> Cost2[i];
    }
   
    int M;
    cin >> M;
    vector<vector<pair<int, ll>>> adj(N + 2);
    for (int i = 0; i < M; ++i) {
        int U, V;
        cin >> U >> V;
        adj[U].emplace_back(V, Cost2[V]); 
    }
   
    for (int i = 1; i <= N; ++i) {
        adj[N + 1].emplace_back(i, Cost[N + 1]);
    }
   
    vector<ll> dist = dijkstra(N + 1, adj, N + 1);
    ll min_cost = 0;
    for (int i = 1; i <= N; ++i) {
        min_cost += min(dist[i], Cost[i]);
    }
    cout << min_cost << '\n';
    return 0;
}

// MINIMUM COST✅
Google

struct Call {
    int start;
    int end;
    int volume;
};

bool compareCalls(const Call &a, const Call &b) {
    return a.end < b.end;
}

int binarySearch(const vector<Call> &calls, int index) {
    int low = 0, high = index - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (calls[mid].end <= calls[index].start) {
            if (calls[mid + 1].end <= calls[index].start)
                low = mid + 1;
            else
                return mid;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int solve(vector<int> &start, vector<int> &duration, vector<int> &volume) {
    int n = start.size();
    vector<Call> calls(n);
    for (int i = 0; i < n; ++i) {
        calls[i] = {start[i], start[i] + duration[i], volume[i]};
    }

    sort(calls.begin(), calls.end(), compareCalls);

    vector<int> dp(n);
    dp[0] = calls[0].volume;

    for (int i = 1; i < n; ++i) {
        int includeVolume = calls[i].volume;
        int l = binarySearch(calls, i);
        if (l != -1) {
            includeVolume += dp[l];
        }
        dp[i] = max(includeVolume, dp[i - 1]);
    }

    return dp[n - 1];
}



// phone calls ✅
Meesho

vector<int> nxtGreaterIdx(const vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> s;
   
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            s.pop();
        }
        if (!s.empty()) {
            res[i] = s.top();
        }
        s.push(i);
    }
   
    return res;
}

vector<int> prvGreaterIdx(const vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> s;
   
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            s.pop();
        }
        if (!s.empty()) {
            res[i] = s.top();
        }
        s.push(i);
    }
   
    return res;
}

void solve() {
    long long n;
    cin >> n;
    vector<int> a(n);
   
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
   
    vector<int> prv = prvGreaterIdx(a);
    vector<int> nxt = nxtGreaterIdx(a);
    vector<int> pre(n, -1);
    vector<int> suf(n, -1);
   
    for (int i = 0; i < n; ++i) {
        pre[i] = i;
        if (i > 0) {
            int j = pre[i - 1];
            if (a[j] > a[i]) {
                pre[i] = j;
            }
        }
    }
   
    for (int i = n - 1; i >= 0; --i) {
        suf[i] = i;
        if (i < n - 1) {
            int j = suf[i + 1];
            if (a[j] > a[i]) {
                suf[i] = j;
            }
        }
    }
   
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        int x = nxt[i], y = prv[i];
        if (prv[i] == -1) {
            y = pre[i - 1];
        }
        if (nxt[i] == -1) {
            x = suf[i + 1];
        }
        ans = max(ans, x - y);
    }
   
    cout << ans;
}

Three Numbers
Google ✅

vector<long> mazeGame(vector<long> t, vector<int> e1, vector<int> e2, vector<int> w) {
    const long n = t.size();
    vector<vector<pair<long, long>>> connections(n);
    for (long i = 0; i < w.size(); ++i) {
        connections[e1[i] - 1].push_back({e2[i] - 1, w[i]});
        connections[e2[i] - 1].push_back({e1[i] - 1, w[i]});
    }
   
    vector<long long> distances(n, -1);
    vector<bool> visited(n);
    priority_queue<pair<long long, int>> pq;
    pq.push({0, 0});
   
    for (distances[0] = 0; !pq.empty();) {
        const long current_node = pq.top().second;
        pq.pop();
       
        if (visited[current_node]) {
            continue;
        }
        visited[current_node] = true;
       
        for (const auto& neighbor : connections[current_node]) {
            const long neighbor_node = neighbor.first;
            const long long new_distance = distances[current_node] + neighbor.second;
           
            if (new_distance < t[neighbor_node] && (distances[neighbor_node] < 0 || distances[neighbor_node] > new_distance)) {
                distances[neighbor_node] = new_distance;
                pq.push({-new_distance, neighbor_node});
            }
        }
    }
   
    return distances;
}.

MAXE GAME ✅

import heapq

def minCost(g_nodes, g_from, g_to, g_weight):
    adj_list = [[] for _ in range(g_nodes)]
    for i in range(len(g_from)):
        adj_list[g_from[i] - 1].append((g_to[i] - 1, g_weight[i]))

    new_edges = []
    for i in range(g_nodes):
        for j in range(g_nodes):
            if i != j and (i+1, j+1) not in zip(g_from, g_to):
                new_edges.append((i, j, 1))

    for i, j, w in new_edges:
        adj_list[i].append((j, w))

    distances = [float('inf')] * g_nodes
    distances[0] = 0

    pq = [(0, 0)]

    while pq:
        dist, node = heapq.heappop(pq)

        if dist > distances[node]:
            continue

        for neighbor, weight in adj_list[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances[-1]

DP World ✅
Minimum weight path in a directed path

import heapq

def maxClusterQuality(speeds, reliabilities, max_size):
    machines = sorted(zip(reliabilities, speeds), reverse=True)
    max_quality = 0
    current_sum = 0
    min_heap = []
   
    for reliability, speed in machines:
        heapq.heappush(min_heap, speed)
        current_sum += speed
       
        if len(min_heap) > max_size:
            current_sum -= heapq.heappop(min_heap)
       
        if len(min_heap) <= max_size:
            max_quality = max(max_quality, current_sum * reliability)
   
    return max_quality

Computing Cluster Quality ✅
DP World

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

vector<int> solve(int N, int M, vector<int> time) {
    vector<int> ans(M, 0);
    vector<vector<int>> v(N);
   
    for(int i = 0; i < M; ++i) {
        v[i % N].push_back(i);
    }

    int departure = 0;

    for(int i = 0; i < N; ++i) {
        if(!v[i].empty()) {
            ans[v[i][0]] = time[v[i][0]] + 1;
            departure = ans[v[i][0]];
        }
        for(int j = 1; j < v[i].size(); ++j) {
            int idx = v[i][j];
            int val1 = time[idx];
            if(departure > val1) {
                ans[idx] = departure + 1;
                departure++;
            } else {
                departure = val1 + 1;
                ans[idx] = departure;
            }
        }
    }

    return ans;
}

Shopping and Billing ✅

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int countSubstrings(string input_str) {
    string d[9] = {"ab", "cde", "fgh", "ijk", "lmn", "opq", "rst", "uvw", "xyz"};
    vector<int> mp(26, 0);
    for (int i = 0; i < 9; ++i) {
        for (char c : d[i]) {
            mp[c - 'a'] = i + 1;
        }
    }

    int ans = 0;
    int n = input_str.size();
    for (int i = 0; i < n; ++i) {
        int s = 0;
        for (int j = i; j < n; ++j) {
            s += mp[input_str[j] - 'a'];
            if (s % (j - i + 1) == 0) {
                ++ans;
            }
        }
    }

    return ans;
}

Countsubstring ✅

vector<string> areAlmostEquivalent(vector<string>& s, vector<string>& t) {
    vector<string> result;
    auto countCharacters = [](const string& str) {
        vector<int> count(26, 0);
        for (char c : str) {
            count[c - 'a']++;
        }
        return count;
    };
    for (size_t i = 0; i < s.size(); ++i) {
        const string& str_s = s[i];
        const string& str_t = t[i];
  
        vector<int> count_s = countCharacters(str_s);
        vector<int> count_t = countCharacters(str_t);

        bool isAlmostEquivalent = true;
        for (int j = 0; j < 26; ++j) {
            if (abs(count_s[j] - count_t[j]) > 3) {
                isAlmostEquivalent = false;
                break;
            }
        }

        if (isAlmostEquivalent) {
            result.push_back("YES");
        } else {
            result.push_back("NO");
        }
    }
   
    return result;
}

// Almost equivalent String ✅

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

int solve(int N, vector<int> A, vector<int> B) {
    set<int> B_set(B.begin(), B.end());
    int smallest_missing = INT_MAX;
    for (int i = 0; i < N; i++) {
        if (B_set.find(A[i]) == B_set.end()) {
            smallest_missing = min(smallest_missing, A[i]);
        }
    }
    return (smallest_missing == INT_MAX) ? -1 : smallest_missing;
}

Missing Elements ✅

public static int getMaxSubarrayLen(int[] batch_a, int[] batch_b) {
        int n = batch_a.length;
        int[] dpA = new int[n];
        int[] dpB = new int[n];

        dpA[0] = dpB[0] = 1;
        int maxLength = 1;

        for (int i = 1; i < n; i++) {
            dpA[i] = dpB[i] = 1;
            if (batch_a[i] >= batch_a[i - 1]) {
                dpA[i] = Math.max(dpA[i], dpA[i - 1] + 1);
            }
            if (batch_a[i] >= batch_b[i - 1]) {
                dpA[i] = Math.max(dpA[i], dpB[i - 1] + 1);
            }
            if (batch_b[i] >= batch_b[i - 1]) {
                dpB[i] = Math.max(dpB[i], dpB[i - 1] + 1);
            }
            if (batch_b[i] >= batch_a[i - 1]) {
                dpB[i] = Math.max(dpB[i], dpA[i - 1] + 1);
            }

            maxLength = Math.max(maxLength, Math.max(dpA[i], dpB[i]));
        }

        return maxLength;
    }

Save the humanity from Covid -X✅