Problems Base course RU

At most R alerts

sliding window queue rate limiting in production science and physics

A service sends earthquake alerts, but no more than r in any t consecutive seconds: if r alerts have already been sent in the last t seconds, a new event gets no alert. More precisely: an alert about an event at time x is sent if, among the alerts already sent, fewer than r were sent at times s with x − s < t. How many alerts will be sent?

Tests two to four are all earthquakes of magnitude five or more for 2015–2025 from the USGS catalogue. On the worst day, after the magnitude 8.8 earthquake off Kamchatka in July 2025, there were 166 of them.

Input

The first line holds n, r and t (1 ≤ n ≤ 2·10⁵, 1 ≤ r ≤ n, 1 ≤ t ≤ 10⁹). The second holds the n event times in seconds, in non-decreasing order, from 0 to 10⁹.

Output

The number of alerts sent.

Examples

Example 1

Input

10 2 10
1 3 5 9 10 11 13 20 21 22

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 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

The decision “send or not” depends only on the alerts of the last t seconds. Which of the alerts already sent need to be remembered, and when can they be forgotten?

2The idea

Keep a queue of the times of sent alerts. Before each event, drop from the head of the queue everything sent t seconds ago or earlier: that window has already moved on. If fewer than r remain in the queue, send and push the time onto the tail.

3Walkthrough

The event times are non-decreasing, so the queue sorts itself: old alerts at the head, new ones at the tail, and dropping is only ever from the head. The queue never holds more than r elements. Such a limiter is called a sliding log: it is the most precise of all but remembers every alert in the window; more about other methods in the article on rate limiting.

The window boundary: an alert sent exactly t seconds ago no longer counts (x − s < t). The example in the statement checks exactly this.

3+Solution

4Complexity

Each time enters the queue once and leaves it at most once: O(n) time and O(r) memory.

5Common mistakes

Fixed windows. Resetting the counter at the start of each hour is simpler, but at the junction of two hours lets through up to 2r alerts in t seconds, and the answers diverge.
The window boundary. “≥” and “>” when dropping from the queue give different answers when events come exactly t apart.
A list instead of a queue in Python. pop(0) shifts the whole list; with a large r that is quadratic.

Algorithms behind it

TEC Technique Sliding window A window of width w crawls along the data: the answer is corrected by the entering and leaving element in O(1) instead of O(w). O(n) 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 SYS Algorithm Rate limiting At most N requests per unit of time: a window, a log, two counters and a token bucket. O(1) per request (the log: O(N)) 2 problems