Always dreamed of studying at IIT? 🎓

Now you can, without JEE!

IIT Guwahati presents a unique Credit Linked Program in Computer Science where you can earn 24 program credits (equivalent to a minor degree) with live modules and rigorous assessments by IIT professors. 🖥️📊

Gain in-depth knowledge in Programming, Math for CS, Data Structures, Algorithms, and more.

This is your second chance to experience IIT-quality education! 🎓

Enrol now and join the prestigious IIT ecosystem without the stress of an entrance exam 🌐

Apply now, Limited Seats Available:  https://epcw.short.gy/AC_IITG_TG

Urgent hiring Bulk Fresher and Interns- PAN -2024
Post Name - Multiple Positions and HR
non IT Freshers & Experience.

Interested Apply here:-https://lnkd.in/gerxxYci


Remote and WFH both options are available.
( Preferably Experience)
- Laptop and welcome kit will provided.
-5 Days working
Qualification - Any Degree and 12 th passout .
Salary - 3.5 LPA to 6 LPA

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const vector<pair<int, int>> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
const vector<char> dirChar = {'L', 'R', 'U', 'D'};
int minCostToReachDestination(int N, vector<vector<char>>& Dir, int Sx, int Sy, int Dx, int Dy) {
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    vector<vector<int>> cost(N, vector<int>(N, INT_MAX));
    pq.push({0, {Sx, Sy}});
    cost[Sx][Sy] = 0;
   
    while (!pq.empty()) {
        auto [curCost, pos] = pq.top();
        pq.pop();
       
        int x = pos.first;
        int y = pos.second;
                if (x == Dx && y == Dy) {
            return curCost;
        }
            for (int i = 0; i < 4; ++i) {
            int nx = x + directions[i].first;
            int ny = y + directions[i].second;
           
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                int newCost = curCost + (Dir[x][y] == dirChar[i] ? 0 : 1);
                if (newCost < cost[nx][ny]) {
                    cost[nx][ny] = newCost;
                    pq.push({newCost, {nx, ny}});
                }
            }
        }
    }
   
    return -1;
}

Cost optimization
Google ✅

const int mod = 1e9 + 7;
void insert(vi &dp, int x){
    for(int i = 1000;i >= x; --i)
        dp[i] = (dp[i] + dp[i-x]) % mod;
}
void remove(vi &dp, int x){
    for(int i = x; i <= 1000; ++i)
        dp[i] = (dp[i] - dp[i-x] + mod) % mod;
}
int solve(){
    int n, s;
    cin >> n >> s;
    int a[n];
    inputarr(a, n);
    vector<int> dp(1001,0);
    dp[0] = 1;
    int r = 0;
    int ans = 1e9;
    for(int i = 0; i < n; i++){
        while(r < n && (dp[s] == 0)){
            insert(dp, a[r]);
            r++;
        }
        if(dp[s])
            ans = min(ans, r - i);
        remove(dp, a[i]);
    }
    if(ans == 1e9)
        ans = -1;
    cout << ans << endl;

    return 0;
}

Subset Queries ✅
Google

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1000000007;

long long calculateWays(long long N, long long K, const string& S, const vector<long long>& A);
bool isValidSubstr(const vector<long long>& charCount, const vector<long long>& A);
void updateCharCount(vector<long long>& charCount, char ch, int delta);

long long calculateWays(long long N, long long K, const string& S, const vector<long long>& A) {
    vector<vector<long long>> dp(N + 1, vector<long long>(K + 1, 0));
    dp[0][0] = 1;

    for (long long i = 1; i <= N; ++i) {
        vector<long long> charCount(26, 0);
        for (long long j = i; j >= 1; --j) {
            updateCharCount(charCount, S[j - 1], 1);
            if (isValidSubstr(charCount, A)) {
                for (long long k = 1; k <= K; ++k) {
                    dp[i][k] = (dp[i][k] + dp[j - 1][k - 1]) % MOD;
                }
            } else {
                break;
            }
        }
    }

    return dp[N][K];
}

bool isValidSubstr(const vector<long long>& charCount, const vector<long long>& A) {
    for (long long k = 0; k < 26; ++k) {
        if (charCount[k] > A[k]) {
            return false;
        }
    }
    return true;
}

void updateCharCount(vector<long long>& charCount, char ch, int delta) {
    charCount[ch - 'a'] += delta;
}

int main() {
    long long N, K;
    cin >> N;
    string S;
    cin >> S;
    vector<long long> A(26);
    for (long long i = 0; i < 26; ++i) {
        cin >> A[i];
    }
    cin >> K;

    long long result = calculateWays(N, K, S, A);
    cout << result << endl;
    return 0;
}

Maximum Partition
Google ✅

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e8;
const long long MOD = 1e9 + 7;

long long mod_pow(long long b, long long e, long long m) {
    long long r = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            r = (r * b) % m;
        }
        b = (b * b) % m;
        e /= 2;
    }
    return r;
}

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

    long long max_v = LLONG_MIN;
    long long res = 0;

    for (int i = 1; i < n; ++i) {
        long long pow_v = mod_pow(INF, n - 1, MOD);
        long long val = (arr[i - 1] - arr[i]);
        long long cur_v = (val * pow_v);
        if (cur_v > max_v) {
            max_v = cur_v;
            res = cur_v;
        }
    }

    cout << res % MOD << endl;
    return 0;
}

Awesomeness factor ✅
Google

#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