COCI '14 Contest 2 #3 Studentsko

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 64M

Problem types

The annual student team competition in table tennis of students enrolled in University of Zagreb takes place next Saturday! Each team consists of $K$ ~K~ students. The excited students, $N$ ~N~ of them, are waiting in queue to register.

Krešo works at the registration desk. He doesn't really feel like doing his job so he decided not to allow students to choose a team. He decided that the first team will consist of the first $K$ ~K~ students standing in queue, the second team the following $K$ ~K~ students, the third one the following $K$ ~K~ students and so on… ( $N$ ~N~ will be divisible by $K$ ~K~ so nobody is left hanging.)

Ante has estimated the skill of each player with an integer. He would like to have the $K$ ~K~ strongest players in the first team, the following $K$ ~K~ strongest in the second team and so on…

Krešo has just taken a break and Ante decided to shift the students standing in queue so that he achieves his goal. The way he shifts them is that he tells a student to step out of the queue and go back in queue after another student or to go to the front of the queue. It takes him one minute to do this.

It's possible that Krešo is going to return from his break any moment so Ante needs to achieve his goal as soon as possible. Help Ante determine the minimal number of minutes necessary for him to achieve his goal.

Input Specification

The first line of input contains the integers $N$ ~N~ and $K$ ~K~ $(1 \le K \le N \le 5\,000)$ ~(1 \le K \le N \le 5\,000)~. The integer $N$ ~N~ is going to be divisible by $K$ ~K~.
The second line contains $N$ ~N~ space separated integers $v_i$ ~v_i~ $(1 \le v_i \le 10^9)$ ~(1 \le v_i \le 10^9)~, $i^{th}$ ~i^{th}~ number denotes the skill of the $i^{th}$ ~i^{th}~ player standing in queue.

All contestants are going to have distinct levels of skill.

Output Specification

The first and only line of output must contain the minimal required number of minutes.

Scoring

In test cases worth 30% of total points, it will hold $N \le 20$ ~N \le 20~.

Sample Input 1

4 1
9 12 5 13

Sample Output 1

Sample Input 2

6 2
16 2 1 7 5 10

Sample Output 2

Sample Input 3

6 3
7 9 8 3 6 5

Sample Output 3

Explanation of Output for Sample Input 3

Ante should move the students with skill levels 5, 6 and 3 to the front of the queue. It takes him three minutes to do that.

Comments

2

jimgao commented on Dec. 25, 2015, 3:36 p.m.

By saying

tells a student to step out of the queue and go back in queue after another student

Does it mean that the student can go behind anyone in the queue, or just the person that is normally behind him?

2

cheesecake commented on Dec. 25, 2015, 3:47 p.m.

Anyone. For example, in the 2nd sample, the solution is to move the student with skill level 16 to the back of the line.