Google Kickstart Round F 2020 Solutions: Part 1 (ATM Queue & Metal Harvest)

In this post, we are going to go through the first 2 problems, ATM Queue and Metal Harvest from Google Kickstart Round F 2020. Both of these problems are based upon one common concept. Ready to find out what it is? Then, let’s begin!

ATM Queue

Problem Statement

There are N people numbered from 1 to N, standing in a queue to withdraw money from an ATM. The queue is formed in ascending order of their number. The person numbered i wants to withdraw amount A_i. The maximum amount a person can withdraw at a time is X. If they need more money than X, they need to go stand at the end of the queue and wait for their turn in line. A person leaves the queue once they have withdrawn the required amount.

You need to find the order in which all the people leave the queue.

Input

The first line of the input gives the number of test cases T. T test cases follow.

The first line of each test case gives two space separated integers: the number of people standing in the queue, N and the maximum amount X that can be withdrawn in one turn.

The next line contains N space separated integers A_i.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the space separated list of integers that denote the order in which the people leave the queue.

Sample

Input	Output
2 3 3 2 7 4 5 6 9 10 4 7 2	Case #1: 1 3 2 Case #2: 3 5 1 2 4

Solution:

If a person wants to withdraw at most X amount, then he can directly withdraw it and exit from the queue. But if he wants to withdraw more than X, then he will have to reenter the queue multiple times until the amount that he wants to withdraw becomes less than X.

That is, the order in which he will leave the queue will be decided by the number of the times he will have to reenter the queue. This will be given by the weight = ceil(A_i/x).

Why to take ceil and not just do the usual floor division?

Consider the case where A_i = 9 and X=6. Here the person has to enter the queue twice (not just once) to withdraw the whole amount.

After that we just have to sort the array according to this weight. In case of a tie, the person with the smaller index will leave the queue first. So both the weight and index will be considered for sorting.

Time Complexity: O(NlogN)

Space Complexity: O(N)

Metal Harvest

Problem Statement

You are in charge of deploying robots to harvest Kickium from a nearby asteroid. Robots are not designed to work as a team, so only one robot can harvest at any point of time. A single robot can be deployed for up to K units of time in a row before it returns for calibration, regardless of how much time it spends on harvesting during that period. Harvesting can only be done during specific time intervals. These time intervals do not overlap. Given K and the time intervals in which harvesting is allowed, what is the minimum number of robot deployments required to harvest at all possible times?

Input

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case gives two space separated integers N and K: the number of time intervals in which harvesting is allowed, and the maximum duration a robot can be deployed for before returning for calibration.

The next N lines contain a pair of space separated integers S_i and E_i: the start time and the end time of the i-th interval respectively. Please note that intervals don’t include the time unit starting at the moment E_i, so for example an interval with (S_i = 2; E_i = 5) has duration of 3 time units.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of times robot deployment is needed so that for each interval there is one robot harvesting at that time.

Sample

Input	Output
2 3 5 1 5 10 11 8 9 3 2 1 2 3 5 13 14	Case #1: 2 Case #2: 3

Solution

In order to know the number of robot deployments, we will have to first sort the events in ascending order. As the events are non overlapping, there won’t arise a case wherein a particular time interval will be common to multiple events.

So now we just have to iterate over all the sorted events, and find the start and end of last time when the robot was deployed which is denoted by s and e.

Initially both s and e are -1. For each interval, we will have to check if the last robot deployed can cover the current interval, otherwise deploy new robot. In that case, pos will denote the start of the new deployment.

Beware! There can be cases like k=4 and current interval=[10,28] and e=9. Here the previous robot will have to leave at 9 units. So new deployment will start from pos=10. But there must be ceil((28-10)/4) = 5 deployments in total to cover this complete interval from 10 to 28. That is, [10,14], [14,18],[18,22],[22,26],[26,30] deployments, with the last robot deployed at s=26 and e=30.

Time Complexity: O(NlogN)

O(NlogN) will be time used for sorting. Traversing the array requires O(N)

Space Complexity: O(1)

Want some more fun? Then go check out the Google Kickstart Round F Solutions to other problems at:

• Google Kickstart Round F 2020 Solutions: Part 2 (Painter’s Duel)
• Google Kickstart Round F 2020 Solutions: Part 3 (Yeetzhee)