UTS Open '18 P3 - Restaurants

View as PDF

Submit solution

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

Problem types

Knowing that UTS is moving to 30 Humbert Street, you notice the lack of restaurants in the surrounding area. In order to maximize the happiness of the students, you plan to build new ones along Humbert Street. The N blocks on the street can be modelled as a 1-indexed array. Initially, there are V restaurants, on blocks a_1,\, a_2,\, a_3,\, \dots,\, a_V. (1 \le a_i \le N)

You want any consecutive segment of T blocks to have at least K restaurants. Additionally, no two restaurants can occupy the same block. Since you’re secretly stealing funds from the school to execute this plan, you want to minimize the total number of extra restaurants to build.

Input Format

The first line contains the four integers N, T, K, and V: the length of the road, the segment length to be checked, the number of desired restaurants in each segment, and the number of restaurants that already exist, respectively. (1 \le K \le T \le N \le 10^6,\ 1 \le V \le N)

The line contains V distinct integers a_1,\, a_2,\, a_3,\, \dots,\, a_V, the positions of the pre-existing restaurants. (1 \le a_i \le N)

Output Format

Print the minimum number of restaurants that must be built in order to satisfy the conditions.


Subtask 1 [20%]
1 \le N \le 10^3

Subtask 2 [80%]
1 \le N \le 10^6

Sample Input 1

10 4 2 3

Sample Output 1


Explanation for Sample Output 1

One possible solution is to build restaurants on blocks 5 and 8.

Sample Input 2

5 1 1 1

Sample Output 2


Explanation for Sample Output 2

4 restaurants must be built, on blocks 1, 2, 3, and 5.


There are no comments at the moment.