UTS Open '18 P3 - Restaurants

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.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, \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 Specification

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 next V lines each contain a single integer. The i^\text{th} line contains the integer a_i (1 \le a_i \le N), the positions of the i^\text{th} pre-existing restaurant. No two pre-existing restaurants will have the same position.

Output Specification

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.