The better of two
A balancer hands out requests to k servers. For each request it asks two random servers how many unfinished jobs they have and gives the request to the one with fewer; on a tie, to the first of the two. Each server executes jobs one after another, in order of arrival: a job that arrived at moment t and needs s µs starts when the server finishes the previous ones, but not before t. A job is unfinished at moment t if it finishes strictly later than t.
Compute the sum and the maximum of the response times: from a request’s arrival to the end of its execution. The tests include the queue from the article: ten servers serving the site’s files of real sizes.
Input
The first line holds the number of servers k and the number of requests n (1 ≤ k ≤ 105, 1 ≤ n ≤ 105). Then n lines “t s a b”: the moment of arrival, the duration in microseconds and the two offered servers (1 ≤ a, b ≤ k, may coincide). Moments do not decrease; 0 ≤ t ≤ 1012, 1 ≤ s ≤ 106.
Output
Two numbers: the sum of response times and the largest of them.
In the second example the job on server 1 finishes exactly at moment 10, when the fourth request arrives: at that moment it no longer counts.
Examples
Example 1
3 5 0 5 1 2 1 5 1 2 2 5 1 2 8 5 3 1 12 1 1 3
24 8
Example 2
2 5 0 10 1 2 0 10 1 2 0 10 2 1 10 3 1 2 20 1 2 2
44 20
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
How many unfinished jobs does a server have at moment t? Those of its jobs that finish later than t. How do you know this number without recounting everything?
2The idea
A server works one job after another, so the completion times of its jobs increase in the order the jobs arrived. Keep for each server a queue of these moments. When a request arrives, throw out of the queues of the two candidates everything that has finished by moment t, from the head, while the head is at most t. What remains of the queue is the number of unfinished jobs. Each job is thrown out at most once, so all the cleaning costs O(n), not O(n·k): nobody touches the queues of the other servers until they are asked about.
3Walkthrough
The completion moment of a new job is max(when the server becomes free, t) + s; it is also the new end of the server’s queue. The response time is the difference with t. The sums are large, up to 105 requests with responses on long queues reaching fractions of a second, so Go needs int64, which an ordinary int provides.
The third test is the same queue as in the article, where the rule of two halves the mean response time compared with one random server. But the rule works only if what is asked about is the present: how many unfinished jobs there are now.
3+Solution
4Complexity
O(n + k): each job enters a queue once and leaves it once.
5Common mistakes
- How many were handed out rather than how many are unfinished. A counter of handed-out jobs always grows; a server that took many short jobs long ago is free now, and one that took a single huge file is busy. The first examples already go wrong this way.
- Cleaning all queues. The answer is the same, but with a hundred thousand servers that is a hundred thousand steps per request.
- The boundary. A job that finished exactly at the moment of arrival no longer gets in the way.
Algorithms behind it
O(d) per decision: learn the load of d servers
2 problems
DS
Data structure
Stack and queue
Stack: last in, first out. Queue: first in, first out. Every operation is O(1).
O(1) for push and pop, enqueue and dequeue
2 problems