Sorting and Simulation Algorithms to Compute the ATM Queue

This problem is from Google Kickstart (Round F 2020 – Kick Start 2020).

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 Ai. 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 Ai.

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.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.

Test Set 1
1 ≤ N ≤ 100.
1 ≤ Ai ≤ 100.
1 ≤ X ≤ 100.

Test Set 2
1 ≤ N ≤ 105 for at most 10 test cases. For the remaining cases, 1 ≤ N ≤ 100
1 ≤ Ai ≤ 109.
1 ≤ X ≤ 109.

Sample Input
2
3 3
2 7 4
5 6
9 10 4 7 2

Sample Output
Case #1: 1 3 2
Case #2: 3 5 1 2 4

In Sample Case #1, there are 3 people and the limit to withdraw in one turn is 3. Below is step-by-step description of how the process will look like:
The queue initially looks like [1, 2, 3]. The first person withdraws an amount of 2 in their first attempt and leaves the queue.
The queue now looks like [2, 3]. The second person wants to withdraw an amount of 7, but they can withdraw only 3 in their first turn. Since they still need to withdraw an amount of 4, they have to rejoin the queue at the end of the line.
The queue now looks like [3, 2]. The third person needs to withdraw an amount of 4 but they can only withdraw 3 in their first turn so, they rejoin the queue at the end of the line to withdraw amount of 1 later.
The queue now looks like [2, 3]. The second person still needs to withdraw an amount of 4. They withdraw an amount of 3 in their second turn and waits for their next turn to arrive to withdraw the remaining amount of 1.
The queue now looks like [3, 2]. The third person withdraws the remaining amount of 1 and leaves the queue.
The queue now looks like [2]. The second person withdraws the remaining amount of 1 and leaves the queue.
The queue is now empty.
The order in which people leave the queue is [1, 3, 2].

In Sample Case #2, there are 5 people and the limit to withdraw in one turn is 6. Below is step-by-step description of how the process will look like:
The queue initially looks like [1, 2, 3, 4, 5]. The first person withdraws an amount of 6, and joins at the end again to withdraw the remaining amount of 3 later.
The queue looks like [2, 3, 4, 5, 1]. The second person similarly withdraws an amount of 6 and waits for his next turn to withdraw an amount of 4.
The queue looks like [3, 4, 5, 1, 2]. The third person withdraws an amount of 4 and leaves the queue.
The queue now looks like [4, 5, 1, 2]. The fourth person withdraws 6 and waits for his next turn.
The queue looks like [5, 1, 2, 4]. The fifth person withdraws amount of 2 and leaves the queue.
The queue looks like, [1, 2, 4]. All other people now leave the queue after their second turn one by one.
The order in which people leave the queue is [3, 5, 1, 2, 4].

Analysis

Firstly, denote Ki as the number of times a person will use the ATM. Formally, Ki = ⌈Ai / X⌉.

Test Set 1
We can directly simulate the process using a queue.

Assume that i-th person, that wants to withdraw Ai, is first in the queue. There are two possibilites:

Ai ≤ X. In that case, this person withdraws Ai and leaves the queue. We can add i to the answer.
Ai > X. In that case, this person withdraws X (thus setting Ai to Ai – X) and goes back to the end of the queue.
Time complexity of this simulation is O(Σ Ki).

In the worst case, when X = 1, Ki = Ai. Since Ai ≤ 100, the worst time complexity is O(N × 100), which easily fits into the time limit.

Test Set 2
In the second test set, Ki can be as big as 109, so direct simulation is too slow.

Let’s look at two people i and j. When will i-th person leave the queue before j-th person? There are two cases:

Ki < Kj. Since i-th person will use the ATM fewer times than j-th person, they will leave the queue earlier.
Ki = Kj and i < j. If they both use the ATM the same amount of times, the person earlier in the queue in the initial configuration will leave first.
This observation is enough to form a full solution. Sort people first in ascending order of Ki, and in case of ties in ascending order of their number. After sorting, this is our answer.

Time complexity of this solution is O(N log N).

Simulation Algorithm to Compute ATM Queue

Simulation Algorithm can be implemented easily with the help of the queue. If a person does not withdraw enough money, we put him/her at the end of the queue. Otherwise, we record the sequence when he/she exits the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
void print(int T, int N, int X, vector<int> &A) {
    cout << "Case #" << T << ": ";
    int i = 0;
    vector<int> res;
    queue<pair<int, int>> Q;
    for (auto i = 0; i < A.size(); ++ i) {
        Q.push({i + 1, A[i]});
    }
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p.second <= X) {
            res.push_back(p.first);
        } else {
            Q.push({p.first, p.second - X});
        }
    }
    for (auto i = 0; i + 1 < res.size(); ++ i) {
        cout << res[i] << " ";
    }
    cout << res.back();
    cout << endl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int T;
    cin >> T;
    for (int i = 0; i < T; ++ i) {
        int N, X;
        cin >> N >> X;
        vector<int> A(N);
        for (int j = 0; j < N; ++ j) {
            cin >> A[j];
        }
        print(i + 1, N, X, A);        
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void print(int T, int N, int X, vector<int> &A) {
    cout << "Case #" << T << ": ";
    int i = 0;
    vector<int> res;
    queue<pair<int, int>> Q;
    for (auto i = 0; i < A.size(); ++ i) {
        Q.push({i + 1, A[i]});
    }
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p.second <= X) {
            res.push_back(p.first);
        } else {
            Q.push({p.first, p.second - X});
        }
    }
    for (auto i = 0; i + 1 < res.size(); ++ i) {
        cout << res[i] << " ";
    }
    cout << res.back();
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int T;
    cin >> T;
    for (int i = 0; i < T; ++ i) {
        int N, X;
        cin >> N >> X;
        vector<int> A(N);
        for (int j = 0; j < N; ++ j) {
            cin >> A[j];
        }
        print(i + 1, N, X, A);        
    }
    return 0;
}

The problem of the simulation algorithm is that it may take ages to complete if the amount he/she wishes to withdraw is far larger than the X that he/she can withdraw each time – i.e. it make take several rounds to finish.

Given N is scale of 10^5 – O(N^2) will yield Time limit Exceeded.

Compute the ATM Queue by using Sorting Algorithm

A better way would be to use the sorting algorithm, we actually don’t care how many rounds he/she needs to withdraw, instead, we just need to know who leaves the queue first. In this case, we can sort (A[i]+X-1)/X and if equal, sorted by order by the original position in the queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
void print(int T, int N, int X, vector<int> &A) {
    cout << "Case #" << T << ": ";
    int i = 0;
    vector<vector<int>> Q;
    for (auto i = 0; i < A.size(); ++ i) {
        Q.push_back({(A[i] + X - 1) / X, i + 1});
    }
    sort(begin(Q), end(Q));
    for (auto i = 0; i + 1 < Q.size(); ++ i) {
        cout << Q[i][1] << " ";
    }
    cout << Q.back()[1];
    cout << endl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int T;
    cin >> T;
    for (int i = 0; i < T; ++ i) {
        int N, X;
        cin >> N >> X;
        vector<int> A(N);
        for (int j = 0; j < N; ++ j) {
            cin >> A[j];
        }
        print(i + 1, N, X, A);        
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

void print(int T, int N, int X, vector<int> &A) {
    cout << "Case #" << T << ": ";
    int i = 0;
    vector<vector<int>> Q;
    for (auto i = 0; i < A.size(); ++ i) {
        Q.push_back({(A[i] + X - 1) / X, i + 1});
    }
    sort(begin(Q), end(Q));
    for (auto i = 0; i + 1 < Q.size(); ++ i) {
        cout << Q[i][1] << " ";
    }
    cout << Q.back()[1];
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int T;
    cin >> T;
    for (int i = 0; i < T; ++ i) {
        int N, X;
        cin >> N >> X;
        vector<int> A(N);
        for (int j = 0; j < N; ++ j) {
            cin >> A[j];
        }
        print(i + 1, N, X, A);        
    }
    return 0;
}

The algorithm takes O(N.LogN) to complete.

–EOF (The Ultimate Computing & Technology Blog) —