PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Simulation and Basic Math.
PROBLEM:
There exist a queue outside restaurant with initially M members in line, and N members shall arrive at times given in array A, find the minimum waiting time if, after every L time, one person from front of queue enter’s the restaurant, and you have to join the queue by K time.
SUPER QUICK EXPLANATION
- If there are X people ahead you and you join the queue at time T, then the waiting time is (X+1)*L-T.
- Just calculate waiting time for all A[i], considering people arrived before A[i]. Also, check the waiting time at time K. Print minimum.
EXPLANATION
The slow solution for this problem would be to simulate the queue for K seconds, noting the time for entering and exiting queue at various positions. Clearly, this solution is O(K) time, which will time out for final sub-task.
So, Let’s discuss the faster solution.
First of all, If we have X people in the queue at time T and we enter the queue now, The waiting time is (X+1)*L-T.
The reason is, that If there are X people ahead of you, they will enter at times L, 2*L \dots X*L and we will enter next time the restaurant opens, which happens after L more seconds, making the entering time X*L+L = (X+1)*L. We joined the queue at time T, so the waiting time is time to leave the queue less the time to join the queue, that is (X+1)*L-T.
Now, We can instantly calculate the waiting time at any unit of time. But the solution is still O(K) as we are calculating waiting time at each time. To speed up, we need the following observation.
Observation: It is always optimal to join the queue at time K or times when any other person joins the queue.
Let us assume that It is optimal to enter the queue at time T when no other person has arrived. Suppose the next person arrives at the T+A time. During time T to T+A, no other person arrives, which means, that exit time from the queue will remain the same if we enter during time interval [T, T+A]. So, to minimize waiting time, we will obviously choose to enter as late as possible during this interval. Hence, T+A offers lesser waiting time that time T. Hence, we reach a contradiction.
Hence, it is optimal to enter the queue at time K, or time just when another person arrives.
So, we can just sort the arrival timings, and calculate waiting times for each time a person arrives and for time K and print minimum waiting time as the answer.
Related problem:
Can you solve this problem, if A is not guaranteed to be distinct? What if in case you enter the queue at the same time as another person, then you stand behind them instead of the front. Think about it!
Time Complexity
Time complexity is O(N*logN) per test case due to sorting.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 