#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

int64_t findMax(vector<vector<int>>& items, int k) {
    int n = items.size() - 1;
    vector<vector<int64_t>> dp(n + 1, vector<int64_t>(k + 1, 0));
    vector<int> ult(n + 5, -1);

    // Sort the items based on their type (tp) in ascending order
    sort(items.begin() + 1, items.end());

    for (int i = 1; i <= n; i++) {
        int tp = items[i][0];
        int wt = items[i][1];
        int val = items[i][2];
        int lsttp = ult[tp];
        if (-1 == lsttp) lsttp = i - 1;
        for (int ow = 0; ow <= k; ow++) {
            dp[i][ow] = max(dp[i][ow], dp[i - 1][ow]);
            if (wt + ow <= k) {
                dp[i][wt + ow] = max({ dp[i][wt + ow], dp[lsttp][ow] + val, dp[i - 1][wt + ow] });
            }
        }
       
        if (-1 == ult[tp]) ult[tp] = i - 1;
    }

    int64_t res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            res = max(res, dp[i][j]);
        }
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> items(n + 1, vector<int>(3));
    for (int i = 1; i <= n; i++) {
        cin >> items[i][0] >> items[i][1] >> items[i][2];
    }

    int k;
    cin >> k;

    int64_t result = findMax(items, k);
    cout << result << endl;

    return 0;
}

Modified knapsack ✅

#include <vector>
#include <queue>
using namespace std;

int solve(vector<int> ropes) {
    priority_queue<int> pq(ropes.begin(), ropes.end());
    int ans = 0;
    while (pq.size() > 1) {
        int rope1 = pq.top();
        pq.pop();
        int rope2 = pq.top();
        pq.pop();
        if (rope1 < 2 || rope2 < 2) {
            break;
        }
        ans += (rope1 - 1) * (rope2 - 1);
    }
    return ans;
}

Ropes Pair Length ✅

int solution(const string &s) {
    const int n = s.length();
    int r = 0;
    for (int i = n - 1, j = 0; i >= 0 && j < n; ++j) {
        if (s[i] == s[j]) {
            --i;
            ++r;
        }
    }
    return n - r;
}

Amazon ✅

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll count(ll k,vector<ll>& a)
{
    unordered_map<ll,ll>mpp,count;
    ll n=a.size();
    for (ll i=2;i*i<=(k);i++)
    {
        if (k%i==0)
          while(k%i==0) mpp[i]++,k/=i;
    }         
    if (k>1) mpp[k]++;
    for (auto num:a)
    {
        for(auto it:mpp)
        {
            ll fac=it.first;
            while (num%fac==0)
            {
                count[fac]++;
                num/=fac;
            }
        }
    }
    ll mini=LONG_MAX;
    for(auto&it:count)
      {
        it.second/=mpp[it.first];
        mini=min(mini,it.second);
      }
      return (mini==LONG_MAX)?0:min(n,mini);
}
signed main() {
    ll n, k; cin>>n>>k;
    vector<ll>a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    cout<<min(n,count(k,a));
    return 0;
}

K Divisible number ✅

#include<bits/stdc++.h>
using namespace std;
int N,M;
int findMinimum (vector<vector<vector<int>>>&arr,int rr,int cc) {
   // Write your code here
   vector<vector<bool>>seen(arr.size(),vector<bool>(arr[0].size(),false));
   seen[0][0]=true;
   queue<pair<int,int>>q;
   int le=0;
   q.push({0,0});
   while(!q.empty())
   {
    int si=q.size();
    while(si-->0)
    {
        pair<int,int>cu=q.front();
        q.pop();
        int r=cu.first;
        int c=cu.second;
        if(r==rr and c==cc)
        return le;
        int x=arr[r][c][0];
        int y=arr[r][c][1];
        int rc=arr.size();
        int cd=arr[0].size();
        int dir[8][2]={{x,y},{x,-y},{-x,y},{-x,-y},{y,x},{y,-x},{-y,x},{-y,-x}};
        for(int i=0;i<8;i++)
        {
            int nr=r+dir[i][0];
            int nc=c+dir[i][1];
            if(nr>=0 and nr<rc and nc>=0 and nc<cd and !seen[nr][nc])
            {
                q.push({nr,nc});
                seen[nr][nc]=true;
            }
        }
    }
    le++;
   }
   return -1;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i=0; t_i<T; t_i++)
    {
        //int N;
        cin >> N;
        //int M;
        cin >> M;
        vector<vector<vector<int>>>arr(N,vector<vector<int>>(M,vector<int>(2)));
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin>>arr[i][j][0]>>arr[i][j][1];
            }
        }
        int out_;
        out_ = findMinimum(arr,N-1,M-1);
        cout << out_;
        cout << "\n";
    }
}

Minimum moves ✅
Hackerearth

Quizizz is hiring Backend Engineer

For 2023, 2022 grads

https://www.instahyre.com/job-314304-software-engineer-backend-at-quizizz-bangalore/

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll count(ll k,vector<ll>& a) 
{
    unordered_map<ll,ll>mpp,count;
    ll n=a.size();
    for (ll i=2;i*i<=(k);i++) 
    {
        if (k%i==0)
          while(k%i==0) mpp[i]++,k/=i;
    }          
    if (k>1) mpp[k]++;
    for (auto num:a) 
    {
        for(auto it:mpp)
        {
            ll fac=it.first;
            while (num%fac==0) 
            {
                count[fac]++;
                num/=fac;
            }
        }
    }
    ll mini=LONG_MAX;
    for(auto&it:count) 
      {
        it.second/=mpp[it.first];
        mini=min(mini,it.second);
      } 
      return (mini==LONG_MAX)?0:min(n,mini);
}
signed main() {
    ll n, k; cin>>n>>k;
    vector<ll>a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    cout<<min(n,count(k,a));
    return 0;
}

K divisible number ✅

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

const int MOD = 1000000007;

long long countMaxXOR(int N, int K) {
    vector<vector<long long>> dp(N + 1, vector<long long>((1 << K), 0));
    dp[1][0] = 1;

    for (int i = 2; i <= N; i++) {
        for (int j = 0; j < (1 << K); j++) {
            for (int k = 0; k < (1 << K); k++) {
                if ((j ^ k) > j) {
                    dp[i][j ^ k] = (dp[i][j ^ k] + dp[i - 1][j]) % MOD;
                }
            }
        }
    }

    long long total_count = 0;
    for (int j = 0; j < (1 << K); j++) {
        total_count = (total_count + dp[N][j]) % MOD;
    }

    return total_count;
}

Array Construction ✅

Greetings from Tata Strive- Nagavara Centre- Bengaluru

🌟 Empowering Students for Brighter Futures 🌟

🚀 Join our targeted upskilling initiatives! 🚀

Are you ready to take your future to new heights? We're offering exclusive courses in AWS Restart, Cyber Security & GIS and Drone Data Processing, Food and Beverages Steward, Housekeeping attendant to uplift underprivileged students like you. Here's your chance to unlock a world of opportunities!

🎓 Course Details:

1.  AWS Restart
📜 Eligibility Criteria:
• Education- BE/Btech(CS,IT,IS)/MCA
• Year of passing -2021,22,23
• Score- min 60% score in 10th, 12th and graduation

2.  Cyber Security
📜 Eligibility Criteria:
• Education- BE/Btech(CS,IT,IS)/MCA
• Year of passing -2021,22,23
• Score- min 60% score in 10th, 12th and graduation

3.  Geographic Information Systems (GIS) and Drone Data Processing
📜 Eligibility Criteria:
• Education- 10th Pass. Diploma and ITI Pass are highly preferred.
• Proficiency in reading and writing English/Hindi

4. Food & Beverages Steward
📜 Eligibility Criteria:
• Education- 10th Pass & Above
• Interested in Food Industry

5. Housekeeping Attendant
📜 Eligibility Criteria:
• Education- 8th & Above
• Interested in Hospitality

🌈 Why Choose Us?:

Hands-on training from industry experts
Learn cutting-edge skills in high-demand fields
Assistance for placements and internships
Empower yourself for a brighter tomorrow!
📅 Enrollment Period: Limited seats available! Act fast to secure your spot.

📝 How to Apply:
 Register now for Cyber Security, AWS & GIS Drone Courses: https://docs.google.com/forms/d/e/1FAIpQLScJNaCZVbTWr3FT6MpPjT9XjLu637pCXDMbcrY04cQzS1gRUQ/viewform?usp=sf_link

 Register now for F&B and Housekeeping attendant Courses
        https://forms.gle/Z58jZLqQ2Uzw29j76
Don't let this opportunity pass you by. Take the first step towards a brighter future today! 💫

📲 Contact Us:
Mahesha KC:  9449941568
Let's journey towards success together!

Amazon hiring SDE-1 | 2022, 2023 Grads | Full Time

https://www.amazon.jobs/jobs/2634686/software-development-engineeri

Geek Count✅

const int MOD = 1000000007; 

int countGeekSubsequences(const string& s) { 
    int n = s.length(); 
    vector<vector<int>> dp(5, vector<int>(n + 1, 0)); 
    for (int i = 0; i < 5; ++i) 
        dp[i][0] = 0; 
    for (int i = 0; i <= n; ++i) 
        dp[0][i] = 1; 

    for (int i = 1; i <= 4; ++i) { 
        for (int j = 1; j <= n; ++j) { 
            dp[i][j] = dp[i][j - 1]; 
            if (s[j - 1] == "geek"[i - 1]) 
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD; 
        } 
    } 
     
    return dp[4][n]; 
}

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

using namespace std;

int getMinTransactions(int n, vector<vector<int>>& debt) {
    unordered_map<int, int> balance
    for (const auto& d : debt) {
        balance[d[0]] -= d[2];
        balance[d[1]] += d[2];
    }
   
    vector<int> transactions;
    for (const auto& entry : balance) {
        if (entry.second != 0) {
            transactions.push_back(entry.second);
        }
    }

    int count = 0;
    int i = 0, j = transactions.size() - 1;
    while (i < j) {
        if (transactions[i] + transactions[j] == 0) {
            count++;
            i++;
            j--;
        } else if (transactions[i] + transactions[j] > 0) {
            transactions[i] += transactions[j];
            j--;
            count++;
        } else {
            transactions[j] += transactions[i];
            i++;
            count++;
        }
    }
    return count;
}

Transaction Simplification ✅

Urban Company is Hiring Business Development Interns

Eligibility:  Tech & Non-Tech both
Graduation Year: 2024, 2025, 2026
Expected Stipend: 20k - 25k per month
Location: Mumbai

Apply Link:
https://www.foundit.in/zuno/job/business-development-associate-intern-6?utm_source=campus-ambassador&utm_medium=urbancompany&utm_campaign=ZW4204

📌Monk Commerce is hiring for Frontend Engineer SDE I - Remote (0-2 years)
Apply here:
https://linkedin.com/jobs/view/3917231666/

Avalara Hiring Fresher For Associate Analyst                        
Location: Pune                    
Qualification: MBA                       
Work Experience: Fresher - 2 Years                 
Salary: 6 LPA 
                               
Apply Link: https://careers.avalara.com/jobs/12839?lang=en-us&iis=Job+Board&iisn=LinkedIn