UTS Open '18 P3 - Restaurants

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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.


  • 4
    wleung_bvg  commented on July 13, 2020, 8:15 p.m.

    This problem previous had invalid data and an incorrect input format. The problem statement has been modified to reflect the actual input format, and the invalid cases have been removed. All out of contest submissions have been rejudged.