PVsNPSolver's blog

Amazon Hackon Coding Round

By PVsNPSolver, history, 3 years ago, In English

This question was asked for an Amazon hackathon coding round held almost two weeks ago which is over now. So I am assuming its alright to discuss the problem (rephrased) now. Please let me know if this is a common problem of priority queues/heaps which I am again assuming might be useful for a solution. Hoping for meaningful approaches and solutions from the codeforces community, which is truly helpful and supportive!

The Problem Statement:

A chef has n orders lined up. The waiting time penalty before an order starts getting processed is k. And for each order a corresponding processing time t is given (in minutes) along with its order id. The earning per order is c times the time taken to process the order. Find out the profits earned for each order from 1 to n and print them in order of the input. The order is free if the profits are negative for that order i.e. the profits is max(0,profit).

The following rules are used for processing the orders:

  1. Pick the order which arrives first. The chef can process only one order at a time.

  2. Among the orders already arrived, pick the one with the least processing time.

Input Format:

First the number of test cases T is given. Then T test cases follow. Each test case consists of n (the number of orders),c (the cost per minute it takes to process any order, which is same for all orders) and k (the waiting time penalty per minute, the chef faces once an order has arrived and is there in the "waiting to be processed queue"). Then in the following n lines an order with its arrival time and processing time is given. The order id of the first of these n lines is 1, the order id of the 2nd order is 2, and so on till the nth line has the order id n. Note that the input may or may not be sorted by the arrival time i.e. order 3 may arrive earlier than order 2 and so on.

Output Format: For each test case, print in a single line the profits earned for orders 1 to n, respectively.

Constraints:

1<=T<=10 ; 1<=n<=10^5 ; 1<=order arrival time, order processing time <= 10^9 ; 1<=k<=100 ; 1<=c<=10^4 ; Time limit: 1 second per test case

Example :

Input:

1
3 10 16
1 2
2 3
3 1

Explanation: The number of test cases T = 1. Number of orders n = 3. Processing cost per order per minute i.e. c = 10. Penalty cost for an order already arrived but in the waiting queue per minute of waiting i.e. k = 1. Then the list of orders follow. Order 1 arrives at time t=1. the chef does nothing from t=0 to t=1. Since he has to pick up the order which arrived first his profit earned for order 1 would be would be processing time*c — k*waiting time. Since the order was processed immediately as it came, the waiting time would be 0 for order 1. Hence, profit of order 1 = 2*10 — 16*0= 20. Now the time t=1+2=3 . Therefore both orders 2 and 3 have arrived and are in the waiting queue. But chef chooses order 3 to be processed first since it has less processing time. Therefore profit for order 3 is 1*10-16*0=10, as the order 3 was processed the moment it came. Now the time t=3+1=4 and the last order 2 is taken up which has been waiting for 4-2=2 minutes. Therefore the profit earned for order 2 = 3*10 — 16*2= 30 — 32 = -2. Therefore the order is free or profit = 0.

Output: 20 0 10

Any help would be appreciated. Here are the numerous approaches I took. First I did a simple sorting by arrival time and then used a map to get me the ones using upper bound and lower bound the items that would be in my absolute time range i.e. would have arrived by then and then used those to get the minimum processing time to process. I would keep doing that till all my orders would have been processed. The same approach I tried using priority queue and heap but failed for the case when the arrival time of say the last order was much ahead of the last order processed (which was already finished processing by then) and my range finding of orders failed and the program just halted in an infinite loop kind of situation. If I put an absolute time outer loop the time constraint would not be met. I am guessing an O(n log n) algorithm is needed to solve this question. Can anyone suggest efficient and easy approaches or codes?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my solution which I submitted in the test.

#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
#define fo(i,s,e_ex) for(i=s;i<e_ex;i++)
#define pbb push_back
#define all(x) x.begin(),x.end()

struct task{
	ll idx,at,bt;
};
bool comp(task p,task q){
	if(p.at==q.at){
		return p.bt<q.bt;
	}
	return p.at<q.at;
}
bool Compare(task a, task b){
	if(a.bt==b.bt){
		return a.idx>b.idx;
	}
	return a.bt>b.bt;
}
void solve(ll caseno){
    ll i,j,n,k,d,t=0;
	cin>>n>>k>>d;
	vector<task> arr;
	vector<ll> ans(n);
	fo(i,0,n){
		ll a,b;
		cin>>a>>b;
		task t;
		t.idx=i;t.at=a;t.bt=b;
		arr.pbb(t);
	}
	sort(all(arr),comp);
	priority_queue<task, std::vector<task>, decltype(&Compare)> pq(Compare);
	i=0;
	while((!pq.empty()) || i<n){
		if(pq.empty()){
			pq.push(arr[i]);
			t=arr[i].at;
			i++;
		}
		task curr = pq.top();pq.pop();
		ll wait = t-curr.at;
		t+=curr.bt;
		ll cost = curr.bt*k - wait*d;
		cost = max(cost,0ll);
		ans[curr.idx] = cost;
		while(i<n && arr[i].at<=t){
			pq.push(arr[i]);
			i++;
		}
	}
	for(auto v:ans) cout<<v<<' ';
	cout<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll t=1;
	cin>>t;
	for(ll i=1;i<=t;i++){
		solve(i);
	}
	return 0;
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks, did it get an AC?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, it was Accepted.

      Also, this question was based on Shortest Job First algorithm taught in Operating Systems. Do read it for better understanding.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks a lot! I know SJF, but got a new insight thanks to this approach of yours.

        → Reply