DMOPC '22 Contest 4 P4 - Anki Reviews

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Edward just lost his Anki streak of 981 days! Completely panic-stricken, he scrambles for ways to recover his lost streak. Luckily, he remembered that the streak calculator works based on Anki's time zone, and that changing the time zone could have the potential to recover some of his streak. Specifically, Edward has logged N reviews, the i-th review at minute t_i. In his world, each day consists of D minutes. If he picks a time zone that resets at minute x, then each day spans the minutes [x + kD, x + (k+1)D) for some integer k. A day is considered active if Edward did at least one review that day, and a streak is a consecutive sequence of active days. Your job is to determine the longest possible length of the longest streak, given that Edward picks an optimal value of x.


1 \le N \le 3 \times 10^5

1 \le t_i, D \le 10^9

Subtask 1 [5%]

D = 1

Subtask 2 [20%]

1 \le N \le 3 \times 10^3

Subtask 3 [75%]

No additional constraints.

Input Specification

The first line contains 2 integers N and D.

The next line contains N space-separated integers t_1, ..., t_N. These are given in non-decreasing order.

Output Specification

Output the length of the longest streak, given that Edward picks an optimal value of x.

Sample Input

5 3
3 5 5 7 16

Sample Output


Explanation for Sample

Edward can pick a reset time of 1. Then, the 0th day consists of minutes 1, 2, 3, the 1st day consists of minutes 4, 5, 6, the 2nd day consists of minutes 7, 8, 9, and so on. Days 0, 1, 2, and 5 are active, so the longest streak is 3 days.


There are no comments at the moment.