Entering edit mode

Airlift

You and your family are trapped on a flood-prone island.When you called the emergency services to ask for assistance . They promised to send aircraft to airlift your family. As long as the combined weight of the two passengers is less than or equal to K

,each aircraft is only permitted to to carry a maxmum of K and a maximum of K and a maximum of two other passengers in addition to the pilot . You are given the following

The maximum capacity of the aircraft
The total number of family members
An array weights where weights[i], reprsent the weight of the i^thfamily member

Task

Return the minimum number of aircraft required to airlift the family

If not possible, return -1.

Example

Assumptions:
K = 5

N= 9

weights = [3,3,5,2,1,4,5,1,5]

Constraints

1 <= K <= 5*10⁹
1 <= N <= 10⁵
1 <= weights[i] <= 10⁹
weights contain only positive integers

Sample Input              Sample Output

6                                3
4
3 5 4 3

Shopping and billing

In a shop wth N counters. M peccie arrive for billing at different times denoted as smell. Each person selects the counter with the shortest queue, based on the number of people already present. if a counter is empty the pets immediate biting, otherefse, they join the queue
For every person, output the tit
rig and leave the counter.
Notes

It takes 1 unit of time for the counter to process a person's bills
The counter processess the next person mmediately after the current person leaves .
The time is given in increasing order of arrival at the counters . In formal terms time[i] <= time[i+1]

Function Description

Complete the function solve . This function takes the following 3 parameters returns teh required answer

N- Represents the numer of counters
M: Represents the number of persons
tiime: Represents an array containing the entry time of the people

Input format for custom testing

Note: Use this input format if you are testing against custom Input or writing code in a language
where we don't provide bollerplate code.

The first line contains N denoting the number of counters.
The second line contains M denoting the number of persons.
The third line contains an array time, indicating the entry time of the people.

Output format

Print a single line of M space-separated integers, denoting the exit times of the people.

Constraints

1<= N <= 10⁵
1 <= M <= 10⁵
0 <= position[i] <= 10⁹

Sample Input           Sample Output
2                        1 1 2  2

4

0 0 0 0

Explanation

N=2
M=4
position = |0, 0. 0. 0]

Output

1 1 2 2

The first person arrives at O, finds both counters empty, goes to counter 1, and leaves at
The second person arrives at 0, finds counter 2 empty, and leaves at 1
The third person arrives at 0, finds both counters with 1 person, goes to counter 2, and leaves at 2
The fourth person arrives at 0, finds counter 1 with 1 person and counter 2 with 2 persons, goes to counter 1 and leaves at 2

Sample Input                                           Sample Output
10                                             88234 93641 99414 99901 99990 99994 99997 99997 99 
31
88233 93640 99410 99900 99989 99993 99996

Special Package

You are the manager of a grocery store and you want to create special package deal for your customers . you are given a matrix of prices of size N * M . for different products ,with each row representing different category of products and esch column representing a different product in the category

You want to select one item from each category such that the total cost of the package is as close as possible to a specific target price K

You need to determine the minimum absolute difference between targer price and actual cost of the package you can create products in the matrix

Fuction Description

Complete the function solution() provided in the editor .The function takes the following 4 parameters and return the solution

N: Represents the number of categories
M:Represents the number of items in each category
K: Repreents the target price
price: represents the price of items

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language
where we don't provide boilerplate code
The first line contains N denoting the number of categories.
The second line contains M denoting the number of items in each category.
* The third line contains K denoting the target price.
• Each of the next N lines contains M integers each, denoting the price of the items.

Output format

Print an integer, representing the minimum absolute difference between the target price and the total cost of the package.

Constraints

1 <= N,M <= 70
1 <= price[i][j] <= 70
1 <= K <= 800

ADD COMMENT • link

Entering edit mode

8

 public static void main(String args[]) throws IOException {
        int k=in.nextInt();
        int n=in.nextInt();
        int arr[]=in.readintarray(n);
        Arrays.sort(arr);
        if(arr[n-1]>k)print(-1);
        else{
        int i=0;
        int j=n-1;int c=0;
        while(i<=j){
            if(arr[i]+arr[j]<=k){
                i++;
                j--;
                c++;
            }
            else if(arr[i]+arr[j]>k){
                j--;
                c++;
            }
            else{
                i++;
                c++;
            }
        }
       print(c);
        }
    }

Question 1 solution

ADD REPLY • link 17 months ago

ROHIT KONER • 120

3

Entering edit mode

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

int main() {
    int k;
    int n;
    cin>>k>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
    cin>>v[i];
    int z=min(k-1,n-1);
    priority_queue<int,vector<int>,greater<int>> pq;
    for(int i=0;i<=z;i++)
   {
        pq.push(v[i]);
   }
    z++;
    vector<int> ans;
    while(!pq.empty())
    {
       int x=pq.top();
       ans.push_back(x+1);
       pq.pop();
       if(z<n and v[z]<=x+1) 
       {
           int p=max(x+1,v[z]);
           pq.push(p);
           z++;
       }
       if(z<n and pq.size()<k)
       {
           pq.push(v[z]);
           z++;
       }
    }
    for(int i=z;i<n;i++)
    ans.push_back(v[i]+1);
    for(int x:ans)
    cout<<x<<" ";
}

Question 2 Solution probably this

ADD COMMENT • link 17 months ago Arko • 60

3

Entering edit mode

similar to 3rd question

https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/

ADD COMMENT • link 17 months ago Div • 30

2

Entering edit mode

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

int main() {
int k;
int n;
cin>>k>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
int z=min(k-1,n-1);
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<=z;i++)
{
pq.push(v[i]);
}
z++;
vector<int> ans;
while(!pq.empty())
{
int x=pq.top();
ans.push_back(x+1);
pq.pop();
if(z<n and v[z]<=x+1)
{
int p=max(x+1,v[z]);
pq.push(p);
z++;
}
if(z<n and pq.size()<k)
{
pq.push(v[z]);
z++;
}
}
for(int i=z;i<n;i++)
ans.push_back(v[i]+1);
for(int x:ans)
cout<<x<<" ";
}

Question 2 Solution probably this

ADD COMMENT • link 17 months ago Arko • 60

2

Entering edit mode

3rd question

Hack--> since 1<=n,m,items<=70 so map will store at max 4900 entries.

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

void solve()
{
ll n,m,k;
cin>>n>>m>>k;

vector<vector<ll>> items(n,vector<ll>(m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>items[i][j];
}
}

unordered_map<ll,ll> mp;
for(int i=0;i<m;i++)
{
mp[items[0][i]]++;
}

for(int i=1;i<n;i++)
{
unordered_map<ll,ll> mpp;
for(int j=0;j<m;j++)
{
for(auto item:mp)
{
mpp[item.first+items[i][j]]++;
}
}

mp=mpp;
}

ll ans=INT_MAX;
for(auto i:mp)
{
ans=min(ans,abs(k-i.first));
}

cout<<ans<<"\n";
}

int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}

ADD COMMENT • link 17 months ago Aayush Agrawal • 180

2

Entering edit mode

Solution to Question no 2 . The approach is we use a set to find the empty counter and cnt is used to see which counter is occupied. We push {time+1, counterid} into pq. Note we use min heap here since we need to find the shortest queue. We remove all the person <= arrivalTime[i]. If there is no free counter when a person comes then he is bound to wait and we pop the first vale and allocate that counter to him since it is guaranteed to have shortest waiting time for that person. Lastly we add pq.top().time+1 as the exit time. Else if counter is free then we will assign counter to him and add arrivalTime[i]+1 as the answer.

using ll = long long int ;
int main() {
ll n,m;
cin>>n>>m;
vector <ll> pos(m);
for (int i=0;i<m;i++ ) {cin>>pos[i];}

priority_queue < pair <int,int> , vector <pair <int,int>>, greater <pair <int,int> >> pq;
set <ll> free;
vector <int> ans;
vector <ll> cnt(n+2,0);

for (ll i=1;i<=n;i++) {free.insert(i);}


for (ll i=0;i<m;i++ ) {
ll Time=pos[i];
while (pq.size () && pq.top().first <= Time) {
pair <int,int> top=pq.top();
pq.pop();
int id=top.second;
if (cnt[id] == 1) {
free.insert(id);

}
cnt[id]--;
}
if (free.size() == 0) {
pair <int,int> top=pq.top();
pq.pop();
int id=top.second;
if (cnt[id] == 1) {
free.insert(id);

}

cnt[id]--;
int begin= *free.begin();
cnt[begin]+=1;
free.erase(begin);
pq.push({top.first+1,begin});
ans.push_back(top.first+1);



}
else {
int begin= *free.begin();
cnt[begin]+=1;
pq.push({ Time+1 ,begin});
free.erase(begin);
ans.push_back(Time+1);

}
}
for (auto &i:ans) {
cout<<i<<" ";
}
return 0;
}

ADD COMMENT • link 17 months ago Sahil Kumar • 260

0

Entering edit mode

Probably Solution to 2nd one

ADD COMMENT • link 17 months ago Arko • 60

0

Entering edit mode

please send solution of third question also

ADD COMMENT • link 17 months ago Sumit Soni • 0

Entering edit mode

1

static int u1=(int)1e9;

    public static void main(String args[]) throws IOException {
       int n=in.nextInt();
       int m=in.nextInt();
       int k=in.nextInt();
       int arr[][]=new int[n][m];
       for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){
               arr[i][j]=in.nextInt();
           }
       }
       f(0,0,n,m,arr,k,0);
       print(u1);
    }
    public static void f(int i,int j,int m,int n,int grid[][],int k,int sum){
        
        if(i==m){
            System.out.print(sum+" ");
            u1=Math.min(u1,Math.abs(sum-k));
            return;
        }
        
        for(int u=j;u<n;u++){
           
             sum+=grid[i][u];
            f(i+1,0,m,n,grid,k,sum);
             sum-=grid[i][u];
        }
       
    }

this can be the solution of q3 but it can give tle

ADD REPLY • link 17 months ago

ROHIT KONER • 120

0

Entering edit mode

Here is my solution to 3rd problem:

https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/submissions/927777874/https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/submissions/927777874/

ADD COMMENT • link 17 months ago PRANAY KUMAR • 0

0

Entering edit mode

2nd question solution let me know if there are any wrongs

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>arr(m);
    for(int i=0;i<m;i++){
        cin>>arr[i];
    }
    int blocklen=n;
    priority_queue<int,vector<int>,greater<int>>pq;
    for(int i=0;i<m;i++){
        pq.push(arr[i]);
    }
    int ind=0;
    vector<int>ans(m);
    int k=1;
    while(!pq.empty()&&blocklen>0){
        int a=pq.top();
        pq.pop();
        ans[ind]=a+k;
        ind++;
        blocklen--;
        if(blocklen==0){
            blocklen=n;
            k++;
        }
    }
    for(auto i : ans){
        cout<<i<<" ";
    }

    return 0;
}

ADD COMMENT • link 17 months ago harsha.yella2002 • 0

Entering edit mode

0

wrong

ADD REPLY • link 15 months ago

Praneeksha Jayam • 0

0

Entering edit mode

#include <bits/stdc++.h>
using namespace std;
int solve(int i,int t,vector<vector<int>>&mat,int sum,vector<vector<int>>&dp){
    int n=mat.size();
    int m=mat[0].size();
    if(i==n){
        return abs(t-sum);
    }
    if(dp[i][sum]!=-1)return dp[i][sum];
    int ans=INT_MAX;
    for(int ind=0;ind<m;ind++){
        ans=min(ans,solve(i+1,t,mat,sum+mat[i][ind],dp));
    }
    return dp[i][sum]=ans;
}

int main()
{
    int n;
    cin>>n;
    int m;
    cin>>m;
    int k;
    cin>>k;
    vector<vector<int>>arr(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    vector<vector<int>>dp(n+1,vector<int>(5000,-1));//5000 because that can be maximum sum possible i.e 4900
    int sum=0;
    cout<<solve(0,k,arr,sum,dp)<<endl;
    return 0;
}

3 rd question memoisation solution

ADD COMMENT • link 17 months ago harsha.yella2002 • 0

0

Entering edit mode

void solve() { ll n ,k ; cin >> n>> k ; vll v(n); fl(i ,0 ,n ) cin >> v[i] ; sort(vbe) ; if(v[n-1]>k) { cout << -1 <

ADD COMMENT • link 16 months ago Kshitiz Kumar • 0

0

Entering edit mode

void solve()
{
ll n ,k ; cin >> n>> k ; 
vll v(n); fl(i ,0 ,n ) cin >> v[i] ;

sort(vbe) ; 

if(v[n-1]>k)
{
    cout << -1 <<nl ;
    return ; 
}

if(n==1)
{
    if(v[0]<=k)
    cout << 1 << nl ; 
    else
    cout << -1 << nl ; 
    return ; 
}
 
ll i = 0 ,j = n-1 ; 
ll ans =0 ,c= 0; 
while(i<j)
{
    ll sum = v[i]+v[j] ; 
    if(sum<=k)
    {ans++ ;i++ ,j-- ; } 
    else
    {
       j-- ;
       c++ ; 
    }
}
cout << ans+c << nl ;
}

ADD COMMENT • link 16 months ago Kshitiz Kumar • 0

0

Entering edit mode

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main(){

ios_base::sync_with_stdio(0);

cin.tie(0);

int n,m;

cin >> n >> m;

ll a[m];

vector<ll> ans(m,0);

for(int i=0;i<m;++i){

cin >> a[i];

}

vector<vector<int>> v(n);

for(int i=0;i<m;++i){

v[i%(n)].push_back(i);

}

ll diparture=0;

for(int i=0;i<n;++i){

if(v[i].size()!=0){

ans[v[i][0]]=a[v[i][0]]+1;

diparture=ans[v[i][0]];

}

for(int j=1;j<v[i].size();++j){

int val1=a[v[i][j]];

if(diparture>val1){

ans[v[i][j]]=diparture+1;

diparture++;

}

else{

diparture=val1+1;

ans[v[i][j]]=diparture;

}

for(int i=0;i<m;++i){

cout << ans[i] << "\n";

}

return 0;

}

solution for ques 2;

ADD COMMENT • link 13 months ago Himanshu kumar • 0

Login before adding your answer.

Airlift

Task

Example

Constraints

Shopping and billing

Function Description

Input format for custom testing

Output format

Constraints

Explanation

Special Package

Fuction Description

Input format for custom testing

Output format

Print an integer, representing the minimum absolute difference between the target price and the total cost of the package.

Constraints

1 <= N,M <= 70 1 <= price[i][j] <= 70 1 <= K <= 800

1 <= N,M <= 70
1 <= price[i][j] <= 70
1 <= K <= 800